廣告贊助

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


創作者介紹

Frank's 資訊科技潮流站

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


留言列表 (3)

發表留言
  • jwxie
  • circular queue

    但如果 次序要保留, 那麼 還不是一樣要全部移動?

    假如 front <---> rear排序是 18 29 40 55
    我將40除掉
    那麼 18和29也不是都要往前移嗎?
    如果後面排不前進, 而直接用40空出來的格再填一個, 次序就不能保留
    18 29 32 55

    對吧?

    queue也可以吧? 如果不保留次序, 那麼只有 40空出來, 填進去不一是都一樣嗎?
    請指教一下
  • Queue是FIFO (First in first out)
    就像你在排隊的時候,只有在最前面的人可以離開隊伍 (表示他排到了!)
    如果有人要加進來,也只能加在最後面 (不然就是插隊!)

    您舉的例子中
    40既然不是在最前面,他當然就不能離開隊伍 (因為還沒排到嘛!)
    因為Queue一定是最前面的人才能離開隊伍,所以不會有您說的40除掉的問題發生

    (請將它想像成不會漏水的水管,40的前面和後面既然都有水滴,那他怎麼能離開水管咧~)

    如有疑問 歡迎再討論喔

    finalfrank 於 2010/09/28 01:07 回覆

  • jwxie
  • 感謝指教. 剛來想一下, 既然是cylic..所以不管永遠都不會有次序的問題. 因為 一旦pop了, rear便會自動前進.
    剛寫了一下, 沒問題啦
    謝謝你的熱心回應
  • 嗯嗯

    finalfrank 於 2010/09/28 10:55 回覆

  • 訪客


  • An operating system can have several queue. The ____ queue holds the processes that are in memory,ready to run and waiting for the CPU.
    可以麻煩你幫我解答這題嗎@@


找更多相關文章與討論