Chap 3 堆疊與佇列 Stack and Queue

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

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)

系統堆疊 當一個函數被呼叫時， 程式會建立一個稱為活動記錄(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

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. };

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

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

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 };

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

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

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

環狀佇列 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

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

迷宮問題 Entrance Exit

移動方向 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

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

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

後置表示法(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

後置表示法(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 + - - * - * - 堆疊

後置表示法(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- ( + + - - 堆疊

後置表示法(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

多堆疊與多佇列 兩個堆疊: 超過兩個堆疊 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]