看完这篇你还不知道这些队列，我这些图白作了

队列有两个重要的概念，一个叫队头，一个叫队尾，队头指向的是第一个元素，而队尾指向的是最后一个元素。队列跟栈一样也是访问受限制的，所以队列也只有两个主要的操作： 入队(enqueue)操作 和 出队(dequeue)操作 。入队操作就是将一个元素添加到队尾，出队操作就是从队头取出一个元素。

队列的底层实现可以用数组和链表，基于数组实现的队列叫作 顺序队列 ，基于链表实现的队列叫作 链式队列 ，下面我们分别用数组和链表来简单的实现这两种队列。

基于数组的队列

不管使用那种方式来实现队列，都需要定义两个指针分别指向队头和队尾，本文中我们用 head 指向队头， tail 指向队尾，后面的示例中这将默认使用这个，有特殊的地方我会进行说明，先来看看顺序队列的入队、出队操作。

图中可以看出，入队时，队尾往后移动，队头保持不变，出队是队头往后移动，队尾保持不变。入队、出队操作的逻辑都比较简单，可能你有疑问的地方是： 出队时为什么队头要往后移动而不是一直指向数组下标为 0 的位置？ 为什么呢？如果我们保持队头一直指向数组下标为 0 的位置，那每次出队操作后，后面的数据都需要往前挪一位，换句话说每次出队操作都需要进行数据迁移，而数据迁移的代价比较大，每次数据迁移的时间复杂度为O(n)，这样会极大的影响队列的使用性能。如果我们出队时，队头往后移动一位，这样我们就避免每次出队都进行数据迁移，我们只需要在只有在 tail 等于数组大小且 head 不等于 0 时，进行一次数据迁移，将已经出队留下的空间继续供入队时使用。下图是数据迁移的过程：

数据迁移时，从 head 位置开始的数据都需要往前移动 head 位，这样就把出队后的空间腾出来，供后续入队操作使用。

基于数组的队列实现代码：

/**
 * 基于数组的队列
 */
public class ArrayQueue {

    // 存放数据的数组
    private String[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;
    // 最后一个节点
    private int tail = 0;

    // 构造函数
    public ArrayQueue(int size){
        this.size = size;
        items = new String[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        // 如果最后一个节点等于容器大小，说明队列满了
        /**
         * 判断队列满了的条件，tail = size,head = 0,
         */
        if (tail == size && head == 0) return -1;

        /**
         * 如果tail = size，但是head != 0,说明前有数据删除，队列未满，需要数据迁移
         */
        if (tail == size){
            // head 后面的数据都需要往前迁移 head 位
            for (int i= head;i< size;i++){
                items[i-head] = items[i];
            }
            // 将最后一个元素迁移 head 位
            tail -=head;
            // 第一个元素指向 0
            head = 0;
        }
        // 向队列中添加元素
        items[tail] = data;

        tail++;

        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        // 第一个元素和最后一个元素相等时，队列为空
        if (head == tail) return null;

        String result = items[head];
        // 第一个元素后移一次，这样做的好处是在出队时不需要数据迁移
        head ++ ;

        return result;
    }
}

链式队列

链式队列实现起来相对顺序队列来说要简单很多，我们先来看看链式队列的入队、出队操作：

从图中可以看出链式队列入队操作是将 tail 的 next 指向新增的节点，然后将 tail 指向新增的节点，出队操作时，将 head 节点指向 head.next 节点。链式队列与顺序队列比起来不需要进行数据的迁移，但是链式队列增加了存储成本。

基于链表的队列实现代码

/**
 * 基于链表的队列
 */
public class LinkQueue {

    // 指向队首
    private Node head;
    // 指向队尾
    private Node tail;

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        Node node = new Node(data,null);
        // 判断队列中是否有元素
        if (tail == null) {
            tail = node;
            head = node;
        }else {
            tail.next = node;
            tail = node;
        }
        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        if (head==null) return null;
        String data = head.data;
        head = head.next;
        // 取出元素后，头指针为空，说明队列中没有元素，tail也需要制为空
        if (head == null){
            tail = null;
        }
        return data;
    }

    class Node{
        private String data;
        private Node next;

        public Node(String data,Node node){
            this.data = data;
            next = node;
        }
    }
}

循环队列

循环队列是对顺序队列的改进，因为顺序队列不可避免的数据迁移操作，数据迁移操作会导致队列的性能下降，为了避免这个问题，将队列改造成循环的，当 tail 到达数组的最大下标时，重新指回数组下标为 0 的位置，这样就避免了数据迁移。先来看看循环队列的出队、入队操作：

因为队列是循环队列，所以在进行入队、出队操作时，就不能像顺序队列那样对 tail 、 head 进行简单的加 1 操作，我们需要对 tail 、 head 加 1 后与数组的大小进行求余操作，来得出 tail 、 head 的值，这样才能进行循环操作。循环队列需要牺牲一个存储空间，对于一个存储空间为 n 的循环队列来说只能存放 n-1 为数据，因为如果不牺牲一个存储空间的话，当 tail==head 时，就有可能存在队空或者队满的情况。

循环队列的实现代码

/**
 * 环形队列,不需要数据迁移，提高性能
 */
public class CircularQueue {

