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

佇列是什么？

如上就是佇列的概念圖，現在佇列中只有資料 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 = https://www.cnblogs.com/wupeixuan/p/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 = https://www.cnblogs.com/wupeixuan/p/data;
            this.next = next;
        }

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

到此，我們就分別實作了基于陣列和鏈表的佇列，大家可以自己實作下，

佇列還有很多擴展，比如回圈佇列、阻塞佇列、并發佇列等，將在以后的文章中進行介紹，

總結

這篇主要講了一種跟堆疊很相似的資料結構-佇列，也是一種線性邏輯結構，

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

參考

《我的第一本演算法書》

標籤：其他

上一篇：論plc在交通燈中的應用

下一篇：有什么其他方法可以快速的求出這ab兩端的等效電阻。（不用萬用表測量的方法）