伫列(Queues).ppt

* * 7.1 佇列簡介 圖形的問題多且複雜，有時需要堆疊來處理問題，有時也需要佇列資料結構來解決問題，如最短路徑的搜尋。 第 7 章 佇列(Queues) 佇列(Queues)的基本概念是：先進先出 。 類比：銀行客服，或速食店的服務，顧客排成一列，都是先到的先服務。排成一列先進先出也就是佇列的特性。 佇列的資料結構：可以用來做為佇列的資料結構，基本上有兩種，一種是陣列，另一種是鏈結 (linked list)。 首先， 考慮以陣列來設計佇列的資料結構如下。 佇列的運算：佇列的運算有 InitializeQueue( ), IsQueueEmpty( ), IsQueueFull( ), Enqueue( ), Dequeue( )。 typedef struct { dataType a[MAXSIZE]; int front, rear;} queue; 其中 front 是指向陣列中儲存元素最前的一個，rear 指向陣列中儲存元素最後的一個。 如果陣列的 size 為 6，其中有2 個元素 x 與 y，front = 3 是指向陣列中儲存最前的一個元素 x，rear = 4 指向陣列中儲存元素最後的一個元素 y，如下左圖所示： x y 0 1 2 3 4 5 front rear 經過兩次 dequeue 之後，front = 5，rear = 4，此時陣列已經是 empty，如上右圖所示： x y 0 1 2 3 4 5 front rear 2 dequeues Queue 是 empty 的條件是 (rear + 1) mod MAXSIZE == front 陣列的 size 為 6，front = 3 是指向最前的元素 x，rear = 4 指向最後一個元素 y，如下左圖所示。將陣列視為一個 circular 情況，即第 5 個元素的下一個是第 0 個。 x y 0 1 2 3 4 5 front rear 經過4次 Eequeue，加入 a，b，c，d 之後，front = 3，rear = 2，此時陣列已經是 full，如上右圖所示： 4 Eequeues Queue 是 empty 的條件是 (rear + 1) mod MAXSIZE = front，當 queue 是 full 時，亦滿足相同的條件，即 empty 與 full 無法區別。因此，我們需要調整 full 的條件，即當陣列差一個就全滿時，就是 full 的條件：(rear + 2) mod MAXSIZE == front x y 0 1 2 3 4 5 front rear a b c d InitializeQueue ( ) : 將一 queue 的 front 設定為 0， rear 設為 -1。 其程式如下 : void InitializeQueue (queue *qp) { qp - front = 0; qp - rear = MAXSIZE – 1;// 或 -1 } IsQueueEmpty( ) : 檢查一個 queue 是否為空, 即檢查 front 是否等於 (rear+1) mod MAXSIZE。 其程式如下 : int IsQueueEmpty(queue q) { return (q.front == (q.rear+1) mod MAXSIZE); } IsQueueFull( ) : 檢查一個 queue 是否已滿, 即檢查 (rear +2) mod MAXSIZE 是否為 front。我們考慮的陣列是 circular 的情況。 其程式如下 : int IsQueueFull ( queue q ) { return ( (q.rear +2) mod MAXSIZE == q.front); } Enqueue( item ) : 將 item 置於 queue 的最後面。 其程式如下 : void Enqueue ( queue *qp, dataType item) { pq-rear = (pq-rear + 1) mod MAXSIZE; qp -a[ qp-rear ] = item; } Dequeue( ) :拿走 queue 的最前面的元素, 同時送回該值. 其程式如下 : dataType Deque ( queue *qp ) { dataType item; item = qp -a[ qp-front ]; qp-front = (qp-front + 1) mod MAXSIZE; return item; } 佇列的資料結構：鏈結 (linked list)