队列

队列

队列是一种先进先出的结构，假设你在排队，那么最先排队的人最先得到服务。我们只能从队尾添加元素，从队首取出元素。老规矩，我们首先规定一下队列Queue的API

public interface Queue<E> {
    //向队列中添加一个元素
    void enqueue(E e);
    //从队列中取出一个元素
    E dequeue();
    //获得队首的元素
    E getFront();
    //获取队列中元素的个数
    int getSize();
    //判断队列是否为空
    boolean isEmpty();
}

数组队列

现在我们将使用动态数组Array类来实现队列，实现的逻辑也十分的简单，如下

public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;
    public ArrayQueue() {
        array = new Array<>();
    }
    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }
    @Override
    public E dequeue() {
        return array.removeFirst();
    }
    @Override
    public E getFront() {
        return array.getFirst();
    }
    @Override
    public int getSize() {
        return array.getSize();
    }
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize()-1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

注意上面我们的dequeue操作是调用了动态数组的removeFirst操作，这个操作需要遍历整个数组将元素向前移动，所以该操作是O(n)的。

循环队列

上面队列的dequeue操作是O(n)级别的，这是因为上面会将数组整体向前移一位，但是如果我们不这么做，而是增加一个变量front来记录队首的位置，这样我们只要将front向前移一位即可，这样的操作就是O(1)级别的

这样做的同时，我们发现，如果当tail来到数组的末尾，按道理应该将数组进行扩容，但是front前面还有空间

这个时候我们应当将tail移动到数组头去

这时tail的计算公式不再是简单的tail = tail + 1，而是tail = (tail + 1) % data.length，如果不理解这个式子，就想象一下时钟，11点向前一步就是12点，也可以称为是0点，这个时候时钟的计算公式为(11 + 1) % 12。因为这种循环的特性，我们把这种实现方式称为循环队列。这次我们实现队列不在使用上面的动态数组，有了上面实现栈和队列的经验，想必可以容易理解下面的代码(在关键的步骤给予注释)

public class LoopQueue<E> implements Queue<E> {
    private int front;
    private int tail;
    //队列中元素的个数
    private int size;
    //底层实现的数组
    private E[] data;
    //构造方法初始化
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
        front = 0;
        tail = 0;
    }
    //默认容量为10
    public LoopQueue() {
        this(10);
    }
    @Override
    public void enqueue(E e) {
        //首先判断数组是不是满了，如果是那么就进行扩容
        if (size == data.length) {
            resize(2 * data.length);
        }
        //向队尾添加元素
        data[tail] = e;
        //tail向后移动 不是简单的+1 上面已有解释
        tail = (tail +1) % data.length;
        size++;
    }
    //数组伸缩操作，已接触过
    private void resize(int newCapacity) {
        E[] temp = (E[]) new Object[newCapacity];
        for (int i =0; i < size; i++) {
            //这里我们将队列的头对应到新数组的开头
            temp[i] = data[(front + i)%data.length];
        }
        //重新记录front和tail的位置
        front = 0;
        tail = size;
        data = temp;
    }
    @Override
    public E dequeue() {
        //如果队列为空，抛出异常
        if (size == 0) {
            throw new IllegalArgumentException("队列为空");
        }
        //获得出队的元素
        E e = data[front];
        data[front] = null;
        //front向前移动(带循环)
        front = (front + 1) % data.length;
        size--;
        //缩容操作，不做解释
        if (size == data.length / 4) {
            resize(data.length / 2);
        }
        return e;
    }
    @Override
    public E getFront() {
        if (size == 0) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }
    @Override
    public int getSize() {
        return size;
    }
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("Queue: size " + size);
        str.append(" capacity " + data.length);
        str.append("\nfront [");
        for (int i = 0; i < size; i++) {
            if (i == size - 1) {
                str.append(data[(front + i) % data.length].toString());
            } else {
                str.append(data[(front + i) % data.length].toString() + ", ");
            }
        }
        str.append("] tail");
        return str.toString();
    }
}

这次我们得到的dequeue操作就是O(1)的了(严格的讲均摊复杂度为O(1)，因为里面resize()复杂度是O(n)的)。