4. 堆疊與佇列 (Stack and Queue) 4. Stak (). 基本觀念 定義 : 當將東西疊成一堆, 而取用的時候由上方來取出 特性 : 先進後出, 後進先出 ( 號球先放, 但 3 號球會先拿出 ) 2 3 3 2 (2). Stack 的運算 基本運算 push: 將資料放入堆疊 pop: 將資料由堆疊最頂端取出一個 TopItem: 位於堆疊中最上面的一個資料 IsEmpty: 用來檢查目前堆疊是否為空 IsFull: 用來檢查目前堆疊是否已經滿了 push IsFull pop Stack 的實作 : 堆疊的宣告 int Item[5]; IsEmpty // 宣告一個堆疊共有 5 個位置 TopItem 37
放入資料 push(); push(); push(c); 取出資料 x = pop(); // C x2 = pop(); // 放入資料 push(d); 範例 : 執行下面指令後, 請填入堆疊的狀態 int Item[3]; () push(); (2) push(); (3) push(c); (4) push(d); (5) x = pop(); (6) x2 = pop(); (7) x3 = pop(); (8) x4 = pop(); (9) push(e); (0) x5 = pop(); () push(f); (2) push(g); 38
X = X2 = X3 = X4 = X5 = ns: X = C X2 = X3 = X4 = 0 X5 = E () (2) (3) (4) C C (5) (6) (7) (8) (9) (0) () (2) G E F F 範例 : 用鏈結串列實作堆疊原始的堆疊為 50,2,0 執行 push(2) 的指令 執行 pop() 的指令 x 50 2 2 () 將 2 的鏈結指向 50 x 50 2 () 將原來指向 50 的鏈結改成指向 2 0 0 39
(3). 利用 Link list 實作 Stack 優點 不受堆疊長度的限制 ( 除非記憶體不足 ) 可以動態的加入堆疊的元素 缺點 必需多一個儲存指標的欄位 實作上較為複雜 4.2 Stack 的應用 (). 主要的應用方向 副程式的呼叫與返回 運算式的轉換及求值 遞迴 (2). 副程式的呼叫與返回 基本觀念 範例主程式執行並呼叫兩個副程式, 請寫出執行下面步驟後的 返回位址堆疊 的內容? 開始 結束 主程式 0000 0002 0004 0006 0008 000 () 呼叫副程式 (4) 返回 副程式 000 002 004 006 008 (2) 呼叫副程式 2 (3) 返回 副程式 2 0200 0202 0204 0206 () (2) (3) (4) 執行上面各步驟後返回位址堆疊的內容 2 0 0002 2 006 0 0002 2 0 0002 2 0 (3). 運算式的轉換及求值 基本觀念 X = + * C ( D + E / F ) 運算式 : 等號的右邊稱為運算式運算子 (Operator) : +, -, *, / 40
運算元 (Operand) :,, C, D, E, F 運算子的優先順序 : (,) *, /, % +, - >, <, <=, >= &&, = 運算式的表示法 : 中序式 (infix): + 後序式 (postfix): + 前序式 (prefix): + 中序式轉成後序表示法的步驟 : +*C 將相關的運算元用括號括起來 ( + ( * C ) ) 找到他右邊最接近的右括號, 並加上箭號 ( + ( * C ) ) 將運算子移到右括號的位置 C * + 範例 ( 將下面的中序式轉成後序式 ) (+) * C D / E 答 : (((+) * C) (D/E)) (( + * C) D E/ ) ( + C* - D E/ ) + C* D E/ - 範例 ( 將下面的中序式轉成後序式 ) + (/C - D) * E F/G 答 : (( + (((/C) - D) * E)) (F/G)) (( + ((C/ - D) * E)) FG/ ) (( + (C/ D - * E)) FG/ ) (( + C/ D - E * ) FG/ ) ( C/ D - E * + FG/ ) C/ D - E * + FG/ - 範例 ( 將下面的中序式轉成後序式 ) (+) * (C D) / E 答 : (((+) * (C D)) / E ) ((+ * CD-) / E ) (+ CD- * / E ) + CD- * E / 範例 ( 將下面的中序式轉成後序式 ) + *C - (E + F) 4
答 : (( + (*C)) - (E + F)) (( + C*) - E F+) ( C*+ - E F+) C*+ E F+ - 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 +CD- * E / = ()CD- * E / = ()(-) * E / = (-) E / = -5.5 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 C*+ E F+ - = (2) + E F + - = (7) E F + - = (7) () = 6 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 + C* D E/ - = () C * D E / - = (22) D E / - = (22) (.5) = 20.5 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 C/ D - E * + FG/ - = (3) D - E * + F G / - = (0) E * + F G / - = (0) + F G / - = (5) F G / - = (5) (3) = 2 範例使用堆疊法將下面中序轉後序式 (+) * C D / E 次序運算式運算子堆疊 ( 底 頂 ) 輸出的後序式 ( ( 2 ( 3 + (+ 4 (+ 5 ) + 42
6 * * + 7 C * +C 8 - - +C* 9 D - +C*D 0 / -/ +C*D E 4.3 Queue (). 基本觀念 定義 : 將東西排成一列, 先到的先處理 特性 : 先進先出, 後進後出 Queue 運算 EnQueue: 將資料放入佇列 DeQueue: 將資料由佇列的前端取出一個 IsEmpty: 用來檢查目前佇列是否為空 IsFull: 用來檢查目前佇列是否已經滿了 Queue 宣告 typredef struct tagqueue { 43
char item[mx_item]; // 假設 MX_ITEM = 7; int front; // 下次將取出資料的地方 int rear; // 本次已加入資料的地方 } QUEUE; Queue 使用 QUEUE q; q.front = -; q.rear = -; 加入資料 : rear 加, 將新項目加入到 item[rear] 中 取出資料 : front 加, 讀出 item[front] 中的資料 Queue 加入資料 q.enqueue(); // 加入 rear = 0, front = - Item[3] Item[4] Item[5] Item[6] q.enqueue(); // 加入 rear =, front = - Item[3] Item[4] Item[5] Item[6] q.enqueue(c); // 加入 C rear = 2, front = - Item[3] Item[4] Item[5] Item[6] Queue 取出資料 str = q.dequeue(); rear = 2, front = 0 Item[3] Item[4] Item[5] Item[6] C 44
str2 = q.dequeue(); rear = 2, front = Item[3] Item[4] Item[5] Item[6] str3 = q.dequeue(); rear = 2, front = 2 C Item[3] Item[4] Item[5] Item[6] C q.enqueue(d); // 加入 D rear = 3, front = 0 Item[3] Item[4] Item[5] Item[6] D (2). 環狀佇列 定義 : 將東西排成一列, 先到的先處理 優點 : 可以重複使用佇列的位置 (3). 利用陣列來模擬環狀佇列 判斷是否可以再加入資料 : MaxSize = 3 Rear = 2 Front = 利用陣列來模擬環狀佇列 (Rear+) Mod MaxSize = 3 Mod 0 = 0 45
比較 Rear 和 Front 的值 Rear < Front 則可以放入資料 Rear = Front 滿了!! 無法放入資料 範例 : MaxSize = 5, Rear = 3, Front = 3, 表示目前為空 Rear = 4 (MaxSize), Front = 3, 無法放入資料 利用陣列來模擬環狀佇列 (Rear+) Mod MaxSize = 5 Mod 5 = 0 比較 Rear 和 Front 的值 Rear < Front 則可以放入資料 Rear = Front 滿了!! 無法放入資料 0 < Front 可以放入資料放入到 0 的位置 範例 : MaxSize = 6, Rear = 4, Front = 3 () 是否可以再放入資料 (Rear + ) % MaxSize = 5 % 6 = 3 Rear (3) = Front (3) ns: 不可放入資料 (2) 放入的資料位置在何處 ns: 不可放入資料 範例 : MaxSize = 5, Rear = 2, Front = 4 () 是否可以再放入資料 (2+) % 5 = 3 3 < 4 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 3 的位置 範例 : MaxSize = 7, Rear = 7, Front = 6 () 是否可以再放入資料 (7+) % 7 = 4 46
4 < 6 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 4 的位置 範例 : MaxSize = 5, Rear = 3, Front = 4 () 是否可以再放入資料 (3+) % 5 = 2 2 < 4 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 2 的位置 (4). 用陣列結構實作佇列 範例 範例 範例 使用函數動作說明 Rear 值 Front 值 EnQueue() 把 加到 0 的位置 0-2 EnQueue() 把 加到 的位置 - 3 DeQueue() 取出 0 4 EnQueue(C) 把 C 加到 2 的位置 2 0 5 DeQueue() 取出 2 6 DeQueue() 使用函數動作說明 Rear 值 Front 值 EnQueue() 把 加到 0 的位置 0 - EnQueue() 把 加到 的位置 - DeQueue() 取出 0 EnQueue(C) 把 C 加到 2 的位置 2 0 DeQueue() 取出 2 DeQueue() 取出 C 2 2 使用函數動作說明 Rear 值 Front 值 EnQueue() 把 加到 3 的位置 3 47
EnQueue(C) 把 C 加到 0 的位置 0 EnQueue(D) 把 D 加到 的位置 DeQueue() 取出 2 EnQueue(E) 把 E 加到 2 的位置 2 2 DeQueue() 取出 2 3 用鏈結串列實作佇列 4.4 綜合練習 (). 利用鏈結串列方式實作貨品管理程式 (array_link_list_0.txt) 本練習要利用陣列的方式撰寫一個進出貨管理程式 48