C++隊列

「隊列 queue」是一種遵循先入先出規(guī)則的線性數(shù)據(jù)結構。顧名思義，隊列模擬了排隊現(xiàn)象，即新來的人不斷加入隊列的尾部，而位于隊列頭部的人逐個離開。

如圖 5-4 所示，我們將隊列的頭部稱為“隊首”，尾部稱為“隊尾”，將把元素加入隊尾的操作稱為“入隊”，刪除隊首元素的操作稱為“出隊”。

圖 5-4   隊列的先入先出規(guī)則

隊列常用操作

隊列的常見操作如表 5-2 所示。需要注意的是，不同編程語言的方法名稱可能會有所不同。我們在此采用與棧相同的方法命名。

表 5-2   隊列操作效率

我們可以直接使用編程語言中現(xiàn)成的隊列類。

queue.cpp

/* 初始化隊列 */
queue<int> queue;

/* 元素入隊 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

/* 訪問隊首元素 */
int front = queue.front();

/* 元素出隊 */
queue.pop();

/* 獲取隊列的長度 */
int size = queue.size();

/* 判斷隊列是否為空 */
bool empty = queue.empty();

隊列實現(xiàn)

為了實現(xiàn)隊列，我們需要一種數(shù)據(jù)結構，可以在一端添加元素，并在另一端刪除元素。因此，鏈表和數(shù)組都可以用來實現(xiàn)隊列。

1.   基于鏈表的實現(xiàn)

如圖 5-5 所示，我們可以將鏈表的“頭節(jié)點”和“尾節(jié)點”分別視為“隊首”和“隊尾”，規(guī)定隊尾僅可添加節(jié)點，隊首僅可刪除節(jié)點。

圖 5-5   基于鏈表實現(xiàn)隊列的入隊出隊操作

以下是用鏈表實現(xiàn)隊列的代碼。

linkedlist_queue.cpp

/* 基于鏈表實現(xiàn)的隊列 */
class LinkedListQueue {
  private:
    ListNode *front, *rear; // 頭節(jié)點 front ，尾節(jié)點 rear
    int queSize;

  public:
    LinkedListQueue() {
        front = nullptr;
        rear = nullptr;
        queSize = 0;
    }

    ~LinkedListQueue() {
        // 遍歷鏈表刪除節(jié)點，釋放內(nèi)存
        freeMemoryLinkedList(front);
    }

    /* 獲取隊列的長度 */
    int size() {
        return queSize;
    }

    /* 判斷隊列是否為空 */
    bool isEmpty() {
        return queSize == 0;
    }

    /* 入隊 */
    void push(int num) {
        // 尾節(jié)點后添加 num
        ListNode *node = new ListNode(num);
        // 如果隊列為空，則令頭、尾節(jié)點都指向該節(jié)點
        if (front == nullptr) {
            front = node;
            rear = node;
        }
        // 如果隊列不為空，則將該節(jié)點添加到尾節(jié)點后
        else {
            rear->next = node;
            rear = node;
        }
        queSize++;
    }

    /* 出隊 */
    void pop() {
        int num = peek();
        // 刪除頭節(jié)點
        ListNode *tmp = front;
        front = front->next;
        // 釋放內(nèi)存
        delete tmp;
        queSize--;
    }

    /* 訪問隊首元素 */
    int peek() {
        if (size() == 0)
            throw out_of_range("隊列為空");
        return front->val;
    }

    /* 將鏈表轉化為 Vector 并返回 */
    vector<int> toVector() {
        ListNode *node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }
};

2.   基于數(shù)組的實現(xiàn)

由于數(shù)組刪除首元素的時間復雜度為 O(n) ，這會導致出隊操作效率較低。然而，我們可以采用以下巧妙方法來避免這個問題。

我們可以使用一個變量 front 指向隊首元素的索引，并維護一個變量 size 用于記錄隊列長度。定義 rear = front + size ，這個公式計算出的 rear 指向隊尾元素之后的下一個位置。

