概念

如果有排隊吃拉麵的經驗，就會理解到一個隊伍一定是按照先來的人先進店吃的原則，這就是佇列（Queue）的基本概念，也稱為「先進先出」（First-In First-Out，簡稱FIFO）。

這個概念在軟體開發中經常被應用，例如軟體安裝、處理輸入測資、CPU工作排程等等。但通常佇列不會單獨存在，而是作為一種資料結構被使用。

實作

#include <bits/stdc++.h>
using namespace std;
int q[100100],l = 0,r = 0;
// 檢查是否還有元素存在 queue
bool isempty(){
    return l == r;
}
// 將元素插入 queue
void push(int num){
    q[r] = num;
    r++;
}
// 將最先放入的元素 pop 掉
void pop(){
    if(!isempty()){
        l++;
    }
}
// 回傳最前面的元素
int front(){
    if(!isempty()){
        return q[l];
    }
    return -1;
}
// 回傳 queue 的長度
int size(){
    return r - l;
}
// 清空 queue
void clear(){
    l = 0;
    r = 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    push(1); // q[] = {1}
    push(2); // q[] = {1,2}
    push(3); // q[] = {1,2,3}
    push(4); // q[] = {1,2,3,4}
    cout << size() << "\n"; // 4
    cout << front() << "\n"; // 1
    pop(); // q[] = {2,3,4}
    cout << size() << "\n"; // 3
    cout << front() << "\n"; // 2
    clear(); // q[] = {}
    cout << size() << "\n"; // 0
    cout << front() << "\n"; // -1
    return 0;
}

陣列實作的壞處

• 有限空間（受限於一開始分配的陣列大小）
• 可能浪費空間（一旦pop掉前面的元素，就無法再利用）

C++ STL 的 queue

事實上，C++已經提供了實作完善且能自動調整大小的STL（標準模板庫）queue。雖然設置過大的 queue 仍可能引發錯誤（Runtime Error，簡稱RE），但相對不會浪費過多空間。需要注意的是，如果 queue 為空時，呼叫 pop() 或 front() 等操作會導致 RE。此外，要使用 queue，必須包含 標頭檔。

STL 的 queue 的操作

• empty()
  • 回傳一個布林值，表示 queue 是否為空
• size()
  • 回傳一個無號整數，表示 queue 的長度
• front()
  • 回傳 queue 最前面的元素
• push()
  • 將元素放入 queue 的尾端
• pop()
  • 移除 queue 最前面的元素
• ...

除了上述操作，STL queue還有其他一些可用的操作，詳情請參考 cpp reference

#include <iostream>
#include <queue>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    q.push(2); // q = {2}
    q.push(5); // q = {2,5}
    q.push(12); // q = {2,5,12}
    q.push(25); // q = {2,5,12,25}
    cout << q.size() << "\n"; // 4
    cout << q.front() << "\n"; // 2
    q.pop(); // q = {5,12,25}
    cout << q.size() << "\n"; // 3
    cout << q.front() << "\n"; // 5
    cout << q.empty() << "\n"; // 0，代表 false
    return 0;
}

結論

在本文中，我們深入研究了佇列（Queue）的概念和實作方式。佇列遵循先進先出（FIFO）的原則，就像排隊吃拉麵一樣，先到的人先進店吃。

首先展示了如何使用 C++ 來手動實作一個佇列，包括插入元素、移除元素、查詢佇列的大小和清空佇列等操作。然而，我們也指出了這種方法的缺點，如受限於初始陣列大小和可能浪費空間的問題。

接著，我們介紹了 C++ STL（標準模板庫）中的 queue，這是一個已經實作好並且長度可以動態變化的佇列。我們展示了如何使用 STL 的 queue，並介紹了一些常用的操作，如檢查佇列是否為空、獲取佇列的大小、訪問佇列的最前面元素、插入元素和移除元素等。

總之，佇列是一個重要的資料結構，常常在軟體開發和演算法實作中使用。無論是手動實作還是使用 STL 的 queue，了解佇列的基本原理和操作都是極為重要的。這將有助於更有效地處理各種應用場景中的資料排列和處理需求。