MK

Monday, 16 April, 2007

Circular Queue

Filed under: CIT Module A,CIT2008 — MK @ 19:10

一般情況下,queue 在電腦內部是用一連串 memory blocks 來實踐。如果最後一個 memory block 可以被當作是與第一個 memory block 連接起來,那麼這個 queue 就成為了一個 circular queue。

對於不清楚電腦內部運作的人來說,circular queue 運作起來的效果跟一般的 queue 無異。不過對於會考 CIT Module A 的同學來說,則必須要理解一下內部運作了。

Circular Queue 1

上圖中,淺藍色的就是扮演電腦內部的十個 memory blocks 被用作為 circular queue,普通電腦用戶是見不到的。我們不斷的 enqueue(排隊)和 dequeue(離隊),普通的人可以見到 queue 的運作是正常的(當然大前題下是要知道 queue 內最多只能有十個 items)。大家不妨留意一下 Front 和 Rear 的走勢。

Circular Queue 2

留意一下 Queue 還未滿時,但 Rear 已到了最後一個 memory block 時,enqueue 會發生什麼事︰

Circular Queue 3

此外,又看看當 Front 到了最後一個 memory block 時,而 queue 還未空時,Front 的走勢又是如何︰

Circular Queue 4

剩下來,要看看怎樣處理 queue 滿時要 enqueue 以及 queue 空時要 dequeue 的問題。

當 queue 滿時,留意一下 Front 和 Rear 的關係(當然,下圖並不是列舉了所有情況)︰

Circular Queue 5

當 queue 快要空時,要留意一下 Front 和 Rear 的關係,以及要留意一下會不會令到 empty 及 full 的情況會混淆。以下是一個我建議的解決方法︰

Circular Queue 6

3 Comments »

  1. I think it may be easier to determine whether the queue is empty or full by adding 2 members to the data structure. One is the queue capacity and the other is the current size. The logic becomes much simpler and one does not require to document the relationship between the front and rear pointers.

    Comment by Ricky Liu — Tuesday, 3 July, 2007 @ 18:08 | Reply

  2. 在 google search “Circular Queue” 第二個結果 =]

    Comment by whh — Sunday, 28 March, 2010 @ 11:08 | Reply

  3. 要用香港繁體中文版的 Google 才可以的吧? =.=”

    現在我把教學有關的東西放在更家合適的地方了。😛

    Comment by MK — Sunday, 28 March, 2010 @ 13:54 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.