Stack

last update: 2025-06-09

Stack 是一種後進先出（LIFO, Last In First Out）的資料結構，常用於處理需要「反向順序」的任務，例如函式呼叫堆疊、字元反轉、遞迴展開等。

---

一、Stack 的基本結構

屬性	說明
top	指向目前堆疊頂端的節點
size	當前堆疊中的元素數量
max_size	堆疊可容納的最大元素數量（可選）

---

二、基本節點結構（Python 範例）

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

---

三、Stack 操作

1. 加入元素（push）

def push(self, value):
    if self.has_space():
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        self.size += 1
    else:
        print("Stack is full!")

2. 移除元素（pop）

def pop(self):
    if self.size > 0:
        value = self.top.value
        self.top = self.top.next
        self.size -= 1
        return value
    else:
        print("Stack is empty!")

3. 查看頂端元素（peek）

def peek(self):
    if self.size > 0:
        return self.top.value
    else:
        print("Stack is empty!")

---

四、輔助方法與屬性

def get_size(self):
    return self.size

def has_space(self):
    return self.max_size is None or self.size < self.max_size

def is_empty(self):
    return self.size == 0

---

五、Stack 特性

• 後進先出（LIFO）：最後加入的元素最先被取出

• 結構簡單：只操作堆疊頂端即可

• 適用場景：遞迴展開、括號匹配、Undo 操作等

---

六、Stack vs Queue 比較

特性	Stack	Queue
操作順序	LIFO（後進先出）	FIFO（先進先出）
插入端	頂端	尾端
移除端	頂端	前端
適用場景	遞迴、字元反轉、括號驗證	排隊、排程、輸出緩衝器

---

Stack 是一種輕量且實用的資料結構，尤其適合處理需要暫存與反向處理的邏輯。進一步可延伸至雙向堆疊、限制容量堆疊（Bounded Stack）等變化結構。