6.3 Stack and Queue 堆疊與佇列

Stack 堆疊

  • Def:
  • Stack 基本操作: ADT(Abstract Data Type)只定義不實作
    1. create(s):
    2. push(i, s):
    3. isEmpty(s):
    4. isFull(s):
    5. top(s):
    6. pop(i, s):
  • Ex1:
  • Ex2:
  • Ex3:
  • 應用:

Stack 的應用

Stack 之 ADT 的製作方式

以 array 製作 stack

  • 資料結構:
  • implement:
  1. create
1

  1. isEmpty
1
2
3
```

3. isFull  
1
2

4. push  
1
2

5. pop  

## Queue 佇列
* Def: 為一組元素, 具下列特性 (有序串列):  
  1. FIFO 之特質  
  2. 插入(於 rear 尾端)跟刪除(於 front 前端)於不同端點

### 提供的基本操作
1. create(Q):  
2. add(item, Q):  
3. delete(item, Q):  
4. isEmpty(Q):  
5. isFull(Q):  

* Ex:  

### Queue 的種類
1. 一般的佇列:  
  * FIFO  
  * 前端刪除尾端加入  
2. Priority queue (Heap)優先權佇列  
  * 提供:  
    1. 加入任意值元素  
    2. 刪除最大(Max-heap)或最小值(Min-heap)元素  
3. double ended queue 雙邊佇列  
  指於 front 和 rear 端皆可做插入跟刪除  
4. double ended priority queue 雙邊優先佇列  
  * 提供:  
    1. 插入任意元素  
    2. 刪除最大鍵值元素  
    3. 刪除最大鍵值元素  

### Queue 的應用
1.  
2.  
3.  
4.  

### Queue 之 ADT 製作方式
* 資料結構:  

* implement  
  1. create  
  2. isEmpty  
  3. isFull  
  4. add  
  5. delete  

* Note: 上述做法有下列問題
  * Ex:  
  * 思考:  
    * implement:  
      1. create:  
      2. add:  
      3. delete:  
  * 特質:  
    1.  
    2.  
    3.  
  * Note:  
  * 結論:  

### 中序, 前序, 中序
1. **中序式 (infix)**  
  * Def:  
  * 適合  
  * 對  
2. **後序式 (postfix)**  
  * 優點:  
3. **前序式 (prefix)**  
  * 優點:  

### compare

### 中序轉後序的方式: 
1. 括號法  
2. 將之用 binary tree 表示, 再以後序追蹤  
3. 利用 stack algorithm  

#### 括號法

#### 反向考題

#### 後序式計算 (同 stack algorithm)
* Ex: