資料結構使用Java 第7章 堆疊(Stack).

Presentation on theme: "資料結構使用Java 第7章 堆疊(Stack)."— Presentation transcript:

1 資料結構使用Java 第7章 堆疊(Stack)

2 課程內容 堆疊的基本結構 堆疊的特性 堆疊的操作 堆疊存取順序的影響 堆疊應用的實例
empty, push, pop, peek, search 堆疊存取順序的影響 堆疊應用的實例

3 堆疊的基本結構 每個物件為一個元素 堆疊的上方是開放的、底部則是封閉的。

4 堆疊的特性 放入或取出都只能從最上方元素的位置來進行。 先加者在下，後加者在上，元素間不能留空位。 空間有限，如果滿了就無法再加入

5 堆疊的特性 移除元素只能從堆疊最上方元素開始移除。 稱做後進先出(LIFO, Last In First Out) 堆疊清空就無法再取出元素

6 實作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>();

7 是否為空(empty) 測試堆疊是否為空。跟前一個操作類似，它也是 用來測試堆疊的現況。 程式碼：物件名.empty();
例如：s.empty();

8 推入(Push) 即是推入元素，這是將元素加入堆疊的唯一方法； 假如堆疊不是滿的，就把元素從上方放入堆疊。
例如：s.push(“Mary”);

9 彈出(pop) 即是彈出元素，並取得該元素的內容；假如堆疊 不是空的，就把目前位於最頂端的元素移出堆疊， 同時探知該元素是什麼內容。
例如：s.pop();

10 查看最頂端元素(peek ) 讀取最頂端的元素 此動作不推入新元素，也不取出既有的元素。 程式碼：物件名.peek();
例如：s.peek();

11 搜尋某元素的位置(search ) 回傳某元素的位置(層次)值。 此動作不會推入新元素、或是彈出既有元素。 最上層的位置為1。
例如：s.search(“Martin”);

12 彈出Stack中的所有元素 判斷Stack是否為空 若不為空則彈出元素 重複步驟直到Stack為空
While(s.empty()!=true) System.out.println(s.pop());

13 存取Stack-不改變元素順序

14 存取Stack-不改變元素順序

15 存取Stack-不改變元素順序

16 存取Stack-元素順序完全倒轉

17 存取Stack-元素順序完全倒轉

18 存取Stack-元素順序完全倒轉

19 練習 輸入數字(不限個數)並反序印出。 數字0即代表輸入完畢。

20 堆疊應用的實例-數字排列 把3個數字以不同組合的push與pop操作 則會產生幾種不同的輸出順序?
3個元素自由排列的結果可有3!種，但並不是所有 可能的次序都能經由堆疊產生。

21 堆疊應用的實例-數字排列 第1個狀況:push與pop交錯進行

22 堆疊應用的實例-數字排列 不同組合的push與pop的操作 數字順序312，無法利用堆疊產生。

23 堆疊應用的實例-括弧對應的檢查 我們下面用堆疊來檢查一個字串裡頭的左括弧與 右括弧是否有適當的對應。

24 堆疊應用的實例-括弧對應的檢查

25 堆疊應用的實例-括弧對應的檢查

26 堆疊應用的實例-中序後序轉換(作業) 運算式的表示法 前序(prefix)表示法: + x y 中序(infix)表示法 : x + y
後序(postfix)表示法 : x y +

27 堆疊應用的實例-中序後序轉換

28 堆疊應用的實例-中序後序轉換

29 堆疊應用的實例-中序後序轉換 後序表示法計算取值的步驟