    // 存放数据的数组
    private String[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;
    // 最后一个节点
    private int tail = 0;

    // 构造函数
    public CircularQueue(int size){
        this.size = size;
        items = new String[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(String data){
        /**
         * 判断环形队列满了的条件，(tail+1)求余等于head
         */
        if ((tail+1)%size == head) return -1;

        // 向队列中添加元素
        items[tail] = data;
        // 因为是环形队列，所以下边是数组长度的余数
        tail= (tail+1)%size;

        return 1;
    }

    /**
     * 出队操作
     * @return
     */
    public String dequeue(){
        // 第一个元素和最后一个元素相等时，队列为空
        if (head == tail) return null;

        String result = items[head];
        // 因为是环形队列，所以下边是数组长度的余数
        head = (head+1)% size ;

        return result;
    }
}

双端队列

双端队列是一种队头、队尾都可以进行入队、出队操作的队列，双端队列采用双向链表来实现，先来看一下双端队列的入队、出队操作：

可以从动态图中看出，双端队列的每一端都是一个栈，都符合栈先进后出的特性，如果我们对双端队列进行禁止队头入队和队尾出队操作的限制，双端队列又变成了一个链式队列，双端队列是一种多功能的数据结构，我们可以使用它来提供队列和栈两种功能。

双端队列的实现代码

/**
 * 双端队列，使用双向链表实现
 */
public class DoubleEndsQueue {

    private static class Node {
        String item;
        Node next;
        Node prev;

        Node(Node prev, String element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    // 第一个节点
    private Node first;
    // 最后一个节点
    private Node last;

    /*
     * 在第一个节点前面入队
     */
    public void enqueueFirst(String e) {
        final Node f = first;
        final Node newNode = new Node(null, e, f);
        // 第一个节点指向新节点
        first = newNode;
        if (f == null)
            // 最后一个节点也指向该节点
            last = newNode;
        else
            // 当前节点的前节点指向新节点
            f.prev = newNode;
    }

    /**
     * 在最后一个元素后面入队
     * @param e
     */
    public void enqueueLast(String e) {
        final Node l = last;
        final Node newNode = new Node(l, e, null);
        // 最后一个节点指向新节点
        last = newNode;
        if (l == null)
            // 第一个节点指向新节点
            first = newNode;
        else
            // 当前节点的下节点指向新节点
            l.next = newNode;
    }

    /**
     * 从第一个节点出队
     * @return
     */
    public String dequeueFirst() {
        if (first == null) return null;
        final Node f = first;
        String element = f.item;
        Node next = f.next;
        f.item = null;
        f.next = null;
        // 第一个节点指向当先节点的next节点
        first = next;
        if (next == null)
            // 说明队列为空
            last = null;
        else
            next.prev = null;
        return element;
    }

    /**
     * 从最后节点出队
     * @return
     */
    public String dequeueLast() {
        final Node l = last;
        if (last == null) return null;
        String element = l.item;
        Node prev = l.prev;
        l.item = null;
        l.prev = null;
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        return element;
    }
    
    // 输出队列全部内容
    public void displayAll() {
        while (first !=null){
            System.out.print(first.item+" ");
            first = first.next;
        }
        System.out.println("===============");
    }
}

优先队列

在示例中，我们规定数值越小优先级越高。我们每执行一次入队操作时，小的元素都会靠近头队，在出队的时候，元素小的也就先出队。

优先队列的代码实现

这里使用的数组实现优先队列，用数组实现主要原因是更好理解优先队列的思想。一般都是使用堆来实现优先队列，因为数组实现在插入的时候对数据的排序代价比较大。

/**
 * 优先队列
 */
public class PriorityQueue {

    // 存放数据的数组
    private Integer[] items;
    // 容器的大小
    private int size = 0;
    // 第一个节点
    private int head = 0;

    // 构造函数
    public PriorityQueue(int size){
        this.size = size;
        items = new Integer[size];
    }

    /**
     * 入队操作
     * @param data
     * @return
     */
    public int enqueue(Integer data){
        int j;
        if (head == 0){
            items[head++] = data;
        }
        else {
            for (j=head-1;j>=0;j--){
                // 将小的数往后排
                if (data > items[j]){
                    items[j+1] = items[j];
                }else {
                    break;
                }
            }
            items[j+1] = data;
            head++;
        }
        return 1;
    }

    public Integer dequeue(){
        return items[--head];
    }
}

总结

• 队列是一种遵循先进先出(FIFO)的数据结构
• 队列可以使用数组和链表实现，数组实现叫作顺序队列，链表实现叫作链式队列
• 循环队列解决了顺序队列的数据迁移带来的性能损耗的问题
• 双端队列是队头和队尾都可以进行入队、出队操作的队列
• 优先队列是一种不必遵循先进先出规则的队列，任意元素加入时，都会讲优先级最高的放入到队头

最后