HackMD
Python 及 C++ 佇列 (queue)
作者：王一哲
日期：2023年8月3日
前言
佇列 (queue) 是一種 先進先出 (the first in is the first out, FIFO) 的資料格式，只能從最後面填入資料，從最前面取出資料，無法從佇列中間存取資料，以下是在 Python 及 C++ 的實作方法。
Python 方法1：引入 queue 函式庫中的 Queue
要先引入函式庫，函式庫的官方說明書在此 queue — A synchronized queue class。
from queue import Queue
建立佇列
語法為
佇列名稱 = Queue(maxsize=長度)
maxsize 可以不加，預設值為 0；如果有設定 maxsize，當佇列已滿且要填入新資料時，會回傳錯誤訊息 Full。以下的程式碼會建立名稱為 q、maxsize 為3的佇列。
q = Queue(maxsize=3)
填入資料
語法為
佇列名稱.put(資料, block=布林, timeout=秒數)
block 可以不加，預設值為 True。timeout 可以不加，預設值為 None。
- 如果 block=True，當佇列已滿且要填入新資料時，會先等待一段時間，當佇列有空間時再填入資料，或是到達 timeout 設定的秒數時回傳錯誤訊息 Full，但如果沒有設定 timeout，程式就會停在這一行，不會執行後面的程式碼。
- 如果 block=False，當佇列已滿且要填入新資料時，立刻回傳錯誤訊息 Full。
延續前面的程式碼，可以試試看第5、6行程式碼執行時的差異。
q = Queue(maxsize=3)
q.put(0) # q 的內容為 [0]
q.put(1) # q 的內容為 [0, 1]
q.put(2) # q 的內容為 [0, 1, 2] 且已填滿
q.put(3, block=True, timeout=1) # 等待 1 秒後回傳錯誤訊息 Full
#q.put(3, block=False) # 立刻回傳錯誤訊息 Full
檢查佇列是否為空
語法為
佇列名稱.empty()
不需要加上任何參數，如果佇列是空的回傳 True，如果佇列中有資料回傳 Fasle。
檢查佇列是否填滿
語法為
佇列名稱.full()
不需要加上任何參數，如果佇列已填滿回傳 True，如果佇列還有空間回傳 Fasle。
取得佇列長度
語法為
佇列名稱.qsize()
不需要加上任何參數，回傳佇列長度，格式為 int。
取得佇列最前面的資料
回傳並移除佇列最前面的資料，語法為
佇列名稱.get(block=布林, timeout=秒數)
block 可以不加，預設值為 True。timeout 可以不加，預設值為 None。
- 如果 block=True，當佇列中已無資料且要取出資料時，會先等待一段時間，當佇列中有資料時再取出資料，或是到達 timeout 設定的秒數時回傳錯誤訊息 Empty，但如果沒有設定 timeout，程式就會停在這一行，不會執行後面的程式碼。
- 如果 block=False，當佇列中已無資料且要取出資料時，立刻回傳錯誤訊息 Empty。
例如以下的程式碼，可以試試看第2、3行程式碼執行時的差異。
q = Queue()
q.get(block=True, timeout=1) # 等待 1 秒後回傳錯誤訊息 Empty
#q.get(block=False) # 立刻回傳錯誤訊息 Empty
由佇列取出所有資料
這是很常用的技巧，假設佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常會這樣寫
while not q.empty(): # 當佇列中還有資料時繼續執行 while 迴圈
n = q.get() # 回傳並移除佇列最前面的資料，回傳的資料指定給變數 n
Python 方法2：使用串列 (list)
關於串列的基本操作請看這篇〈串列〉，以下是把串列當作佇列的方法。
建立空的串列
語法為
串列名稱 = []
填入資料
語法為
串列名稱.append(資料)
檢查串列長度
語法為
len(串列名稱)
如串列是空的，長度為 0，
取得串列最前面的資料
回傳並移除串列最前面的資料，語法為
串列名稱.pop(0)
參數為索引值，預設值為 -1，也就是最後一筆資料。其實 pop 可以回傳串列中任何索引值的資料，在此是為了配合佇列的操作方式，而將索引值設定為 0。
由串列取出所有資料
為了配合佇列的操作方式，假設串列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常會這樣寫
while q: # 當串列中還有資料時繼續執行 while 迴圈
n = q.pop(0) # 回傳並移除串列最前面的資料，回傳的資料指定給變數 n
C++ STL queue 函式庫
要先引入函式庫，函式庫的官方說明書在此 cplusplus.com std::queue。
#include <queue>
建立佇列
語法為
queue<資料格式> 佇列名稱;
可以使用所有內建的資料格式，例如 int、float、string，甚至也可以使用自訂的資料格式。
填入資料
語法為
佇列名稱.push(資料);
例如
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(0); // q 的內容為 [0]
q.push(1); // q 的內容為 [0, 1]
q.push(2); // q 的內容為 [0, 1, 2]
return 0;
}
呼叫已定義的建構子處理資料後再填入
看起來功能和 push 很像，官方說明書在此std::queue::emplace，push 與 emplace 的差異請看 Difference between <queue>'s emplace and push。語法為
佇列名稱.emplace(資料);
檢查佇列是否為空
語法為
佇列名稱.empty();
不需要加上任何參數，如果佇列是空的回傳 1，如果佇列中有資料回傳 0。
取得佇列長度
語法為
佇列名稱.size();
不需要加上任何參數，回傳佇列長度，格式為 size_t，沒有正負號的整數。
取得佇列最前面的資料
回傳佇列最前面的資料，語法為
佇列名稱.front();
移除佇列最前面的資料
移除佇列最前面的資料，語法為
佇列名稱.pop();
取得佇列最後面的資料
回傳佇列最後面的資料，語法為
佇列名稱.back();
交換兩個佇列的資料
語法為
佇列1.swap(佇列2);
由佇列取出所有資料
這是很常用的技巧，假設佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常會這樣寫
while(!q.empty()) { // 當佇列中還有資料時繼續執行 while 迴圈
int n = q.front(); // 回傳佇列最前面的資料並指定給變數 n
q.pop(); // 移除佇列最前面的資料
}
結語
以上是我目前常用到的佇列功能，如果之後有遇到其它需求會再補充內容。
參考資料
- Python 3.11.4 queue — A synchronized queue class
- cplusplus.com std::queue
- Difference between <queue>'s emplace and push
