# Data Structure / Stack
## 1. 基本概念
堆疊（Stack）是一種遵循「後進先出」（Last In First Out，LIFO）原則的資料結構。我們可以將堆疊想像成一疊盤子：你只能從最上面放入或拿走盤子，無法直接觸及中間或底部的盤子。
## 2. 基本操作
1. **`push()`**：將新元素推入堆疊頂端
2. **`pop()`**：從堆疊頂端彈出元素
3. **`peek()`**：查看堆疊頂端的元素，但不移除
## 3. 堆疊的實作方式
先定義一個堆疊的基本介面ㄅ：
```java=
interface Stack<T> {
void push(T item) throws StackOverflowException;
T pop() throws StackUnderflowException;
T peek() throws StackUnderflowException;
boolean isEmpty();
boolean isFull();
}
```
### 3.1 使用陣列實作（Array-Based Implementation）
以下是使用陣列實作佇列的範例程式碼：
```java=
class ArrayStack<T> implements Stack<T> {
private T[] stack;
private int top;
private final int capacity;
@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
this.capacity = capacity;
stack = (T[]) new Object[capacity];
top = -1;
}
@Override
public void push(T item) throws StackOverflowException {
if (isFull()) {
throw new StackOverflowException("堆疊已滿");
}
stack[++top] = item;
}
@Override
public T pop() throws StackUnderflowException {
if (isEmpty()) {
throw new StackUnderflowException("堆疊是空的");
}
T item = stack[top];
stack[top--] = null; // 避免記憶體洩漏
return item;
}
@Override
public T peek() throws StackUnderflowException {
if (isEmpty()) {
throw new StackUnderflowException("堆疊是空的");
}
return stack[top];
}
@Override
public boolean isEmpty() {
return top == -1;
}
@Override
public boolean isFull() {
return top == capacity - 1;
}
}
// customize Exceptions
class StackOverflowException extends Exception {
public StackOverflowException(String message) {
super(message);
}
}
class StackUnderflowException extends Exception {
public StackUnderflowException(String message) {
super(message);
}
}
```
### 3.2 使用鏈結串列實作（Linked List Implementation）
以下是使用循環鏈結串列實作佇列的範例：
```java=
class LinkedStack<T> implements Stack<T> {
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}
private Node<T> top;
public LinkedStack() {
top = null;
}
@Override
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
}
@Override
public T pop() throws StackUnderflowException {
if (isEmpty()) {
throw new StackUnderflowException("堆疊是空的");
}
T item = top.data;
top = top.next;
return item;
}
@Override
public T peek() throws StackUnderflowException {
if (isEmpty()) {
throw new StackUnderflowException("堆疊是空的");
}
return top.data;
}
@Override
public boolean isEmpty() {
return top == null;
}
@Override
public boolean isFull() {
return false; // 鏈結串列實作的堆疊永遠不會滿
}
}
```
---
#### 所以泥在 Main Class 裡面就可以醬：
```java=
public class StackDemo {
public static void main(String[] args) {
try {
// 使用陣列實作的堆疊
Stack<Integer> arrayStack = new ArrayStack<>(5);
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(3);
System.out.println("Pop: " + arrayStack.pop()); // 3
System.out.println("Peek: " + arrayStack.peek()); // 2
// 使用鏈結串列實作的堆疊
LinkedStack<String> linkedStack = new LinkedStack<>();
linkedStack.push("Hello");
linkedStack.push("World");
System.out.println("Pop: " + linkedStack.pop()); // World
System.out.println("Peek: " + linkedStack.peek()); // Hello
} catch (StackOverflowException | StackUnderflowException e) {
System.err.println("堆疊操作錯誤: " + e.getMessage());
}
}
}
```
## 4. 堆疊的應用
1. 函式呼叫的管理
- 系統使用堆疊來追蹤函式的呼叫順序
- 儲存函式的區域變數和返回位址
2. [表達式求值](#堆疊在運算式處理中的應用)
- 中序、前序、後序運算式的轉換
- 運算式的計算
3. 編輯器的復原功能
- 儲存操作歷史
- 實現 Undo/Redo 功能
4. 瀏覽器的網頁歷史
- 回到上一頁/下一頁功能
5. 括號匹配檢查
```java=
public class BracketChecker {
public static boolean isBalanced(String expression) {
LinkedStack<Character> stack = new LinkedStack<>();
Map<Character, Character> brackets = new HashMap<>();
brackets.put(')', '(');
brackets.put('}', '{');
brackets.put(']', '[');
try {
for (char ch : expression.toCharArray()) {
if ("({[".contains(String.valueOf(ch))) {
stack.push(ch);
} else if (")}]".contains(String.valueOf(ch))) {
if (stack.isEmpty() ||
stack.pop() != brackets.get(ch)) {
return false;
}
}
}
return stack.isEmpty();
} catch (StackUnderflowException e) {
return false;
}
}
public static void main(String[] args) {
String expr1 = "({[]})";
String expr2 = "({[})";
System.out.println("表達式 " + expr1 + " 是否成對: " + isBalanced(expr1)); // true
System.out.println("表達式 " + expr2 + " 是否成對: " + isBalanced(expr2)); // false
}
}
```
## 5. 使用堆疊時的注意事項
1. 堆疊溢位（Stack Overflow，aka [Stack Overflow](https://stackoverflow.com/)）
- 確保不會超過堆疊容量
- 考慮使用動態大小的實作方式
2. 空堆疊處理
- 在 `pop()` 或 `peek()` 操作前檢查堆疊是否為空
- 適當的例外處理
3. 記憶體管理
- 適時釋放不需要的記憶體
- 避免記憶體洩漏
4. 如果是使用 JDK 的 `Stack` 類別，它是繼承自 `Vector`，在某些效能考量的情況下可能更適合使用 `ArrayDeque` 作為堆疊。
# 堆疊在運算式處理中的應用
由於電腦無法像人腦一樣，能夠在算式之間就進行先乘除後加減的優先級判斷與排序，因此才會設計出一套規則，能夠讓電腦step by step的處理好加減乘除。
## 1. 運算式的表示方法
在開始之前，讓我們先了解三種主要的運算式表示方法：
1. **中序表示法（Infix）**：這是我們最常用的表示方法，運算子放在兩個運算元之間，如 `A + B * C`。
2. **後序表示法（Postfix）**：也稱為逆波蘭表示法，運算子放在相關的運算元後面，如 `A B C * +`。
3. **前序表示法（Prefix）**：也稱為波蘭表示法，運算子放在相關的運算元前面，如 `+ A * B C`。
## 2. 中序轉後序（Infix to Postfix）
### 2.1 轉換原理
將中序式轉換為後序式時，我們需要：
1. 由左至右掃描運算式
2. 使用一個運算子堆疊（operator stack）來暫存運算子
3. 根據運算子優先順序決定輸出順序
### 2.2 轉換規則
1. 遇到運算元（operand）直接輸出
2. 遇到運算子（operator）時：
- 若堆疊為空，直接將運算子推入堆疊
- 比較目前運算子與堆疊頂端運算子的優先順序
- 若目前運算子優先順序 **較高**，則推入堆疊
- 若目前運算子優先順序 **較低或相等**，則將堆疊頂端運算子輸出，直到找到優先順序 **較低** 的運算子
### 2.3 範例說明
以 `A + B * C / D - E` 為例：
```plain
掃描順序 堆疊狀態 輸出結果
A 空 A
+ + A
B + AB
* +* AB
C +* ABC
/ +/ ABC*
D +/ ABC*D
- - ABC*D/+
E - ABC*D/+E
結束 空 ABC*D/+E-
```
### 2.4 範例程式碼（python）
```python=
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
operators = []
output = []
for char in expression:
if char.isalnum():
output.append(char)
elif char == '(':
operators.append(char)
elif char == ')':
while operators and operators[-1] != '(':
output.append(operators.pop())
operators.pop() # 移除 '('
else:
while (operators and operators[-1] != '(' and
precedence.get(operators[-1], 0) >= precedence.get(char, 0)):
output.append(operators.pop())
operators.append(char)
while operators:
output.append(operators.pop())
return ''.join(output)
# 測試範例
expr = "A+B*C/D-E"
print(infix_to_postfix(expr)) # 輸出：ABC*D/+E-
```
## 3. 中序轉前序（Infix to Prefix）
### 3.1 轉換原理
中序轉前序的過程與轉後序類似，但是：
1. 需要由右至左掃描運算式
2. 輸出時從左邊開始堆疊
3. 運算子優先順序的判斷方式略有不同
### 3.2 轉換規則
1. 遇到運算元（operand）直接輸出
2. 遇到運算子（operator）時：
- 若堆疊為空，直接將運算子推入堆疊
- 比較目前運算子與堆疊頂端運算子的優先順序
- 若目前運算子優先順序 **較高**，則推入堆疊
- 若目前運算子優先順序 **較低**，則將堆疊頂端運算子輸出，直到找到優先順序 **相同** 的運算子
### 3.3 範例說明
以 `A + B * C / D - E` 為例：
```plain
掃描順序 堆疊狀態 輸出結果
E 空 E
- - E
D - DE
/ -/ DE
C -/* CDE
* -/* BCDE
B -+ /*BCDE
+ -+ A/*BCDE
A 空 -+A/*BCDE
```
## 4. 運算式求值
### 4.1 後序式求值
後序式求值的過程相對簡單：
1. 由左至右掃描運算式
2. 遇到運算元則推入堆疊
3. 遇到運算子則從堆疊取出兩個運算元進行運算，將結果推回堆疊
#### 範例程式碼（python）：
```python=
def evaluate_postfix(expression):
stack = []
for token in expression:
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a / b)
return stack[0]
# 範例：評估 "47+82-*"
print(evaluate_postfix("47+82-*")) # 結果應為 66
```
### 4.2 前序式求值
前序式求值的過程與後序式類似，但需要：
1. 由右至左掃描運算式
2. 運算時注意運算元的順序
#### 範例程式碼（python）：
```python=
def evaluate_prefix(expression):
stack = []
for token in reversed(expression): # 前序式需從右到左掃描
if token.isdigit():
stack.append(int(token))
else:
a = stack.pop() # 注意：前序式彈出順序與後序式相反
b = stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a / b)
return stack[0]
# 範例：評估 "*+47-82" (相當於 (4+7)*(8-2))
print(evaluate_prefix("*+47-82")) # 結果應為 66
```
### 4.3 中序式求值
中序式求值需要兩個堆疊：
1. 運算元堆疊（operand stack）
2. 運算子堆疊（operator stack）
處理過程較為複雜，需要考慮：
1. 運算子優先順序
2. 括號的處理
3. 運算元的順序
#### 範例程式碼（python）：
```python=
def evaluate_infix(expression):
operators = []
values = []
for token in expression:
if token.isdigit():
values.append(int(token))
elif token in "+-*/":
while (operators and operators[-1] in "+-*/" and
precedence(operators[-1]) >= precedence(token)):
process_operator(operators, values)
operators.append(token)
elif token == '(':
operators.append(token)
elif token == ')':
while operators and operators[-1] != '(':
process_operator(operators, values)
operators.pop() # 移除 '('
while operators:
process_operator(operators, values)
return values[0]
def precedence(op):
if op in "+-": return 1
if op in "*/": return 2
return 0
def process_operator(operators, values):
op = operators.pop()
b = values.pop()
a = values.pop()
if op == '+': values.append(a + b)
elif op == '-': values.append(a - b)
elif op == '*': values.append(a * b)
elif op == '/': values.append(a / b)
# 範例：評估 "4+7*8-2" 和 "(4+7)*(8-2)"
print(evaluate_infix("4+7*8-2")) # 結果應為 58
print(evaluate_infix("(4+7)*(8-2)")) # 結果應為 66
```
## 5. 特殊考慮事項
1. 括號處理：
- 左括號 `(` 直接推入運算子堆疊
- 遇到右括號 `)` 時，不斷輸出運算子直到遇到左括號
2. 運算子優先順序：
- 括號最高優先順序
- 乘除（*、/） > 加減（+、-）
- 同級運算子從左到右運算
3. 錯誤處理：
- 運算式語法檢查
- 除數為零的檢查
- 堆疊溢出的處理
Sign in with Wallet
Connect another wallet