Chap2 Stack & Queue.

Presentation on theme: "Chap2 Stack & Queue."— Presentation transcript:

1 Chap2 Stack & Queue

2 Stack 堆疊（Stack） 採用後插入者先刪除(LIFO, Last In First Out)的規則
資料插入和刪除的動作只發生在堆疊的頂端（Top） Stack結構 自助餐廳裡餐盤由桌面往上一個一個疊放的方式就是一個

3 Stack基本運作 1. 產生堆疊結構 2.將資料放入堆疊（Push）
利用程式語言的宣告（Declaration）指令，將堆疊宣告成陣列（假設陣列之大小為  N  並且資料從第  0  個索引開始存放）或鏈結串列(Linked List) 結構。 2.將資料放入堆疊（Push） 更改  Top  指標後，將資料存入堆疊，但必須 先判斷堆疊是否已滿（使用陣列時） 。

4 Stack基本運作 3.刪除資料（Pop）: 4.判斷堆疊是否滿溢： 5.判斷堆疊是否是空的：
若堆疊不是空的，則將頂端資料取出，並更改  Top  指標值。 4.判斷堆疊是否滿溢： 判斷  Top  指標是否等於  N ━  1？（使用陣列時）。 5.判斷堆疊是否是空的： Top  值小於  0  （陣列） 或  Top  指向 NULL （鏈結串列）。

5 Stack的應用 副程式的呼叫(Subroutine Call)
用Stack儲存Return Address(即呼叫副程式的下一行指令的位址) 將算式運算式從中序表示式(infix)轉換為後序(postfix)或前序(prefix)表示式 A*B/C (infix)  AB*C/ (postfix)

6 Queue 佇列（Queue） 採先插入者先刪除(FIFO , First In First Out)規則
資料的插入刪除分別發生在佇列的兩端， 插入的一端稱為尾端（Rear） 刪除的一端稱為前（首）端（Front） 常見的佇列 搭公車時大排長龍準備上車時 買票的人隊伍 高速公路收費站前大排長龍等待繳費的車陣

7 Queue 佇列的表示法 陣列是屬於循序配置(Sequential Allocation)
鏈結串列則是屬於動態配置( Dynamic Allocation）

8 Queue基本運作 1.產生佇列結構： 2.將資料加入佇列： 3.從佇列刪除一個元素：
宣告一個陣列結構或鏈結串列結構，並設定成空佇列，即Front = Rear = -1  或  Front = Rear = NULL(=0)。 2.將資料加入佇列： 若佇列未滿溢，則改變Rear指標後將資料存入佇列之Rear位置。 3.從佇列刪除一個元素： 若非空佇列，則改變 Front 指標後將  Front  所指到之佇列元素刪除。

9 Queue基本運作 4.判斷佇列是否滿溢： 5.判斷是否為空佇列：
當  Rear = N-1 時，表示佇列滿溢(Overflow)。（假設陣列之大小為 N ，並且資料從第 0 個索引開始存放） 5.判斷是否為空佇列： 當  Front = Rear 時，為空佇列。

10 3種常見的變形佇列 環狀佇列（Circular Queue） 優先佇列（Priority Queue）
每一個佇列中的元素，我們都賦予一個代表優先權的數字，最大的數字就有最高的優先權。 應用 CPU 的工作排程(Job Schedule, Task Schedule) 作為輸出入工作緩衝區： SPOOLING，是先將輸入資料寫在磁碟上，再輸入電腦處理，處理 後的資料先寫在磁碟上，再由印表機印出。 用於電腦模擬（Computer  Simulation）方面 在模擬中經常有時間導向（time - driven）或事件導向（event - driven）的輸入訊號，由於訊號到達的時間不一定，也是用佇列來安排。 雙向佇列（Double  Ended  Queue）