# 【考試向】資料結構筆記（堆疊、佇列、環狀佇列、後序表示式）

[TOC]

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

## 堆疊（Stack）

特性：後進先出（LIFO：**L**ast **I**n **F**irst **O**ut）

資料只能在頂端（Top）做堆入（Push），跟移除（Pop）。


Image Source：[Stack Data Structure and Implementation in Python, Java and C/C++](https://www.programiz.com/dsa/stack)

應用：

- Ctrl + Z 復原功能
- 函式呼叫
- 括號匹配
- DFS（Depth First Search：深度優先搜尋）

時間複雜度：

- 堆入（Push）： $O(1)$
- 移除（Pop）： $O(1)$

優點：

- 記憶體管理高效：資料只在頂端操作，記憶體配置連續可預測。在系統層級（如 Call Stack），比堆積（Heap）快很多。
- 存取速度快（$O(1)$）：無論堆疊有多大，Push 跟 Pop 的時間複雜度永遠是 $O(1)$ 。
- 防資料碎片化：資料按順序堆疊，不會像其他結構一樣在記憶體中留下零散的空隙。

缺點：

- Stack Overflow：遞迴過深或存放過多，記憶體用太多易導致程式當掉。
- 靈活性差：不支援隨機存取（Random Access），要拿中間某個資料只能一個一個把東西拿出來才能拿到。

### 實作方式

使用 C 語言實作。

標頭檔 `#include <stdbool.h>` 用於 `true`/`false`。

- 變數 `int top = -1` 用於追蹤 stack 目前的位置。
- `top == MAX - 1` 判斷 stack 滿了沒。
- `top == -1` 判斷 stack 是否為空。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int stack[MAX];

int top = -1;

bool empty(){
    return top == -1;
}

void push(int data){
    if (top == MAX - 1){
        printf("堆疊已滿:資料 %d 無法堆入堆疊\n", data);
    }
    else{
        top++;
        stack[top] = data;
        printf("資料 %d 堆入堆疊\n", data);
    }
}

int pop(){
    if (empty()){
        printf("堆疊為空:無法 pop\n");
        return -1;
    }
    else{
        int data = stack[top];
        top--;
        return data;
    }
}

void printStack() {
    printf("目前堆疊內容: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    for (int i = 0; i <= top; i++) printf("%d ", stack[i]);
    printf(" <- Top\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    printStack();

    int val = pop();
    printf("取出的值為:%d\n", val);
    printStack();

    push(40);
    push(50);
    push(60);
    push(70);
    printStack();

    while (!empty()) {
        pop();
    }
    pop();

    return 0;
}

## 佇列（Queue）

特性：先進先出（FIFO：**F**irst **I**n **F**irst **O**ut）

想像陣列分為兩端開口：前端（Front）跟尾端（Rear）。

可以做到加入（enqueue）、移除（dequeue）元素這兩種操作。


Image Source：[What is Queue Data Structure? - GeeksforGeeks](https://www.geeksforgeeks.org/dsa/what-is-queue-data-structure/)

應用：

- 作業系統層面：
- CPU 工作排程：利用佇列管理待執行的程序（Processes），確保每個任務按順序或優先級獲得處理時間。
- 
- IO 緩衝區（Buffering）：當資料產生速度快於處理速度時（如印表機排隊列印、磁碟寫入等等），佇列可暫存資料避免遺失情形發生。
- BFS（Breadth First Search：廣度優先搜尋）

時間複雜度：

- Enqueue：$O(1)$
- Dequeue：$O(1)$（不移動元素，只移動指標）

優點：

- 保證公平性與順序：處理多執行緒任務排程或網路封包時很重要。
- 解耦（Decoupling）：在分散式系統中，佇列（如 RabbitMQ, Kafka）可作為生產者與消費者之間的緩衝，讓雙方不需要同時在線，增加系統穩定性。

缺點：

- 假溢位問題：若用簡單陣列實作，當前端資料 dequeue 後，後面的資料若不往前移，就會浪費前端的記憶體空間。而一旦往前移的話，就會額外耗費 $O(N)$ 時間。
- 搜尋效率低：若要確認某個特定資料是否在佇列中，必須遍歷整個佇列 ($O(n)$)。

### 實作方式

使用 C 語言實作。

輸出結果顯示一般佇列實作方式的問題，移除資料時，剩餘資料沒有往前移，因此導致後面要加入資料進去就加不進去，這情況差不多就像是下圖那樣：


Image Source：作者繪製。

程式實作講解：

- 雙指標法：變數 `int front = -1`、`int rear = -1` 各別追蹤前端、尾端。
- enqueue 時 `rear` 增加。
- dequeue 時 `front` 增加。
- `rear == MAX - 1` 判別一個佇列是否已滿。
- `front == -1 && rear == -1` 判別一個佇列是否為空。
- 在 `dequeue` 時做 `front >= rear` 判別，把兩個變數初始化成 `-1` ，免得 `front` 越加越多。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;

bool empty(){
    return front == -1 && rear == -1;
}

void enqueue(int data){
    if (rear == MAX - 1){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        if (front == -1){
            front = 0;
        }
        rear++;
        queue[rear] = data;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        if (front >= rear){
            front = -1;
            rear = -1;
            printf("取出資料 %d [佇列已空]\n", data);
        }
        else{
            front++;
            printf("取出資料 %d\n", data);
        }
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    for (int i = front; i <= rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printQueue();

    dequeue();
    printQueue();
    
    enqueue(40);
    enqueue(50);
    printQueue();

    enqueue(60);

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
目前佇列: Front -> 10 20 30 <- Rear
取出資料 10
目前佇列: Front -> 20 30 <- Rear
加入資料 40
加入資料 50
目前佇列: Front -> 20 30 40 50 <- Rear
佇列已滿:資料 60 無法加入

## 環狀佇列（Circular Queue）

環狀佇列是為了解決一般佇列的假溢位問題而誕生的，將陣列的頭尾邏輯上相連，讓 `rear` 可以繞回 Index 0 繼續存放資料。

環狀佇列在物理上仍然是一個線性陣列，但在邏輯上，用模運算（Modulo Operator, %）讓索引值循環。

假設 `front` 跟 `rear` 兩指標為 `index`，則要做指標移動時，搭配模運算動：$$index = (index + 1) \% N$$

當 $index$ 為 $N-1$（最後一格）時，$(N-1+1) \% N$ 會變成 $0$。

### 實作方式 A：空位版

這是第一種實作方式，有一個缺點，就是會有一個空位留在那邊。

程式實作講解：

- 雙指標 `int front = 0`、`int rear = 0`，注意這邊要設成 `0` 而不是 `-1`。
- `front` 代表指向第一個元素
- `rear` 代表指向下一個空位
- `front == rear` 判斷佇列是否為空。
- `(rear + 1) % MAX == front` 判斷佇列是否滿了。因為這裡，才會把空位留在那不能加入。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = 0;
int rear = 0;

bool empty(){
    return front == rear;
}

void enqueue(int data){
    if ((rear + 1) % MAX == front){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        queue[rear] = data;
        rear = (rear + 1) % MAX;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        front = (front + 1) % MAX;
        printf("取出資料 %d\n", data);
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    int i = front;
    while (i != rear) {
        printf("%d ", queue[i]);
        i = (i + 1) % MAX; // 移動到下一格
    }
    
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    printQueue();

    enqueue(50); 
    
    dequeue();
    dequeue();
    printQueue();

    enqueue(50);
    enqueue(60);
    printQueue();

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
加入資料 40
目前佇列: Front -> 10 20 30 40 <- Rear
佇列已滿:資料 50 無法加入
取出資料 10
取出資料 20
目前佇列: Front -> 30 40 <- Rear
加入資料 50
加入資料 60
目前佇列: Front -> 30 40 50 60 <- Rear

### 實作方式 B：無空位版

改進方式是在原有的程式碼中，新增 `int count = 0;`，去判斷目前有多少個元素，剩下邏輯不變。

基本上就是判斷目前佇列大小。

- `count == 0;` 判斷佇列是否為空。
- `count == MAX;` 判斷佇列是否滿了。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = 0;
int rear = 0;
int count = 0;

bool empty(){
    return count == 0;
}

void enqueue(int data){
    if (count == MAX){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        queue[rear] = data;
        rear = (rear + 1) % MAX;
        count++;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        front = (front + 1) % MAX;
        count--;
        printf("取出資料 %d\n", data);
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    int temp = front;
    for (int i = 0; i < count; i++) {
        printf("%d ", queue[temp]);
        temp = (temp + 1) % MAX; // 移動臨時指標
    }
    
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    printQueue();

    enqueue(50);
    printQueue();
    
    dequeue();
    dequeue();
    printQueue();

    enqueue(50);
    enqueue(60);
    printQueue();

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
加入資料 40
目前佇列: Front -> 10 20 30 40 <- Rear
加入資料 50
目前佇列: Front -> 10 20 30 40 50 <- Rear
取出資料 10
取出資料 20
目前佇列: Front -> 30 40 50 <- Rear
加入資料 50
加入資料 60
目前佇列: Front -> 30 40 50 50 60 <- Rear

## 堆疊應用：後序表示式（Postfix notation）

在談後序表示式前，需要先知道中序表示式。

### 中序表示式（Infix Notation）

中序表示式是人類最習慣用的寫法，就是將兩個運算元之間夾帶一個運算子，如：$$1 + 1$$

這種形式的寫法就叫做中序表示式。

格式： $Operand \ A \quad Operator \quad Operand \ B$

缺點： 對於電腦來說，這個處理起來比較複雜，因為需要處理「運算子優先順序」（如乘除先於加減）以及「括號」來改變順序。如果用這個寫法來做處理，時間複雜度可能最多會到 $O(N^2)$ ，善用演算法技巧如雙堆疊法，可減至 $O(N)$ 。

### 後序表示式（Postfix notation）

後序表示式又稱為逆波蘭表示式（Reverse Polish Notation, RPN）。

這種寫法是可以讓電腦看得懂的寫法，而且會比較快，原理是將運算子放在兩個運算元後面，如：$$1 \ 1 \ +$$

原本中序表示式的寫法是 $$1 + 1$$

優點：

1. 不需要括號
2. 電腦好處理：電腦只要從左讀到右，遇到數字就存起來，遇到運算子就抓最近的兩個數字運算，非常適合以堆疊（Stack）來實作。

時間複雜度： $O(N)$ ，但是因為用堆疊實作，一些操作基本上是常數時間，執行速度上來說會比中序還快。

### 中序轉後序（堆疊法）

用堆疊將中序轉後序，主要依照以下規則：

1. 遇到運算元（數字 or 變數）：直接輸出。
2. 遇到左括號 `(`：放入堆疊。
3. 遇到右括號 `)`：將堆疊中的運算子依序 pop 並輸出，直到 pop 左括號 `(` 為止（括號不輸出）。
4. 遇到運算子（`+`, `-`, `*`, `/`）：
- 檢查堆疊頂端的運算子。
- 若堆疊頂端運算子優先權 $\ge$ 目前運算子：將堆疊頂端 pop 並輸出，重複此步驟直到堆疊頂端優先權較小或是遇到 `(`。
- 將目前的運算子放入堆疊。
5. 讀取完畢：將堆疊中剩餘的所有運算子依序 pop 並輸出。

至於優先順序，大致上就如下表所示：

| 優先順序（Priority） | 運算子（Operator） |
| -------- | -------- |
| 5（最高） | `*`, `/`, `%` |
| 4 | `+`, `-` |
| 3 | `<`, `<=`, `>`, `>=` |
| 2 | `&&` |
| 1（最低） | `||` |

另外在實作「中序轉後序」演算法時，需要兩數值來決定動作，因為左括號 `(` 在堆疊外和堆疊內的優先順序是完全不同的。

因此在這邊會有兩個名詞：

- ICP（Incoming Priority）：運算子在堆疊外（剛讀到，準備進去）的優先順序。
- ISP（In-Stack Priority）：運算子在堆疊內（已在內）的優先順序。

運算規則：

- 若 $ICP > ISP \rightarrow$ 堆入堆疊（push）。
- 若 $ICP \le ISP \rightarrow$ pop 並輸出，直到 $ICP > ISP$ 為止，然後再 push。

優先順序表（數字越低，優先順序越低；數字越高，優先順序越高）：

| 運算子（Operator） | ICP（堆疊外優先順序） | ISP（堆疊內優先順序） |
| -------- | -------- | -------- |
| `)` | 1 | N/A |
| `*`, `/`, `%` | 2 | 2 |
| `+`, `-` | 1 | 1 |
| `(` | 4 | 1 |

右括號 `)` 被讀到後需要 pop 找到 `(` 才結束，且不進堆疊。

左括號 `(` 在進堆疊後，優先順序變最低的原因是為了不擋住後續進來的任何 `+`, `-`, `*`, `/`，讓括號內的運算子能順利堆疊起來。

### 中序轉後序（堆疊法）範例

將以下中序表示式轉換成後序表示式：$$A + B * (C - D) / E$$

解法：

先求出後序表示式的結果：$$A B C D - * E / +$$

ok 之後就開始來做模擬表了（記得規則就是上節的那五條）：

| 讀取字元（next token） | 堆疊內容（stack） | 輸出（output） | 說明 |
| -------- | -------- | -------- | -------- |
| A | empty | A | 遇到運算元直接輸出 |
| `+` | `+` | A | 堆疊為空，直接 push |
| B | `+` | A B | 遇到運算元直接輸出 |
| `*` | `+` `*` | A B | `*` 優先順序大於堆疊頂端 `+`，push |
| `(` | `+` `*` `(` | A B | 左括號 `(` 直接 push |
| `C` | `+` `*` `(` | A B C | 遇到運算元直接輸出 |
| `-` | `+` `*` `(` `-` | A B C | 堆疊頂端是 `(`，直接 Push |
| D | `+` `*` `(` `-` | A B C D | 遇到運算元直接輸出 |
| `)` | `+` `*` | A B C D `-` | 遇到右括號，不斷 pop 直到遇到 `(`，由於這邊 `-` 被 pop 掉了，所以直接輸出 `-` |
| `/` | `+` `/` | A B C D `-` `*` | 1. 比較 `*` 與 `/`。<br>2. `*` 優先順序 $\ge$ `/`，pop `*`。<br>3. 接著比較 `+`，`+` $\le$ `/`，因此 `/` push 進去。 |
| E | `+` `/` | A B C D `-` `*` E | 遇到運算元直接輸出 |
| none | empty | A B C D `-` `*` E `/` `+` | 字串讀完後，pop 所有剩餘項目（`/` 接下來是 `+`） |

最後得到後序表示式就是 $A B C D - * E / +$ 。

### 中序轉後序（括號法）

繼續以上節的範例為例子： $$A + B * (C - D) / E$$

先找到原本的括號 $(C - D)$ ，就不動他，再看到運算子優先級最高的部分，也就是乘除的地方，由於優先級相同，於是先從左邊開始算： $$B * (C - D)$$

加上括號後，接著再算 $$(B * (C - D)) / E$$

一樣加上括號後，最後做加法 $$A + ((B * (C - D)) / E)$$

最後補齊括號 $$(A + ((B * (C - D)) / E))$$

做好前處理之後，就要先從最內層的括號開始轉換，每一組 `(X op Y)`，轉成後序就是 `X Y op`。

第一個是 $$(C - D) \rightarrow C D -$$

接下來 $$(B * (C D -)) \rightarrow BCD - *$$

接下來 $$((B C D - *) / E) \rightarrow BCD - * E /$$

最後 $$(A + (BCD - * E /)) \rightarrow ABCD - * E / +$$

### C 程式實作：中序轉後序

基本上在函式 `infixToPostfix()` 中，主要以五條規則下撰寫：

1. 遇到運算元（數字 or 變數）：直接輸出。
2. 遇到左括號 `(`：放入堆疊。
3. 遇到右括號 `)`：將堆疊中的運算子依序 pop 並輸出，直到 pop 左括號 `(` 為止（括號不輸出）。
4. 遇到運算子（`+`, `-`, `*`, `/`）：
- 檢查堆疊頂端的運算子。
- 若堆疊頂端運算子優先權 $\ge$ 目前運算子：將堆疊頂端 pop 並輸出，重複此步驟直到堆疊頂端優先權較小或是遇到 `(`。
- 將目前的運算子放入堆疊。
5. 讀取完畢：將堆疊中剩餘的所有運算子依序 pop 並輸出。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

bool isEmpty(){
    return top == -1;
}

void push(char i){
    if (top >= MAX - 1){
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = i;
}

char pop(){
    if (isEmpty()){
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

char peek(){
    if (isEmpty()) return -1;
    return stack[top];
}

int getPriority(char op){
  switch (op){
    case '*':
    case '/':
    case '%':
      return 2;
    case '+':
    case '-':
      return 1;
    case '(':
      return 0;
    default:
      return -1;
  }
}

void infixToPostfix(char* infix, char* postfix){
  int i = 0; // infix 的索引
  int j = 0; // postfix 的索引
  char token;
  
  while ((token = infix[i++]) != '\0'){
    
    // 1. 如果是運算元 (字母或數字)，直接輸出
    if (isalnum(token)){
      postfix[j++] = token;
      postfix[j++] = ' '; // 美觀用
    }
    // 2. 如果是左括號，直接 push 進堆疊
    else if (token == '('){
      push(token);
    }
    // 3. 如果是右括號，pop 直到遇到左括號
    else if (token == ')'){
      while (!isEmpty() && peek() != '('){
        postfix[j++] = pop();
        postfix[j++] = ' ';
      }
      if (!isEmpty() && peek() == '('){
        pop(); // 把左括號丟掉，不輸出
      }
    }
    // 4. 如果是運算子
    else if (token == '+' || token == '-' || token == '*' || token == '/' || token == '%'){
      // 當堆疊不為空，且堆疊頂端優先權 >= 目前運算子優先權
      // 就要把堆疊頂端踢出來 (Pop)
      while (!isEmpty() && getPriority(peek()) >= getPriority(token)){
        postfix[j++] = pop();
        postfix[j++] = ' ';
      }
      // 踢完之後，把自己放進去
      push(token);
    }
  }
  // 5. 處理剩餘的運算子
  while (!isEmpty()){
    postfix[j++] = pop();
    postfix[j++] = ' ';
  }
  
  postfix[j] = '\0'; // 記得加上字串結束符號
}

int main(){
  char infix[] = "A+B*(C-D)/E";
  char postfix[MAX];
  
  printf("中序表示式: %s\n", infix);
  
  infixToPostfix(infix, postfix);
  
  printf("後序表示式: %s\n", postfix);
  
  return 0;
}

Output：

中序表示式: A+B*(C-D)/E
後序表示式: A B C D - * E / + 

### 用堆疊計算後序表示式的結果

基本上只要做兩件事情：

1. 遇到運算元（Operand）：直接堆入堆疊（push）。
2. 遇到運算子（Operator）：從堆疊拿出兩個數字運算，算完把結果放回去。

當遇到運算子（例如 `/`）時，要從堆疊 Pop 兩次：

1. 第一次 Pop 出來的數字：是「右邊」的運算元（Right Operand）。
2. 第二次 Pop 出來的數字：是「左邊」的運算元（Left Operand）。

公式：$$Value = SecondPop \ (Op) \ FirstPop$$

Op = Operator

假設有個後序表示式是 $1 \ 2 \ 5 \ 3 \ - \ * \ 2 \ / \ +$ （其對應的中序表示式是 $1 + 2 * (5 - 3) / 2$），如何用堆疊模擬後序表示式的計算結果？

| 讀取字元（next token） | 堆疊內容（stack） | 說明 |
| -------- | -------- | -------- |
| 1 | 1 | 數字 $\rightarrow$ push |
| 2 | 1, 2 | 數字 $\rightarrow$ push |
| 5 | 1, 2, 5 | 數字 $\rightarrow$ push |
| 3 | 1, 2, 5, 3 | 數字 $\rightarrow$ push |
| `-` | 1, 2, 2 | 1. pop 出 3（右運算元）<br>2. Pop 出 5（左運算元）<br>3. 計算 $5 - 3 = 2$<br>4. 將 2 push 回去 |
| `*` | 1, 4 | 1. pop 出 2<br>2. pop 出 2<br>3. 計算 $2 * 2 = 4$<br>4. 將 4 push 回去 |
| 2 | 1, 4, 2 | 數字 $\rightarrow$ push |
| `/` | 1, 2 | 1. pop 出 2（除數）<br>2. pop 出 4（被除數）<br>3. 計算 $4 / 2 = 2$<br>4. 將 2 push 回去 |
| `+` | 3 | 1. pop 出 2<br>2. pop 出 1<br>3. 計算 $1 + 2 = 3$<br>4. 將 2 push 回去 |
| none | 3 | 讀取完畢，堆疊內唯一的數字即為答案。 |

### C 程式實作：計算後序表示式

註：以下程式碼僅展示後序表示式的數值計算，並未將前面的中序轉後序程式做結合。另外該版本程式碼支援多位數的計算。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int i){
  if (top >= MAX - 1){
    printf("Stack Overflow\n");
    return;
  }
  stack[++top] = i;
}

int pop(){
  if (top == -1){
    printf("Stack Underflow\n");
    exit(1);
  }
  return stack[top--];
}

int evalPostfix(char* postfix){
  int i = 0;
  
  while (postfix[i] != 0){
    if (postfix[i] == ' '){
      i++;
      continue;
    }
    
    if (isdigit(postfix[i])){
      int num = 0;
      
      while (isdigit(postfix[i])){
        num = num * 10 + (postfix[i] - '0');
        i++;
      }
      push(num);
    }
    else{
      int val2 = pop();
      int val1 = pop();
      
      switch(postfix[i]){
        case '+': push(val1 + val2); break;
        case '-': push(val1 - val2); break;
        case '*': push(val1 * val2); break;
        case '/': 
            push(val1 / val2); 
            break;
        case '%': 
            push(val1 % val2); 
            break;
        default: 
            printf("Unknown operator: %c\n", postfix[i]); 
            exit(1);
      }
      i++;
    }
  }
  return pop();
}

int main() {
    char postfix[] = "1 2 5 3 - * 2 / +";
    
    printf("後序表示式: %s\n", postfix);
    
    int result = evalPostfix(postfix);
    
    printf("計算結果: %d\n", result);
    
    return 0;
}

## 總整理

### 堆疊（Stack）

特性：

- 後進先出（LIFO）
- 僅能在頂端（Top）進行操作（Push / Pop）
- Push、Pop 皆為 O(1)

應用：

- Ctrl + Z（復原）
- 函式呼叫（Call Stack）
- 括號匹配
- DFS（深度優先搜尋）

優點：

- 操作速度快、實作簡單
- 記憶體連續、效率高（系統層面尤為重要）

缺點：

- 容易 Stack Overflow（遞迴過深）
- 不支援隨機存取

Stack 是只看最頂端的資料結構，適合處理「巢狀結構」與「反向回復」問題。

### 佇列（Queue）

特性：

- 先進先出（FIFO）
- 使用 Front / Rear 兩端操作
- Enqueue / Dequeue 皆為 O(1)（指標移動）

應用：

- CPU 排程
- IO Buffer
- BFS（廣度優先搜尋）
- 生產者—消費者模型（如 Kafka、RabbitMQ）

優點：

- 公平、有序，適合排隊處理任務
- 可作為系統模組間的緩衝區

缺點：

- 一般陣列實作會有「假溢位」問題
- 搜尋效率低（$O(n)$）

### 環狀佇列（Circular Queue）

主要用於解決一般 Queue 的「假溢位」問題。

核心技巧：

- 使用模運算 `%`，讓索引循環
- 邏輯上首尾相接，實體仍為陣列

兩種實作策略：

1. 空位版：
- 判斷滿：(rear + 1) % MAX == front
- 判斷空：front == rear
- 缺點：浪費一格空間
2. 無空位版：
- 使用 count 紀錄目前元素數
- 判斷空：count == 0
- 判斷滿：count == MAX
- 空間利用率 100%

環狀佇列只索引循環，不搬資料。

### 堆疊應用：後序表示式（Postfix / RPN）

為何需要後序表示式？

中序表示式（如 1 + 2）對電腦不友善，需處理優先順序與括號。

後序表示式：

- 不需要括號
- 非常適合用 Stack 處理
- 時間複雜度 $O(N)$

### 中序轉後序（Infix → Postfix）

堆疊法核心規則（五條）：

1. 運算元 → 直接輸出
2. 左括號 `(` → push
3. 右括號 `)` → pop 直到遇到 `(`
4. 運算子 →
- Stack 頂端優先權 ≥ 自己 → pop
- 否則 push
5. 讀完後 → pop 剩餘運算子

重要觀念：左括號在 Stack 內的優先權最低。

---

括號法核心規則：

1. 前處理：從優先級最高的運算子開始補括號，已經有括號的就不用補了。
2. 拆括號：從最內層開始拆解， `(x op y)` 會轉成 `x y op` 。

### 計算後序表示式

演算法：

1. 運算元 → push
2. 運算子 → pop 兩次計算，再 push 回去

重要順序：

1. 第一次 pop → 右運算元
2. 第二次 pop → 左運算元

公式：$$Value = SecondPop \ (Op) \ FirstPop$$

最後 Stack 中唯一剩下的數字就是答案。