队列

队列是一种常用的数据结构，它的主要特点是先进先出(FIFO—first in first out)，从队尾(rear)入队，从队头(front)出队。

队列的实现有很多方式，比如基础实现(数组 \ 链表)，或结合了其他特性的变种(优先队列 \ 双端队列)等。

不考虑一些高级特性，基础实现中，数组队列存在空间复用导致的数据移动问题，链表队列则有占用空间大和碎片化的问题。

这些问题在当代应用层编程中，受益于高规格硬件和高级语言特性，绝大多数场景影响不大。

但是，在硬件底层开发，特别是嵌入式开发中还是有较大影响的。环形队列以其简单高效的实现特性，广泛用于网络数据收发，和不同程序间数据交换。

环形队列

实际的底层内存中是不存在环形结构的，环形队列真实使用的是数组的线性空间。

在真实实现过程中，由于判断队列空和判断队列满的条件都是头尾指针相等，存在二义性，所以一般将判断队列满的条件改为头尾差1，这样会造成最大容量比实际容量少一

队列空: Front = Rear

队列满: Front = Rear + 1

代码实现

public class CircularQueue {

    /**
     * capacity of queue
     */
    private int capacity;

    private int front = 0;
    private int rear = 0;
    private String[] data;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        data = new String[capacity];
    }

    /**
     * if queue full
     */
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    /**
     * if queue empty
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * get data size in queue
     */
    public int size() {
        return (rear + capacity - front) % capacity;
    }

    /**
     * enqueue
     */
    public void enQueue(String ele) {

        if (this.isFull()) {
            throw new RuntimeException("CircularQueue full");
        }

        data[rear] = ele;
        rear = (rear + 1) % capacity;
    }

    /**
     * dequeue
     */
    public String deQueue() {

        if (this.isEmpty()) {
            throw new RuntimeException("CircularQueue empty");
        }

        String res = data[front];
        front = (front + 1) % capacity;
        return res;
    }
}