Circular Queue

一般情況下,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

Advertisements

3 thoughts on “Circular Queue

  1. Ricky Liu

    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.

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