---
# System prepended metadata

title: Data Structure / Stack
tags: [Data Structure]

---

# 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. 錯誤處理：
   - 運算式語法檢查
   - 除數為零的檢查
   - 堆疊溢出的處理