資料結構使用Java 第7章 堆疊(Stack)
課程內容 堆疊的基本結構 堆疊的特性 堆疊的操作 堆疊存取順序的影響 堆疊應用的實例 empty, push, pop, peek, search 堆疊存取順序的影響 堆疊應用的實例
堆疊的基本結構 每個物件為一個元素 堆疊的上方是開放的、底部則是封閉的。
堆疊的特性 放入或取出都只能從最上方元素的位置來進行。 先加者在下，後加者在上，元素間不能留空位。 空間有限，如果滿了就無法再加入
堆疊的特性 移除元素只能從堆疊最上方元素開始移除。 稱做後進先出(LIFO, Last In First Out) 堆疊清空就無法再取出元素
實作Stack 使用Java Collections Framework中的Stack類別 實作。 不用從頭寫一個全新的Stack功能程式。 Stack在Java API架構中的位置： import java.util.*; 宣告Linked List物件 Stack<元素DT> 物件名 = new Stack<元素DT> (); 例如：Stack<String> s = new Stack<String>();
是否為空(empty) 測試堆疊是否為空。跟前一個操作類似，它也是 用來測試堆疊的現況。 程式碼：物件名.empty(); 例如：s.empty();
推入(Push) 即是推入元素，這是將元素加入堆疊的唯一方法； 假如堆疊不是滿的，就把元素從上方放入堆疊。 例如：s.push(“Mary”);
彈出(pop) 即是彈出元素，並取得該元素的內容；假如堆疊 不是空的，就把目前位於最頂端的元素移出堆疊， 同時探知該元素是什麼內容。 例如：s.pop();
查看最頂端元素(peek ) 讀取最頂端的元素 此動作不推入新元素，也不取出既有的元素。 程式碼：物件名.peek(); 例如：s.peek();
搜尋某元素的位置(search ) 回傳某元素的位置(層次)值。 此動作不會推入新元素、或是彈出既有元素。 最上層的位置為1。 例如：s.search(“Martin”);
彈出Stack中的所有元素 判斷Stack是否為空 若不為空則彈出元素 重複步驟直到Stack為空 While(s.empty()!=true) System.out.println(s.pop());
存取Stack-不改變元素順序
存取Stack-不改變元素順序
存取Stack-不改變元素順序
存取Stack-元素順序完全倒轉
存取Stack-元素順序完全倒轉
存取Stack-元素順序完全倒轉
練習 輸入數字(不限個數)並反序印出。 數字0即代表輸入完畢。
堆疊應用的實例-數字排列 把3個數字以不同組合的push與pop操作 則會產生幾種不同的輸出順序? 3個元素自由排列的結果可有3!種，但並不是所有 可能的次序都能經由堆疊產生。
堆疊應用的實例-數字排列 第1個狀況:push與pop交錯進行
堆疊應用的實例-數字排列 不同組合的push與pop的操作 數字順序312，無法利用堆疊產生。
堆疊應用的實例-括弧對應的檢查 我們下面用堆疊來檢查一個字串裡頭的左括弧與 右括弧是否有適當的對應。
堆疊應用的實例-括弧對應的檢查
堆疊應用的實例-括弧對應的檢查
堆疊應用的實例-中序後序轉換(作業) 運算式的表示法 前序(prefix)表示法: + x y 中序(infix)表示法 : x + y 後序(postfix)表示法 : x y +
堆疊應用的實例-中序後序轉換
堆疊應用的實例-中序後序轉換
堆疊應用的實例-中序後序轉換 後序表示法計算取值的步驟