队列

队列跟数组一样，也是一种线性结构。相比数组，队列对应的操作是数组的子集，只能从一端(队尾)添加元素，也只能从一端(队首)取出元素。队列是一种先进先出的数据结构（FIFO）。

队列代码实现

首先，我们先定义一个队列需要用到的接口方法，因为队列的底层实现可以是多样的，只要实现了接口方法的，都可以称为队列。

队列接口定义

public interface Queue<E> {

    /**
     * 返回队列内元素的个数
     */
    int getSize();

    /**
     * 队列内元素个数是否为空
     */
    boolean isEmpty();

    /**
     * 向队尾添加一个元素
     */
    void enqueue(E e);

    /**
     * 移除队首元素
     */
    E dequeue();

    /**
     * 查看队首元素
     */
    E getFront();
}

底层为数组的队列实现

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();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front [");
        for (int i = 0; i < getSize(); i++) {
            res.append(array.get(i));
            if (i != getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

时间复杂度分析

int getSize() ，O(1) 级别

boolean isEmpty() ， O(1) 级别

void enqueue(E e) ， O(1) 级别，均摊

E dequeue() ， O(n) 级别

E getFront() ， O(1) 级别

循环队列代码

上述代码出队的时间复杂度为 O(n) 级别的，当数据量大的时候，性能比较差，如果想把复杂度变为 O(1) 级别的，可以用循环队列来实现。

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    // 指向队首的位置
    private int front;
    // 指向队尾即将被添加元素的位置（不是队尾的位置，队尾的下一个位置）
    private int tail;
    // 队内实际存储元素的个数
    private int size;

    public LoopQueue(int capacity) {
        // 为防止元素装满时 front == tail ，所以故意空出一个位置
        // 但为了保证元素个数，把容量做 +1 处理
        data = (E[]) new Object[capacity + 1];
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        // 创建的时候做了 +1 处理，这里应当 -1
        return data.length - 1;
    }

    @Override
    public void enqueue(E e) {
        // 当元素装满时，扩容
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        // 维护 tail 的位置，要循环处理，所以取模运算
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 扩容，均摊时间复杂度O(1)
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // 从 front 开始，把所有元素复制到新对象中，索引从 0 开始
            newData[i] = data[(i + front) % data.length];
        }
        // 将当前数组对象指向新的数组对象
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        E ret = data[front];
        data[front] = null;// 把没用到的对象置null，利于GC释放内存
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() { return front == tail; }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LoopQueue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        // 这种遍历方式也是可以的
       /* for (int i = 0; i < size; i++) {
            res.append(data[(i+front)%data.length]);
            if (i != size - 1) {
                res.append(", ");
            }
        }*/

        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

ArrayQueue 和 LoopQueue 性能比较

public class Main {

    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        System.out.println("arrayQueue need time = " + testQueue(arrayQueue, opCount));
        System.out.println("loopQueue need time = " + testQueue(loopQueue, opCount));
    }

    /**
     * 测试队列的运行时间
     */
    private static double testQueue(Queue<Integer> queue, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            queue.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            queue.dequeue();
        }
        long endTime = System.nanoTime();
        // 纳秒转成秒
        return (endTime - startTime) / 1000000000.0;
    }
}

运行结果：

arrayQueue need time = 60.940822538

loopQueue need time = 0.055889565

总结：LoopQueue 的性能比 ArrayQueue 好很多，因些 LoopQueue 是 O(1)级别的，ArrayQueue 是 O(n)级别的。