伫列资料结构.PPTVIP

佇列與推疊 (Queue and Stack) 佇列（ Queue ）概念 佇列基本觀念 佇列是屬於線性串列，而加入的一端稱為後端（rear），刪除的那一端為前端（front）。 資料可以在後端新增，從前端刪除。兩端皆可進行資料的擷取。 佇列的實作需要保持前端與後端的追蹤，而堆疊只要維護頂端即可。 由於佇列具有先進先出（First In First Out，FIFO）的特性，因此也稱佇列為先進先出串列。 佇列前端 佇列後端 佇列新增作業 佇列刪除作業 佇列範例 佇列的加入與刪除（使用陣列） 佇列的操作行為是先進先出，我們可以假想在一陣列中有二端分別為front和rear端，每次加入都加在rear端，而刪除（即將被服務）的在front端。 一開始，佇列的front=-1，rear=-1，當加入一元素到佇列時，主要判斷rear是否會超過其陣列的最大容量。 佇列的加入與刪除（使用陣列） 當rear為MAX-1時，表示陣列已到達最大容量了，此時不能再加任何元素進來； 反之，則陣列未達最大容量，因此可以加入任何元素。以下是其片段程式 佇列的加入與刪除（使用陣列） 而刪除佇列的元素則需考慮佇列是空的情況，因為佇列為空時，表示沒有元素在佇列中，怎能刪除呢？當front = rear時，則表示佇列是空的，其片段程式如下： 佇列的加入與刪除（使用陣列） 上述的佇列是線性佇列（linear queue），表示的方式為Q(0: MAX-1)，但此線性佇列。 不太合理的現象就是當rear到達MAX-1時 無論如何的加入皆是不允許的，因為上述的加入片段程式會印出佇列是滿的訊息，因此它沒考慮佇列的前面是否還有空的位子。 環狀佇列（使用陣列） 為了解決此一問題，佇列常常以環狀佇列(circle queue)來表示之，CQ(0: MAX-1)，如下圖所示： 環狀佇列（使用陣列） 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述 rear=(rear+1) % MAX; 求出rear，主要的用意在於能夠使rear回到前面，看看是否還有空的位置可放。如當rear為MAX-1時，((MAX-1)+1)% MAX，其餘數為0，此時便可進入環狀佇列的前端了。 環狀佇列（使用陣列） 以下是 片段程式 環狀佇列（使用陣列） 環狀佇列的刪除，乃判斷front是否和rear同在一起，若是，則印出環狀佇列是滿的訊息， 否則，將front往前移，並加入元素，以下是其片段程式： 其中, front = (front+1) % MAX ; 佇列（使用鍊結串列 ） 如果是以鍊結串列來實作佇列，會使用表頭 (Head) 節點與資料節點等兩種結構。 資料結構，需要兩種不同的結構來實作佇列， 一個head結構。 資料節點。 建立佇列之後，佇列會有一個haed節點與0個或1個以上的資料節點。 佇列資料結構 （使用鍊結串列 ） 佇列（使用鍊結串列 ） 佇列（使用鍊結串列 ） 佇列的應用 假如所要解決的問題是有先進先出的性質時，則宜用佇列來解決，例如作業系統的工作安排（job scheduling），若不考慮特權（priority）的話。 舉凡銀行櫃台的服務、停車場的問題、大型計算機中心列印報表的情形，以及飛機起飛與降落等等的應用。 堆疊（Stack）觀念 堆疊是一種先進後出的資料結構，所有的新增與刪除都要在同一端進行，我們稱此端為頂端。 堆疊基本觀念 堆疊是一有序串列（order list），其加入（insert）和刪除（delete）動作都在同一端，此端通常稱之為頂端（top）。 加入一元素於堆疊，此動作稱為推入（push），與之相反的是從堆疊中刪除一元素；此動作稱為彈出（pop）。 由於堆疊具有先進去的元素最後才會被搬出來的特性，所以又稱堆疊是一種後進先出（Last In First Out，LIFO）串列。 堆疊和佇列比較 堆疊、佇列如圖3.1之(a)、(b)所示。 基本的堆疊作業 三個基本的堆疊操作是： 推入 (Push) 。 彈出 (Pop) 。 頂端元素(Stack Top)。 推入堆疊作業 推 入 (Push) 推入會在堆疊頂端加入一個項目，此項目即成為堆疊的頂端元素。 此作業只有一個要求，就是要有足夠的空間。 彈出堆疊作業 彈　出 (Pop) 當進行彈出作業時，將頂端的項目移除並傳回給使用者。 頂端元素操作 頂端元素 (Stack Top) 頂端元素就是拷貝頂端元素；但是未進行刪除。 堆疊實例 堆疊實例 堆疊的加入與刪除（使用陣列） 我們可以設定一陣列來表示堆疊，此堆疊是