我們昨天看了Stack的實作，今天要來學習佇(ㄓㄨˋ)列吧!

什麼是佇列(Queue)?

佇列(Queue)與堆疊(Stack)都是一種有序串列，並且是抽象資料型態(ADT)，具有先進先出(First in First out, FIFO)的特性

常見的生活例子有 :

• 排隊 : 最先到的人會最先被服務，而最後到的人則需要排在隊伍尾端等待
• 羽球桶 : 先放進去的球會先被拿出來

Queue 常見操作

佇列宣告

queue<int> q;

enqueue

q.push(10);
q.push(20);
q.push(30);

dequeue

q.pop();

原本的 10 被移除

C++ STL(標準模板庫) Queue

#include<queue>

#include <iostream> 
#include <queue> 
using namespace std; 
int main() { 
    queue<int> q; 
    q.push(10); 
    q.push(20); 
    q.push(30); 
    cout << q.front() << endl; 
    cout << q.back() << endl; 
    q.pop(); 
    cout << q.front() << endl; 
    return 0; 
}

輸出:
10
30
20

用串列實作佇列

#include <iostream>

using namespace std;
struct Node{
    int data;
    Node *next;
    Node(int x):data(x),next(nullptr) {}
};
Node* front = nullptr;
Node* rear = nullptr;

void enqueue(int value) {
    Node* newNode = new Node(value);
    if (front == nullptr) {       // 空佇列,新節點同時是 front 也是 rear
        front = rear = newNode;
        return;
    }
    rear->next = newNode;         // 接在原本 rear 後面
    rear = newNode;               // rear 更新成新節點
}

int dequeue() {
    if (front == nullptr) {
        cout << "Queue is empty" << endl;
        return -1;
    }
    Node* temp = front;
    int value = temp->data;
    front = front->next;          // front 往後移一格

    if (front == nullptr) {       // 如果移除後串列空了,rear 也要清空
        rear = nullptr;
    }

    delete temp;
    return value;
}

int main(){
    
    enqueue(10);
    enqueue(20);
    enqueue(30);

    cout << dequeue() << endl;  
    cout << dequeue() << endl;  

    return 0;
}

思考步驟 :

最開始

Node* front = nullptr;
Node* rear = nullptr;

Queue是空的

建立：enqueue(10)

Node* newNode = new Node(10);

進入：if(front == nullptr)

    if (front == nullptr) {   
        front = rear = newNode;
        return;
    }

建立：enqueue(20)

Node* newNode = new Node(20);

注意這個新節點目前是獨立的,還沒有跟前面的 [10] 接起來
這時候front指向10，不是nullptr所以 if 不成立
所以執行

rear->next = newNode;

(rare還沒更新)

rear = newNode;

enqueue(30)，以此類推

rear->next = newNode;

rear = newNode;

開始 dequeue()

Node* temp = front;

兩個指標都指向 10

接著

front = front->next;

front的next是20，所以front=20

delete temp;

cout << dequeue() << endl;

輸出 10

後面以此類推~

時間複雜度

那明天我們會繼續來看Queue的其他應用，加油!

參考資料和書籍

1. 圖解資料結構×演算法:運用C++ 胡昭明
2. https://vocus.cc/article/67ea78b9fd89780001a595de
3. https://hackmd.io/@Aquamay/S1eTd_LcO