同樣是從雙向佇列中, 我們了解到佇列的基本性質. 佇列中的元素操作, 限制和堆疊差不多. 只不過, 堆疊中是只能在最後一個位置進行插入或者彈出, 而佇列是從最後一個元素插入, 從第一個位置彈出. 也就是說, 佇列只允許最後一個位置進行插入, 並且只允許在一個位置進行彈出. 因此, 佇列中的元素, 先進去的肯定先出來, 後進去的肯定後出來

我們通過一張 SVG 圖像來看一下佇列的結構 :

當有元素需要進入佇列的時候, 直接被安放在 last 內, 並且同時 last 會向後移動; 當佇列中有元素想要彈出的時候, 將第一個元素之後的所有元素向前移動一個位置即可

相對於堆疊來說, 佇列的性質要比堆疊稍難, 但是它也是屬於較為簡單的線性結構了

和堆疊一樣, 也是因為佇列的嚴格限制, 在 STL 中, 佇列也是一種容器配接器. 儘管佇列可以訪問第一個元素, 也可以訪問最後一個元素, 但是中間的元素是不可以訪問的. 因此, 佇列中存在的疊代器的意義也同樣是不太大

此時, 你可能又有疑問了, 每次彈出的時候, 都需要將元素從後往前複製 (移動) 一個位置, 這樣是不是太消耗時間了? 答案當然是沒錯, 儘管 C++ 11 引入了移動, 儘管移動通常來說要比複製來得快, 但是這並不代表著移動不消耗性能. 因此, 我們需要一個更好的方法來優化佇列, 此時, 就有了「迴圈佇列」 (循環佇列)

我們需要看一下迴圈佇列的基本結構 :

我們可以發現迴圈佇列中多了一個 first 指標, 它一直指向迴圈佇列中的第一個元素. 因此, first 肯定是一個可以移動的指標

迴圈佇列中迴圈的意義和雙向連結串列中的迴圈的意義是完全不同的. 雙向連結串列中迴圈的意義是當疊代器走向最後一個元素, 再對疊代器進行自遞增, 疊代器會回到第一個元素從而構成一個迴圈. 但是迴圈佇列中的迴圈意義是每一次彈出都不需要複製, 而只是移動 first, 然後對之前的位置中的元素進行解構就可以了. 當兩個指標中任何一個到達迴圈佇列記憶體地址範圍之外時, 自動回到第一個. 這就是迴圈佇列中迴圈的意義

了解了迴圈佇列中的基本結構, 我們還需要迴圈佇列中存在另外兩種特殊的情況 - 就是迴圈佇列可能會出現假空以及假滿的現象

首先我們來討論為什麼會出現迴圈佇列的假空現象或者假滿現象 :

我們需要判斷一個佇列是否已滿或者為空, 需要一個條件. 在具有兩個指標的迴圈佇列中, 我們很自然就認為當頭部的疊代器 (這裡是指標) 和尾後疊代器相遇的時候, 佇列是空的或者是滿的. 在之前的 SVG 圖像中, 我們設定了 first 為頭部疊代器, last 為尾後疊代器. 那麼判斷佇列為空或者已滿的條件即是 first == last. 但是這個條件只能判定一個條件, 那麼我們設定它用於判斷佇列是否為空好了. 那麼佇列是否已滿的條件怎麼辦呢? 我們使用 last 是否為最後一個指標來判定

但是從在其中一種情況, 我們可以看到下面的 SVG 圖像 :

圖像中的迴圈佇列中, 充滿了元素, 我們很容易判斷這個迴圈佇列是滿的. 但是根據我們之前的判定條件 first == last, 那麼電腦就會判定這個迴圈佇列又是空的. 儘管電腦會判定這個迴圈佇列為空, 但是實際上, 這個迴圈佇列中充滿了元素, 已經容不下任何其他新元素了, 這個迴圈佇列是滿的. 這裡就出現了迴圈佇列的其中一個問題 : 迴圈佇列的假空問題

我們再來看看另外一種情況 :

圖像中的迴圈佇列, 在 first 之前有兩個空位, 很明顯我們可以判定這個迴圈佇列是有空位的. 但是根據我們之前的判定條件 last 是否指向迴圈佇列的最後一個元素, 那麼電腦又會判定這個迴圈佇列是滿的. 但是實際上這個迴圈佇列的空位足以容下兩個新的元素, 這個迴圈佇列並不是滿的. 這裡就出現了另外一個迴圈佇列的問題 : 迴圈佇列的假滿問題

要解決這個問題, 有兩個方案 :

  • 我們讓迴圈佇列的實際元素個數比預期一個, 但是這一個永遠都是空著的. 因此, 對於迴圈佇列的使用者來說, 大小還是和原來一樣. 讓這個位置永遠為空的原因就是, 我們以 first == last 作為判定迴圈佇列為空的條件, 但是 first 不可以追上 last. 否則就會出現 ambiguous. 當 last + 1 == first 的時候, 我們就判定這個迴圈佇列已經滿了, 此時再想要插入元素, 只能擲出例外情況了. 在這種方案下, 迴圈佇列判定為空的條件是 last == first; 迴圈佇列判定為滿的條件是 last + 1 == first
  • 我們在迴圈佇列的類別中設定一個標誌 tag, 我們同樣以 first == last 作為迴圈佇列判定空或者滿的條件. 為什麼這個時候 first == last 既可以判定迴圈佇列是否為空也可以判定迴圈佇列是否為滿呢? 因為當迴圈佇列為空的時候, first == last 成立並且標誌 tagfalse, 代表著我們可以向迴圈佇列中插入元素, 迴圈佇列中還有空的位置. 當迴圈佇列滿的時候, first == last 成立並且 標誌 tagtrue , 代表著我們不可以再向迴圈佇列中插入新元素了, 迴圈佇列已經滿了, 如果還要插入那就只能擲出例外情況了. 在這種方案下, 迴圈佇列判定為空的條件為 first == last && tag == false, 迴圈佇列判定為滿的條件為 first == last && tag == false

此時, first 或者 last 疊代器任何一個超出了迴圈佇列的範圍, 我們立馬讓其回到第一個的位置

至此為止, 我們已經完美地解決了迴圈佇列中的假空或者假滿的問題了

對於佇列、迴圈佇列的實作方式, 我還是比較傾向於樣板特製化. 與 Stack 相同, 指定 Queue 中的容器為型別對應的指標, 就相當於使用指標陣列作為容器, 實現佇列

資料結構 Queue : GitHub 點擊直達

資料結構 Queue 使用說明 : GitHub 點擊直達