與前面提到的數據結構相同，隊列中的數據也呈

隊列是什麼？

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

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

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

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

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

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

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

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

如何理解隊列？

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

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

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

隊列的實現

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

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

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

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

<code>/** * 基於數組實現的順序隊列 * * @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;    }}/<code> 

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

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

<code>/** * 基於鏈表實現的鏈式隊列 * * @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;        }    }}/<code>

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

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

總結

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

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

參考

《我的第一本算法書》

閱讀更多 武培軒 的文章

關鍵字: 數據結構 隊列 最先