C++隊(duì)列

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

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

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

隊(duì)列常用操作

隊(duì)列的常見(jiàn)操作如表 5-2 所示。需要注意的是，不同編程語(yǔ)言的方法名稱可能會(huì)有所不同。我們?cè)诖瞬捎门c棧相同的方法命名。

表 5-2   隊(duì)列操作效率

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

queue.cpp

/* 初始化隊(duì)列 */
queue<int> queue;

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

/* 訪問(wèn)隊(duì)首元素 */
int front = queue.front();

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

/* 獲取隊(duì)列的長(zhǎng)度 */
int size = queue.size();

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

隊(duì)列實(shí)現(xiàn)

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

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

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

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

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

linkedlist_queue.cpp

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

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

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

    /* 獲取隊(duì)列的長(zhǎng)度 */
    int size() {
        return queSize;
    }

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

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

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

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

    /* 將鏈表轉(zhuǎn)化為 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ù)組的實(shí)現(xiàn)

由于數(shù)組刪除首元素的時(shí)間復(fù)雜度為 O(n) ，這會(huì)導(dǎo)致出隊(duì)操作效率較低。然而，我們可以采用以下巧妙方法來(lái)避免這個(gè)問(wèn)題。

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

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

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

可以看到，入隊(duì)和出隊(duì)操作都只需進(jìn)行一次操作，時(shí)間復(fù)雜度均為 O(1) 。

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

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

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

array_queue.cpp

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

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

    ~ArrayQueue() {
        delete[] nums;
    }

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

    /* 獲取隊(duì)列的長(zhǎng)度 */
    int size() {
        return queSize;
    }

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

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

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

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

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

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

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

隊(duì)列典型應(yīng)用

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