基于此設計，數(shù)組中包含元素的有效區(qū)間為 [front, rear - 1]，各種操作的實現(xiàn)方法如圖 5-6 所示。

• 入隊操作：將輸入元素賦值給 rear 索引處，并將 size 增加 1 。
• 出隊操作：只需將 front 增加 1 ，并將 size 減少 1 。

可以看到，入隊和出隊操作都只需進行一次操作，時間復雜度均為 O(1) 。

圖 5-6   基于數(shù)組實現(xiàn)隊列的入隊出隊操作

你可能會發(fā)現(xiàn)一個問題：在不斷進行入隊和出隊的過程中，front 和 rear 都在向右移動，當它們到達數(shù)組尾部時就無法繼續(xù)移動了。為解決此問題，我們可以將數(shù)組視為首尾相接的“環(huán)形數(shù)組”。

對于環(huán)形數(shù)組，我們需要讓 front 或 rear 在越過數(shù)組尾部時，直接回到數(shù)組頭部繼續(xù)遍歷。這種周期性規(guī)律可以通過“取余操作”來實現(xiàn)，代碼如下所示。

array_queue.cpp

/* 基于環(huán)形數(shù)組實現(xiàn)的隊列 */
class ArrayQueue {
  private:
    int *nums;       // 用于存儲隊列元素的數(shù)組
    int front;       // 隊首指針，指向隊首元素
    int queSize;     // 隊列長度
    int queCapacity; // 隊列容量

  public:
    ArrayQueue(int capacity) {
        // 初始化數(shù)組
        nums = new int[capacity];
        queCapacity = capacity;
        front = queSize = 0;
    }

    ~ArrayQueue() {
        delete[] nums;
    }

    /* 獲取隊列的容量 */
    int capacity() {
        return queCapacity;
    }

    /* 獲取隊列的長度 */
    int size() {
        return queSize;
    }

    /* 判斷隊列是否為空 */
    bool isEmpty() {
        return size() == 0;
    }

    /* 入隊 */
    void push(int num) {
        if (queSize == queCapacity) {
            cout << "隊列已滿" << endl;
            return;
        }
        // 計算隊尾指針，指向隊尾索引 + 1
        // 通過取余操作，實現(xiàn) rear 越過數(shù)組尾部后回到頭部
        int rear = (front + queSize) % queCapacity;
        // 將 num 添加至隊尾
        nums[rear] = num;
        queSize++;
    }

    /* 出隊 */
    void pop() {
        int num = peek();
        // 隊首指針向后移動一位，若越過尾部則返回到數(shù)組頭部
        front = (front + 1) % queCapacity;
        queSize--;
    }

    /* 訪問隊首元素 */
    int peek() {
        if (isEmpty())
            throw out_of_range("隊列為空");
        return nums[front];
    }

    /* 將數(shù)組轉化為 Vector 并返回 */
    vector<int> toVector() {
        // 僅轉換有效長度范圍內(nèi)的列表元素
        vector<int> arr(queSize);
        for (int i = 0, j = front; i < queSize; i++, j++) {
            arr[i] = nums[j % queCapacity];
        }
        return arr;
    }
};

以上實現(xiàn)的隊列仍然具有局限性，即其長度不可變。然而，這個問題不難解決，我們可以將數(shù)組替換為動態(tài)數(shù)組，從而引入擴容機制。有興趣的同學可以嘗試自行實現(xiàn)。

兩種實現(xiàn)的對比結論與棧一致，在此不再贅述。

隊列典型應用

• 淘寶訂單。購物者下單后，訂單將加入隊列中，系統(tǒng)隨后會根據(jù)順序依次處理隊列中的訂單。在雙十一期間，短時間內(nèi)會產(chǎn)生海量訂單，高并發(fā)成為工程師們需要重點攻克的問題。
• 各類待辦事項。任何需要實現(xiàn)“先來后到”功能的場景，例如打印機的任務隊列、餐廳的出餐隊列等。隊列在這些場景中可以有效地維護處理順序。