stackk.PNG

什麼是Queue ?

Queue 就是 佇列

 

佇列 運作方式 就像 排隊

排隊的特性是:

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

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

 

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

就叫做:FIFO (First In First Out)

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

排隊,不正是這個樣子嗎?

queue.PNG

排隊,就是像這張圖一樣

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

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

stak.PNG

(push是放進,pop是提出)

 

 

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

會用到 front 和 rear 兩個值

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

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

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

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

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

看一下做法就知道了

stak2.PNG

(front的值一開始是-1)

 

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

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

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

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

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

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

挺花時間的

 

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

也就是如果後面排不進去,就從前面繼續排!

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

 

讓我們看看是概念是怎樣

 

circular_stack.PNG

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

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

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

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

這樣還是比較划算的

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

若 Stack 是 的,則
 front = rear

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

 

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

stak3.PNG


arrow
arrow
    全站熱搜

    finalfrank 發表在 痞客邦 留言(3) 人氣()