Chap 3 堆疊與佇列 Stack and Queue.

Presentation on theme: "Chap 3 堆疊與佇列 Stack and Queue."— Presentation transcript:

1 Chap 3 堆疊與佇列 Stack and Queue

2 堆疊(Stack) 堆疊的定義：堆疊是一個有序串列，它的插入、刪除都在被稱為top的這端做。因此堆疊也被稱為後進先出 Last-In-First-Out (LIFO) list.

3 Stack (Cont.) 給定一個陣列 S = (a0, …, an-1), a0 為最底端的元素, an-1 為最頂端的元素, ai 位於 ai-1的上面, 0 < i < n. a3 a3 a2 a2 a1 a1 a0 a0 Push (Add) Pop (Delete)

4 系統堆疊 當一個函數被呼叫時， 程式會建立一個稱為活動記錄(activation record)或是堆疊框 (stack frame)的結構, 並且把它放在系統堆疊最上端. previous frame pointer fp return address a1 local variables previous frame pointer fp previous frame pointer return address main return address main

5 ADT 3.1 堆疊的抽象資料型態 Template <class KeyType> class Stack
{ // objects: A finite ordered list with zero or more elements public: Stack (int MaxStackSize = DefaultSize); // Create an empty stack whose maximum size is MaxStackSize Boolean IsFull(); // if number of elements in the stack is equal to the maximum size // of the stack, return TRUE(1) else return FALSE(0) void Add(const KeyType& item); // if IsFull(), then StackFull(); else insert item into the top of the stack. Boolean IsEmpty(); // if number of elements in the stack is 0, return TRUE(1) else return FALSE(0) KeyType* Delete(KeyType& ); // if IsEmpty(), then StackEmpty() and return 0; // else remove and return a pointer to the top element of the stack. };

6 利用陣列實現堆疊 an-1 a2 a1 a0 a0 a1 a2 an-1 Array index 1 2 3 n-1

7 佇列(Queue) 佇列是一個有序串列， 它的插入、 刪除發生在不同端。 加入新元素的那一端稱為後端(rear) ， 而刪除舊元素的那一端稱為前端(front). 它也被稱為 First-In-First-Out (FIFO) . a0 a1 a2 an-1 front rear

8 ADT 3.2 佇列的抽象資料型態 Template <class KeyType> class Queue {
// objects: A finite ordered list with zero or more elements public: Queue(int MaxQueueSize = DefaultSize); // Create an empty queue whose maximum size is MaxQueueSize Boolean IsFull(); // if number of elements in the queue is equal to the maximum size of // the queue, return TRUE(1); otherwise, return FALSE(0) void Add(const KeyType& item); // if IsFull(), then QueueFull(); else insert item at rear of the queue Boolean IsEmpty(); // if number of elements in the queue is equal to 0, return TRUE(1) // else return FALSE(0) KeyType* Delete(KeyType&); // if IsEmpty(), then QueueEmpty() and return 0; // else remove the item at the front of the queue and return a pointer to it };

9 佇列操作問題 一般使用陣列來實現佇列. 然而為了維持佇列空間上的充分利用, 在佇列上進行插入或刪除時必須對佇列內的元素進行移動. 在最差情形下其時間複雜度將達O(MaxSize).

10 佇列元素的變動 front rear front rear front rear

11 環狀佇列 為解決佇列中元素移動的問題, 在環狀佇列中當 rear == MaxSize – 1時指定下一個元素為q[0]
佇列的前端元素會依順時鐘方向會在指標 front 的後一個位置上. 問題：當 front = rear 時佇列是空的. 然而這條件亦適用於當佇列滿了的時候.

12 環狀佇列 4 4 n-4 n-4 3 3 n-3 n-3 2 2 n-2 n-2 1 1 n-1 n-1
J4 J3 n-4 n-4 3 3 J1 J2 n-3 n-3 J2 2 J1 2 J3 J4 n-2 n-2 1 1 n-1 n-1 front = 0; rear = 4 front = n-4; rear = 0

13 環狀佇列 判斷若 front == rear 時代表佇列為空的或滿的的方法之一為限制佇列中最多僅能儲存 MaxSize – 1個元素.
每一次當佇列中需要加入一個新的元素時, 會利用指標newrear 進行判斷. 若 newrear == front 時代表佇列滿了. 另一種解決方式為使用 flag 指標來記錄佇列上一次的運算. 此法的缺點為會降低 Add 與 Delete 函數的速度.

14 迷宮問題 Entrance Exit

15 移動方向 N [i-1][j-1] [i-1][j] [i-1][j+1] NE NW W [i][j-1] X [i][j+1] E
SW S SE

16 迷宮問題 通常解決迷宮問題時常用堆疊來儲存已走過之路徑的方向和座標. 使用另外一個 mxp 維度的陣列來記錄哪些位置已經走訪過.

17 運算式的計算 運算式中運算子的優先順序. Priority Operator 1 2 3 4 5 6 7 Unary minus, !
*, /, % 3 +, - 4 <, <=, >=, > 5 ==, != 6 && 7 ||

18 後置表示法(postfix notation)
在編譯過程中運算式必須先轉換成後置表示法，之後編譯器方能產生正確機械碼. X = A/B – C + D * E – A * C Infix A/B–C+D*E–A*C Postfix => AB/C-DE*+AC*- Operation Postfix T1 = A / B T1C-DE*+AC*- T2 = T1 - C T2 DE*+AC*- T3 = D * E T2T3+AC*- T4 = T2 + T3 T4AC*- T5 = A * C T4 T5 - T6 = T4 - T5 T6

19 後置表示法(postfix notation)的產生
X = A+ B* C / D – E * F 後置式: ABC*D/+EF*- 輸出 A A AB AB ABC ABC* ABC* ABC*D + + * + * + + / + / + 堆疊 輸出 ABC*D/ ABC*D/+ ABC*D/+E ABC*D/+E ABC*D/+EF + - - * - * - 堆疊

20 後置表示法(postfix notation)的產生
X = A+ (B+C*D) – E 後置式: ABCD*++E– 輸出 A A A AB AB ABC ABC ABCD ABCD* + ( + ( + + ( + ( * + ( * + ( + ( 堆疊 輸出 ABCD*+ ABCD*+ ABCD*++ ABCD*++E ABCD*++E- ( + + - - 堆疊

21 後置表示法(postfix notation)的運算
後置式: ABC*D/+EF*- A B A C B A B*C A D B*C A B*C/D A A+B*C/D 堆疊 E A+B*C/D F E A+B*C/D E*F A+B*C/D A+B*C/D-E*F

22 多堆疊與多佇列 兩個堆疊: 超過兩個堆疊 Stack A Stack B 1 2 3 4 m-4 m-3 m-2 m-1 m-1 b[0]
1 2 3 4 m-4 m-3 m-2 m-1 Stack A Stack B m-1 b[0] b[1] b[2] b[n] t[0] t[1] t[2] t[n]