『數據結構與演算法』隊列

• 2021 年 2 月 15 日
• 筆記
• 數據結構, 數據結構與演算法, 演算法, 隊列

微信搜索：碼農StayUp
主頁地址：//gozhuyinglong.github.io
源碼分享：//github.com/gozhuyinglong/blog-demos

1. 隊列（queue）

隊列和棧一樣，也是一個操作受限制的線性表。不同的是隊列的插入在一端進行，我們稱為隊尾（rear）；而刪除（取出）在另一端進行，我們稱為隊頭（front）。

隊列是一個先進先出（FIFO – First In First Out）的有序列表，其操作只有兩種：

• 入隊（enqueue）：向隊尾添加一個元素
• 出隊（dequeue）：從隊頭刪除（取出）一個元素

2. 隊列的數組實現

如同棧一樣，對隊列的每一種操作，鏈表實現或數組實現都給出快速的運行時間。隊列的鏈表實現是簡單而直接的，我們就不過介紹了。下面我們討論如何使用數組實現一個隊列。

先看下圖，我們需要聲明一個數組，並維護兩個指針：

• head指針：指向待出列的元素位置
• tail指針：指向待入列的存儲位置
  可以看出，到達隊尾後無法再添加新的元素，然後前面已出列的位置還空著。

上面問題我們可以將數組進行首尾相連，形成一個環形數組，即指針到達數組尾部後，重新指向數組頭部，如下圖所示。

這裡需要注意幾點：

• 判斷空隊列可以通過head == tail
• 判斷隊列滿不能再通過head與tail重合，而是需要空出一個存儲空間來，即：head == tail + 1。而環形數組需要取模運算，所以正確判斷隊列滿：head == (tail + 1) % capacity。
• 數組真實容量應為：指定容量 + 1

3. 程式碼實現

下面程式碼是使用環形數組實現的隊列，所以又叫做環形隊列。
其容量為：指定容量 + 1，head 與t ail 初始值為0。隊列存儲元素使用了泛型，所以可以操作你想用的數據類型。下面看具體實現：

public class ArrayQueueDemo {

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("出隊： --> " + queue.get());
        System.out.println("入隊：1 --> " + queue.add(1));
        System.out.println("入隊：2 --> " + queue.add(2));
        System.out.println("入隊：3 --> " + queue.add(3));
        System.out.println("入隊：4 --> " + queue.add(4));
        System.out.println("入隊：5 --> " + queue.add(5));

        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("出隊： --> " + queue.get());
        System.out.println("入隊：6 --> " + queue.add(6));
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("入隊：7 --> " + queue.add(7));
        System.out.println("出隊： --> " + queue.get());
        System.out.println("出隊： --> " + queue.get());
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("入隊：8 --> " + queue.add(8));
        System.out.println("入隊：9 --> " + queue.add(9));
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("出隊： --> " + queue.get());
        System.out.println("出隊： --> " + queue.get());
        System.out.println("出隊： --> " + queue.get());
        System.out.println("出隊： --> " + queue.get());
        System.out.println("出隊： --> " + queue.get());
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
        System.out.println("入隊：10 --> " + queue.add(10));
        System.out.printf("頭指針: %s\t尾指針: %s\t隊列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity);
    }


    private static class ArrayQueue<T> {

        private final T[] queue; // 存儲隊列數據元素
        private final int capacity; // 容量
        private int head = 0; // 頭部指針，指向隊頭元素
        private int tail = 0; // 尾部指針，指向下一個待入隊元素的存儲位置

        public ArrayQueue(int capacity) {
            this.capacity = capacity + 1; // 環形隊列需要空出一個位置，來滿足隊列滿時head與tail不重合
            this.queue = (T[]) new Object[this.capacity];
        }

        /**
         * 向隊列添加一個元素
         *
         * @param data
         * @return
         */
        public boolean add(T data) {
            // 隊列滿，添加失敗
            if (isFull()) {
                return false;
            }
            // tail指向下一個待入隊元素的存儲位置，所以先賦值再讓指針加1
            queue[tail] = data;
            // 環形數組需要取模運算
            tail = (tail + 1) % capacity;
            return true;
        }

        /**
         * 從隊列中獲取一個元素
         *
         * @return
         */
        public T get() {
            if (isEmpty()) {
                return null;
            }
            // head指向頭元素位置，所以先取出再讓指針加1
            T data = queue[head];
            // 環形數組需要取模運算
            head = (head + 1) % capacity;
            return data;
        }

        /**
         * 當前隊列大小
         *
         * @return
         */
        public int size() {
            int size = tail - head;
            if (size < 0) {
                size += capacity;
            }
            return size;
        }

        /**
         * 隊列是否為空：當tail與head指向同一位置時，表示隊列為空
         *
         * @return
         */
        public boolean isEmpty() {
            return tail == head;
        }

        /**
         * 隊列是否已滿：因為預留了一個位置，所以tail需要加1；環形隊列需要取模運算
         *
         * @return
         */
        public boolean isFull() {
            return head == (tail + 1) % capacity;
        }

    }
}

輸出結果：

頭指針: 0	尾指針: 0	隊列大小: 0	容量: 6
出隊： --> null
入隊：1 --> true
入隊：2 --> true
入隊：3 --> true
入隊：4 --> true
入隊：5 --> true
頭指針: 0	尾指針: 5	隊列大小: 5	容量: 6
出隊： --> 1
入隊：6 --> true
頭指針: 1	尾指針: 0	隊列大小: 5	容量: 6
入隊：7 --> false
出隊： --> 2
出隊： --> 3
頭指針: 3	尾指針: 0	隊列大小: 3	容量: 6
入隊：8 --> true
入隊：9 --> true
頭指針: 3	尾指針: 2	隊列大小: 5	容量: 6
出隊： --> 4
出隊： --> 5
出隊： --> 6
出隊： --> 8
出隊： --> 9
頭指針: 2	尾指針: 2	隊列大小: 0	容量: 6
入隊：10 --> true
頭指針: 2	尾指針: 3	隊列大小: 1	容量: 6

推薦閱讀

• 《 數組 》
• 《 稀疏數組 》
• 《 鏈表（單鏈表、雙鏈表、環形鏈表） 》
• 《 棧 》
• 《 隊列 》
• 《 樹 》
• 《 二叉樹 》
• 《 二叉查找樹（BST） 》
• 《 AVL樹（平衡二叉樹） 》
• 《 B樹 》
• 《 散列表（哈希表） 》