队列，又称为伫列（queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

队列顾名思义就是我们现实中的队列，用于顺序处理数据。它的 FIFO 的性质在对于顺序排列数据非常有用，高并发下可以用消息队列进行流量削峰，多线程下可以用全局的队列可以让数据变为同步处理。

队列的基本操作

操作	API	描述
添加数据	EnQueue	新元素入队
移除数据	DeQueue	队首元素出队
查看队首	Peek	查看队首元素

一个基本的队列必须实现以上的 API，有的地方会写道最基本的操作是 EnQueue 和 DeQueue，但这两个仅仅只是队列的数据操作，但我们对队列的所有操作并非一直都是数据读写操作。

Peek 操作是对队列的状态的描述之一，Peek 操作可以让我们知道队列是否为空，队首元素的状态，而队列的长度、队首之后的其他元素这些信息并不是我们必须关心的。

队列的实现

队列的实现分为两种：链表实现和顺序表实现

链表实现并不需要关心栈的容量，实现起来较为方便。顺序表实现由于在初始化队列的时候需要设定顺序表的长度，因此涉及到了判断是否队列满和是否扩容的操作；同时由于队列需要操作队首和队尾两个指针，因此在指针不段右移的时候最终会触底，前面已经出队的空间将会被浪费，因此我们对于队列的顺序实现，一般都采用循环队列的方式，即当队列触底发生时，将指针移回数组顶部。

先定义一个队列的虚基类，继承 Vector，设定好必需的 API：

public abstract class Vector<E> {

    /**
     * 容器当前元素数量
     */
    protected int size = 0;

    /**
     * 判断该容器是否为空
     *
     * @return 为空则返回 true
     */
    public synchronized boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 获取概况容器中元素的数量
     *
     * @return 元素的数量
     */
    public synchronized int getSize() {
        return this.size;
    }
}

public abstract class Queue<E> extends Vector<E> {

    /**
     * 入队
     *
     * @param element 待入队元素
     * @return 若成功入队返回 true
     */
    public abstract boolean enQueue(E element);

    /**
     * 元素出队
     *
     * @return 元素
     */
    public abstract E deQueue();

    /**
     * 获取栈顶部的元素
     *
     * @return 容器头部的元素
     */
    public abstract E peek();
}

队列的顺序实现

/**
 * 队列的链表实现
 * 
 * @param <E> 元素类型
 */
public class LinkedListQueue<E> extends Queue<E> {
    SingleLinkedListNode<E> head;
    SingleLinkedListNode<E> tail;

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
    }

    @Override
    public synchronized boolean enQueue(E element) {
        SingleLinkedListNode<E> node = new SingleLinkedListNode<>(element, null);
        if (isEmpty()) {
            this.head = node;
        } else {
            this.tail.next = node;
        }
        this.tail = node;
        this.size += 1;
        return true;
    }

    @Override
    public E deQueue() {
        if (isEmpty())
            return null;
        SingleLinkedListNode<E> firstNode = this.head;
        this.head = firstNode.next;
        if (this.size == 1) {
            this.tail = null;
        }
        this.size -= 1;
        return firstNode.data;
    }

    @Override
    public E peek() {
        if (isEmpty())
            return null;
        return this.head.data;
    }
}

队列的链表实现

/**
 * 队列的顺序实现 - 循环队列实现
 * @param <E>
 */
public class ArrayQueue<E> extends Queue<E> {
    private int factor = 1;
    private int capacity;
    private boolean isExtendible = true;
    private Object[] elements;

    /**
     * 头指针应如果和尾指针相同，表示空队列
     */
    private int head = 0;
    private int tail = 0;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public ArrayQueue(int capacity, int factor) {
        this.factor = factor;
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public ArrayQueue(int capacity, boolean isExtendible, int factor) {
        this.capacity = capacity;
        this.isExtendible = isExtendible;
        this.factor = isExtendible ? factor : 1;
        this.elements = new Object[capacity];
    }

    @Override
    public boolean enQueue(E element) {
        return this.isExtendible ? enQueueWithExtension(element) : enQueueWithoutExtension(element);
    }

    /**
     * 入队操作，容量不足则进行扩容操作
     *
     * @param element 待入队元素
     * @return 若成功入队，则返回 true
     */
    private boolean enQueueWithExtension(E element) {
        ensureCapacity();
        this.elements[this.tail] = element;
        this.tail = (this.tail + 1) % this.capacity;
        this.size += 1;
        return true;
    }

    /**
     * 入队操作，容量不足不允许入队
     *
     * @param element 待入队元素
     * @return 若成功入队，则返回 true
     */
    private boolean enQueueWithoutExtension(E element) {
        if (this.size == this.capacity)
            return false;
        this.elements[this.tail] = element;
        this.tail = (this.tail + 1) % this.capacity;
        this.size += 1;
        return true;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E deQueue() {
        if (isEmpty())
            return null;
        int idx = this.head;
        this.head = (this.head + 1) % this.capacity;
        this.size -= 1;
        return (E) this.elements[idx];
    }

    @Override
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty())
            return null;
        return (E) this.elements[this.head];
    }

    private void ensureCapacity() {
        if (this.size + 1 <= this.capacity * this.factor)
            return;
        /* 如果是正序的，则直接扩容 */
        if (this.head < this.tail) {
            this.capacity += 1;
            this.elements = Arrays.copyOf(this.elements, this.capacity);
            return;
        }
        /* 如果是循环的，重新排列元素 */
        Object[] newElements = new Object[this.capacity + 1];
        System.arraycopy(this.elements, this.head, newElements, 0, this.capacity - this.head);
        System.arraycopy(this.elements, 0, newElements, this.capacity - this.head, this.tail);
        this.head = 0;
        this.tail = this.size;
        this.capacity += 1;
        this.elements = newElements;
    }
}