與前面提到的數據結構相同，隊列中的數據也呈線性排列。雖然與棧有些相似，但隊列中添加和刪除數據的操作分別是在兩端進行的，就和隊列這個名字一樣，把它想象成排成一隊的人更容易理解。在隊列中，處理總是從第一名開始往後進行，而新來的人只能排在隊尾。

隊列是什麼？

如上就是隊列的概念圖，現在隊列中只有數據 Blue。往隊列中添加數據時，數據被加在最上面。

然後，隊列中添加了數據 Green。往隊列中添加數據的操作叫作入隊。

緊接著，數據 Red 也入隊了。

從隊列中取出（刪除）數據時，是從最下麵，也就是最早入隊的數據開始的，即 Blue。從隊列中刪除數據的操作叫作出隊。

如果再進行一次出隊操作，取出的就是 Green 了。

像隊列這種最先進去的數據最先被取來，即先進先出的結構，我們稱為 First In First Out，簡稱 FIFO。

與棧類似，隊列中可以操作數據的位置也有一定的限制。在棧中，數據的添加和刪除都在同一端進行，而在隊列中則分別是在兩端進行的。隊列也不能直接訪問位於中間的數據，必須通過出隊操作將目標數據變成首位後才能訪問。

介紹完隊列的基本知識後，接下來舉一個例子，比如生活中常見的排隊買票。

如何理解隊列？

隊列這個概念非常好理解，你可以把它想象成排隊買票，先來的先買，後來的人只能站末尾，不允許插隊，先進者先出，這就是典型的隊列。

上一篇講到棧只支持兩個基本操作：入棧和出棧。隊列跟棧非常相似，支持的操作也很有限，最基本的操作也是兩個：入隊，放一個數據到隊列尾部；出隊，從隊列頭部取一個元素。

所以，隊列跟棧一樣，也是一種操作受限的線性表數據結構，隊列的概念很好理解，基本操作也很容易掌握。作為一種非常基礎的數據結構，隊列的應用也非常廣泛，特別是一些具有某些額外特性的隊列，比如迴圈隊列、阻塞隊列、併發隊列。

隊列的實現

看到這裡，相信你已經對隊列有了初步的理解，隊列主要包含兩個操作，入隊和出隊。光理解還不夠，我們還要動手去實現隊列，接下來讓我們來看一看如何用代碼實現一個隊列。

跟棧一樣，隊列可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫作順序棧，用鏈表實現的棧叫作鏈式棧。同樣，用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。

首先來看下用數組實現的隊列是怎麼樣的，其實現如下圖所示：

那麼我先用 Java 語言來實現下順序隊列，代碼如下：

/**
 * 基於數組實現的順序隊列
 *
 * @author wupx
 * @date 2020/02/13
 */
public class ArrayQueue {

    private String[] items;
    /**
     * 數組大小
     */
    private int n = 0;
    /**
     * 隊頭下標
     */
    private int head = 0;
    /**
     * 隊尾下標
     */
    private int tail = 0;

    /**
     * 申請一個大小為 capacity 的數組
     *
     * @param capacity
     */
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    /**
     * 入隊
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        // 如果 tail == n 表示隊列已經滿了
        if (tail == n) {
            return false;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    /**
     * 出隊
     *
     * @return
     */
    public String dequeue() {
        // 如果 head == tail 表示隊列為空
        if (head == tail) {
            return null;
        }
        String ret = items[head];
        ++head;
        return ret;
    }
}

另外一種就是鏈式隊列，它的實現如下圖所示：

再用鏈表去實現隊列，代碼如下：

/**
 * 基於鏈表實現的鏈式隊列
 *
 * @author wupx
 * @date 2020/02/13
 */
public class LinkedListQueue {
    /**
     * 隊頭
     */
    private Node head = null;
    /**
     * 隊尾
     */
    private Node tail = null;

    /**
     * 入隊
     *
     * @param value
     */
    public void enqueue(String value) {
        if (tail == null) {
            Node newNode = new Node(value, null);
            head = newNode;
            tail = newNode;
        } else {
            tail.next = new Node(value, null);
            tail = tail.next;
        }
    }

    /**
     * 出隊
     *
     * @return
     */
    public String dequeue() {
        if (head == null) {
            return null;
        }

        String value = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    private static class Node {
        private String data;
        private Node next;

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

        public String getData() {
            return data;
        }
    }
}

到此，我們就分別實現了基於數組和鏈表的隊列，大家可以自己實現下。

隊列還有很多擴展，比如迴圈隊列、阻塞隊列、併發隊列等，將在以後的文章中進行介紹。

總結

這篇主要講了一種跟棧很相似的數據結構-隊列，也是一種線性邏輯結構。

隊列遵循先進先出（FIFO）的原則，主要的兩個操作是入隊和出隊。隊列既可以用數組來實現，也可以用鏈表來實現。用數組實現的叫順序隊列，用鏈表實現的叫鏈式隊列。

參考

《我的第一本演算法書》