資料結構 第4章 堆疊
4-1 認識堆疊 堆疊 (stack) 是一個線性串列 (linear list)，兩端分別稱為頂端 (top) 與底端 (bottom)，無論要新增或刪除資料，都必須從堆疊的頂端開始。
4-2 堆疊的實作 4-2-1 使用陣列實作堆疊 堆疊應該要提供下列運算： #define MAX_SIZE 5 4-2 堆疊的實作 4-2-1 使用陣列實作堆疊 #define MAX_SIZE 5 typedef struct stk{ char data[MAX_SIZE]; int top; }stack; 堆疊應該要提供下列運算： 判斷堆疊已滿 (isFull) 判斷堆疊已空 (isEmpty) 推入 (push) 彈出 (pop)
堆疊的 [推入] 運算
堆疊的 [彈出] 運算
4-2-2 使用鏈結串列實作堆疊 typedef struct node{ int data; struct node *next; 4-2-2 使用鏈結串列實作堆疊 typedef struct node{ int data; struct node *next; }list_node; typedef list_node *list_pointer;
鏈結堆疊的 [推入] 運算
鏈結堆疊的 [彈出] 運算
4-3 堆疊的應用 資料反轉 (reversing) 資料剖析 (parsing) 回溯 (backtracking)
4-3-1 轉換運算式表示法 當運算子位於運算元的中間時 (例如a + b)，屬於中序表示法 (infix)；當運算子位於運算元的前面時 (例如+ab)，屬於前序表示法 (prefix)；當運算子位於運算元的後面時 (例如ab+)，屬於後序表示法 (postfix)。 範例4.7：使用 [括號法] 將a * (b + c) - d由中序表示法轉換成後序表示法。
範例4.8：使用 [括號法] 將a * (b + c) - d由中序表示法轉換成前序表示法。
範例4.9：使用 [堆疊法] 將a * (b + c) - d由中序表示法轉換成後序表示法。
4-3-2 計算後序表示法 範例4.11：[計算後序表示法] 假設a = 5、b = 6、c = 7、d = 8，試計算後序表示法abc+*d- 的結果。
4-3-3 系統堆疊
4-3-4 遞迴 河內塔 (towers of hanoi) 例如當河內塔有三個圓盤時，開始與結束情況如下： 一次只能移動一個圓盤 4-3-4 遞迴 河內塔 (towers of hanoi) 一次只能移動一個圓盤 小圓盤必須疊在大圓盤上 例如當河內塔有三個圓盤時，開始與結束情況如下：
從1、2、3個圓盤類推到n個圓盤： 當有1個圓盤時，直接將圓盤從柱子A移到柱子C即可。
當有2個圓盤時 (假設由小到大，依序編號為1、2)，搬移順序如下：
當有3個圓盤時 (假設由小到大，依序編號為1、2、3)，搬移順序如下：
當有n個圓盤時 (假設由小到大，依序編號為1、2、…、n)，搬移順序如下：