摘要訊息 : 佇列是一個只能逐個在頭部移除元素或者在尾部插入元素的資料結構.
0. 前言
在《【資料結構】堆疊》中, 我們提到堆疊是只允許在尾部進行逐個插入和移除操作的資料結構. 同樣以雙向佇列為低層資料結構, 如果只允許在頭部逐個移除元素, 在尾部逐個插入元素, 那麼我們又得到了一個新的資料結構.
更新紀錄 :
- 2022 年 4 月 7 日進行第一次更新和修正.
1. 定義
定義 1. 設有不可尋坊的線性表 L_{\boldsymbol {\alpha}} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 若插入只能逐個在尾部進行, 而刪除元素只能逐個在頭部進行, 尋訪只能在頭部第一個元素和尾部最後一個元素進行, 那麼我們稱 L_{\boldsymbol {\alpha}} 為佇列 (queue).
佇列比起堆疊要稍微寬鬆一些, 雖然內部元素都是不可尋坊的. 在堆疊上我們只允許存取尾部最後一個元素, 而佇列允許存取頭部第一個元素和尾部最後一個元素. 這也是佇列的定義所決定的.
根據佇列的定義, 最先進入的元素是最先出來的, 最後進入的元素是最後才能出來的. 因此, 我們又稱佇列為先進先出 (first in first out, FIFO) 的資料結構.
在 C++ 中, std::queue 也是一個容器配接器, 它也是以 std::deque 為低層.
2. 插入和移除
據定義 1, 我們已經知道了向佇列插入元素只能在尾部進行, 移除元素只能在頭部進行, 而且一次只允許操作一個元素. 那麼, 插入和移除的時間複雜度是取決於低層資料結構在尾部插入和移除元素的時間複雜度 :
- 以向量作為低層資料結構 : 插入的時間複雜度為平攤 \Theta(1), 移除的時間複雜度為 \Theta(n);
- 以前項連結串列作為低層資料結構 : 插入的時間複雜度為 \Theta(n), 移除的時間複雜度為 \Theta(1);
- 以連結串列作為低層資料結構 : 插入的時間複雜度為 \Theta(1), 移除的時間複雜度為 \Theta(n);
- 以雙向佇列作為低層資料結構 : 插入的時間複雜度可以視為 \Theta(1) 的, 移除的時間複雜度也可以視為 \Theta(1) 的.
為什麼不以連結串列作為低層資料結構的原因是和堆疊是相同的, 這裡不再累贅.
和堆疊類似, 由於除了頭部第一個元素和尾部最後一個元素之外其它元素不可存取, 因此本來可以在線性結構上進行的搜尋, 字典比較和旋轉等演算法都不可以在佇列上進行.
3. 像素分割
如果閣下完全沒有圖像處理的經驗, 可以跳過本節.
我們知道, 電腦中的所有圖像都是一個一個像素點搭建起來的, 任意一幅圖像都是一個 m 行 n 列的像素矩陣. 若我們將像素限制為黑色 (0) 和白色 (255), 那麼整個像素矩陣中只有 0 和 255 這兩個數字, 此時我們稱這幅圖像為二值圖. 在 C++ 中, 我們可以使用布林型別來表示黑白兩色 : 黑色的布林值為 false, 白色的布林值為 true.
對於任意二值圖, 黑色或者白色的邊界可能把整幅圖像分割為若干個區域 :
在 Figure 1.1 中, 每一個框代表一個像素, 框裡面的顏色代表著像素值. 如果框內部被灰黑色 (這裡我沒有使用黑色的原因是黑色填充會導致邊框不可見) 填充, 則代表像素值為 0; 如果框內部是白色的, 那麼代表像素值為 255. 我們可以發現, 白色部分被分為了四個區域, 我們分別用其它顏色來表示這些不同區域 :
現在, 我們的任務是設法切割得到獨立的區域. 這個問題的基本思路是 :
- 逐行掃描圖像, 把所有沒有被標記白色像素的位置放入佇列中;
- 每次從佇列中取出一個像素, 如果這個像素被標記過了, 那麼略過這個像素; 否則檢查是否存在與其相鄰的白色像素, 做好相同的標記並放入佇列中;
- 在佇列為空的時候, 我們就找到了所有區域.
#include <queue>
#include <utility>
template <std::size_t Row, std::size_t Column>
void split(int (&arr)[Row][Column]) {
using position_type = std::pair<int, int>;
std::queue<position_type> q;
auto region {2};
for(auto row {0}; row < Row; ++row) {
for(auto col {0}; col < Column; ++col) {
if(arr[row][col] == 1) {
arr[row][col] = region++;
q.push({row, col});
while(not q.empty()) {
auto pos {q.front()};
/* 上 */
--pos.first;
if(pos.first >= 0 and arr[pos.first][pos.second] == 1) {
arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
q.push(pos);
}
/* 下 */
++++pos.first;
if(pos.first < Row and arr[pos.first][pos.second] == 1) {
arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
q.push(pos);
}
/* 左 */
--pos.first;
--pos.second;
if(pos.second >= 0 and arr[pos.first][pos.second] == 1) {
arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
q.push(pos);
}
/* 右 */
++++pos.second;
if(pos.second < Column and arr[pos.first][pos.second] == 1) {
arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
q.push(pos);
}
q.pop();
}
}
}
}
}對於 Figure 1.1, 主函式中的設定是這樣的 :
#include <iostream>
int main(int argc, char *argv[]) {
int arr[16][16] {};
for(auto i {0}; i < 16; ++i) {
for(auto j {0}; j < 16; ++j) {
arr[i][j] = 1;
}
}
arr[0][4] = arr[1][4] = arr[2][4] = arr[3][4] = arr[4][4] = 0;
arr[4][5] = arr[4][6] = arr[4][7] = arr[4][8] = arr[4][9] = arr[4][10] = 0;
arr[0][10] = arr[1][10] = arr[2][10] = arr[3][10] = 0;
for(auto i {0}; i < 16; ++i) {
arr[7][i] = 0;
}
arr[10][6] = arr[11][6] = arr[12][6] = arr[13][6] = arr[14][6] = arr[15][6] = 0;
arr[10][11] = arr[11][11] = arr[12][11] = arr[13][11] = arr[14][11] = arr[15][11] = 0;
arr[10][11] = arr[10][12] = arr[10][13] = arr[10][14] = arr[10][15] = 0;
split(arr);
for(auto i {0}; i < 16; ++i) {
for(auto j {0}; j < 16; ++j) {
std::cout << arr[i][j] << " ";
}
std::cout << std::endl;
}
}最終, 陣列 arr 的輸出是這樣的 :
對於任意圖像, 我們必定要尋訪每一個像素, 因此像素分割的時間複雜度為 \Theta(mn). 當圖像只有一個區域, 即圖像本身, 我們要將所有像素都放入佇列中, 此時的空間複雜度為 \Theta(mn).
4. 迴圈佇列 (循環佇列)
如果我們使用陣列 (這裡的陣列可以是固定大小, 也可以是動態大小的向量) 作為佇列的低層資料結構, 又希望在頭部移除元素的時候, 時間複雜度可以降到 \Theta(1), 我們就需要對陣列進行一些優化. 優化點就在於當佇列頭部的元素被移除的時候, 我們是否可以放棄將剩餘元素往前面移動一個位置的做法, 而改用其它方法.
現在建立兩個指向型標記, 一個指向佇列的頭部, 一個指向佇列的尾部. 如果佇列頭部的元素被移除了, 那麼只需要讓頭部的指向型標記重新指向接下來的元素即可. 如果佇列在尾部增加了一個元素, 只需要讓尾部的指向型標記指向下一個空位即可.
為了利用全部空間, 當指向佇列尾部的指向型標記超出陣列範圍的時候 (例如在 Figure 3 中再插入一個元素), 我們將這個指向型標記重新指向陣列的頭部 :
我們稱這樣的佇列為迴圈佇列 (circular queue, 也稱為循環佇列).
現在, 我們繼續向 Figure 4 的佇列中插入兩個元素, 使得兩個指向型標記相遇 :
或者不斷從 Figure 4 的佇列中移除元素, 使得兩個指向型標記相遇 :
那麼現在的問題就是, 如果兩個指向型標記相遇的話, 怎麼判斷佇列到底是空的還是滿的呢? 要解決這個問題, 有兩個方案 :
- 我們讓迴圈佇列的實際元素數量比預期多一個, 但是這一個位置永遠都是空著的. 因此, 對於迴圈佇列的使用者來說, 大小還是和原來一樣. 讓這個位置永遠為空的原因就是我們以兩個指向型標記相遇作為判定迴圈佇列為空的條件. 一開始, 我們讓指向頭部的指向型標記和指向尾部的指向型標記共同指向佇列的頭部. 不斷插入元素之後, 如果指向尾部的指向型標記向後移動一個位置就可以遇到指向頭部的指向型標記的時候, 我們就判定這個迴圈佇列已經滿了, 此時再想要插入元素只能擴充陣列. 如果不斷移除元素, 兩個指向型標記又可以相遇, 此時我們可以判斷佇列為空;
- 我們也可以設定一個標記 t. 一開始, 我們同樣讓指向頭部的指向型標記和指向尾部的指向型標記共同指向佇列的頭部. 插入元素的過程中, 一旦兩個指向型標記相遇, 那麼就令 t = 1, 說明佇列已經滿了. 移除元素的過程中, 如果兩個指向型標記相遇, 那麼就令 t = 0, 說明佇列為空. 剛開始, 我們令 t = 0. 在這種方案下, 判斷佇列是否為滿的條件是兩個指向型標記是否相遇以及 t 是否為 1; 判斷佇列是否為空的條件是兩個指向型標記是否相遇以及 t 是否為 0.
至於這兩個方案應該如何選擇, 應該看佇列中儲存的型別. 如果型別對應的物件在空間中佔了很多位置 (在 C++ 中可以表示為 sizeof(T) 遠大於 sizeof(bool)), 那麼我們就可以使用標記的方法; 否則可以讓佇列多出一個元素空間.
5. 實作
我自己用 C++ 實作了佇列 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/queue.hpp, 大家可以參考後自行實作.
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :
