Frank's 資訊科技潮流站

什麼是Queue ?

Queue 就是 佇列

 

佇列 運作方式 就像 排隊

排隊的特性是：

1. 先來排的，先排到 (而且從隊伍中消失)

2. 新來的人，會加在隊伍的最後面

 

佇列 運作方式 有一種術語形容

就叫做：FIFO (First In First Out)

也就是，先進來的，會先出去

排隊，不正是這個樣子嗎？

排隊，就是像這張圖一樣

而我們的Queue也是這樣運作的

讓我們來看看「理論上」一個可以容納八個人的Queue是怎麼樣的概念

(push是放進，pop是提出)

 

 

但是程式實際上是怎麼運作的呢？

會用到 front 和 rear 兩個值

其中 front 表示 最前面值位置 -1

而 rear 表示 最後一個值的位置

值得注意的是，為了執行的效率，

所以pop的時候，只是移動front的值而已，沒有每次都把整個stack往前移！

只有在滿的時候才會往前移

看一下做法就知道了

(front的值一開始是-1)

 

這樣看起來似乎已經是個不錯的方法

但是，在這個只有8個空間的Queue看起來還好

但是要修補位置，就要把元素一個一個移到最前方

你的Queue有多大，你要修補的元素就越多

雖然即使上面這個Queue全滿，全部元素往前修補，最多也只需要8個步驟

但是如果你的Queue有100這麼大，那全部往前修補需要100個步驟！

挺花時間的

 

因此我們用一點技巧，就是讓這個Queue變成可循環的！  (Circular Queue)

也就是如果後面排不進去，就從前面繼續排！

這樣就可以省去剛剛那個「修補」的動作！

 

讓我們看看是概念是怎樣

 

因為front = rear 代表「Queue是空的」

所以只要有Queue有值，front那格應該永遠是空白的  (詳見最上面兩個情況的比較)

因此得知這個方法的缺點是，填滿 = 最大格數 -1

不過，雖然這樣犧牲一格空間，我們卻省了很多修補移動的時間

這樣還是比較划算的

從上面那張圖我們得到的結論是

若 Stack 是 空 的，則
 front = rear

若 Stack 是 滿 的，則
1. front = rear + 1           //那 rear = front + 1 是什麼情況??
2. front = min  &  rear = max

 

瞭解了之後，讓我們來看看實際上是怎麼運作的