堆疊是一個遵循後進先出 (Last In First Out, LIFO) 的線性資料結構，表示最後放進去的資料會最先被取出。例如有一個羽球罐，不斷往裡面塞入羽球，而最後一顆被塞入的球，下次打球時會最先被拿出來（除非用倒的）。
堆疊操作
通常實作堆疊時，會建立以下幾個方法：
- 入堆 (push)：將元素放入堆頂
- 出堆 (pop)：將堆頂元素移除並回傳
- 頂元素 (peek)：查看堆頂元素（不會移除）
| 操作 |
時間複雜度 |
push() |
$\mathcal{O}(1)$ |
pop() |
$\mathcal{O}(1)$ |
peek() |
$\mathcal{O}(1)$ |
堆疊操作釋疑
為何不抽中間的東西呢？
原因在於如果直接抽取中間的元素，會破壞整體順序。假設要提取中間的元素，就必須先把該元素上面的所有元素全部暫存到另一個地方，提取後再將這些元素放回。此時有幾個問題：
- 暫存到另一個地方會增加空間複雜度，記憶體配置會更多，並非我們所樂見的狀況。
- 將元素放回後，原本的索引會因此而改變，堆疊的結構被破壞了。
實作訪問頂端元素的目的是什麼？
可以舉個簡單的例子，假設有個程式用來處理網站請求，請求會放到堆疊中排隊處理。假設有段程式碼會運作如下：
1
2
| if stack[-1] == 'shutdown':
|
如果改為
1
2
| if stack.pop() == 'shutdown':
|
因為 pop() 會把元素刪除並回傳該值，那麼就會誤刪。事實上我們只是想要檢查頂端元素而已，這種「看一眼」但不動資料的行為，就是 peek 的用處。
堆疊功能
堆疊非常適合處理最近加入的任務，因為這些任務是最容易被取出的，毋需翻動前面的元素，僅處理工作堆中頂端那一層。因此，如果撰寫程式時，遇到「最後一個進來、最先處理」的情境，就適合使用堆疊。
呼叫堆疊 (call stack)
呼叫堆疊是一種來記錄目前程式在執行時函式的呼叫順序與執行狀態。
每當一個函式被呼叫時，系統就會把它的執行狀態放進堆疊中；當它執行完畢後，會從 stack 移除，然後回到呼叫它的那一層繼續執行。
- 函式可能呼叫函式，會產生巢狀邏輯
- 程式要記得呼叫者的位置與暫存資料
- 多個函式同時存在時，彼此不能干擾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def A():
print("Enter A")
B()
print("Exit A")
def B():
print("Enter B")
C()
print("Exit B")
def C():
print("Enter C")
A()
|
| 時間點 | 呼叫堆疊內容 | 執行動作 |
|---|
| 1 | A() | 呼叫 A |
| 2 | A() → B() | A 呼叫 B |
| 3 | A() → B() → C() | B 呼叫 C |
| 4 | A() → B() | C 執行完畢 → pop 掉 C |
| 5 | A() | B 執行完畢 → pop 掉 B |
| 6 | （空） | A 執行完畢 → pop 掉 A |
堆疊實作
由於堆疊僅能在堆頂新增或刪除元素的性質，實踐上其實較為容易，而實作堆疊的資料結構非陣列與鏈結串列莫屬，原因是這兩者可以在任意增刪元素，因此堆疊可以視為是受限制的陣列或鏈結串列。
使用鏈結串列
鏈結串列有頭節點與尾節點，分別對應到堆頂與堆底。因此入堆即是將元素插入頭節點，出堆則是移除頭節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class LinkedListStack:
def __init__(self):
self._peek: ListNode | None = None
self._size = 0
def size(self) -> int:
return self._size
def is_empty(self) -> bool:
return self.size() == 0
def push(self, val: int) -> None:
node = ListNode(val)
node.next = self._peek
self._peek = node
self._size += 1
def pop(self) -> int:
num = self.peek()
self._peek = self._peek.next
self._size -= 1
return num
def peek(self) -> int:
if self.is_empty():
raise ValueError("堆疊為空")
return self._peek.val
|
使用陣列
若以陣列表示，就需要一點想像力。當元素逐一放入陣列後，堆底其實是元素的第一個元素，堆頂則為最後一個元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class ArrayStack:
def __init__(self):
self._stack: list[int] = []
def size(self) -> int:
return len(self._stack)
def is_empty(self) -> bool:
return self.size == 0
def push(self, val: int) -> None:
self._stack.append(val)
def pop(self) -> int:
if self.is_empty():
raise ValueError("堆疊為空")
return self._stack.pop()
def peek(self) -> int:
if self.is_empty():
raise ValueError("堆疊為空")
return self._stack[-1]
|
練習題
給一個只包含 (、)、{、}、[、] 的字串 s，請判斷此字串中的括號是否成對配對且順序正確。有效的定義如下：
- 左括號必須由相同類型的右括號閉合。
- 括號必須以正確順序閉合。
1
2
3
| 輸入: s = "({[]})"
輸出: True
原因: 每個左括號都有正確的右括號以正確順序配對
|
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in range(len(s)):
if s[i] == "(" or s[i] == "{" or s[i] == "[":
stack.append(s[i])
else:
if stack and ((stack[-1] == "(" and s[i] == ")") or
(stack[-1] == "{" and s[i] == "}") or
(stack[-1] == "[" and s[i] == "]")):
stack.pop()
else:
return False
return not stack
|
實作一個支援下列操作的堆疊 (MinStack)：
push(x)：將 x 推入堆疊pop()：移除堆疊頂端元素top()：取得堆疊頂端元素getMin()：取得目前堆疊中的最小值（常數時間）
1
2
3
4
5
6
7
8
9
10
11
12
13
| 輸入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出: [null,null,null,null,-3,null,0,-2]
理由:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
|
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class MinStack:
def __init__(self):
self._stack = []
self._min_stack = []
def push(self, val: int) -> None:
self._stack.append(val)
if not self._min_stack:
self._min_stack.append(val)
else:
curr_min = self._min_stack[-1]
self._min_stack.append(min(curr_min, val))
def pop(self) -> None:
self._stack.pop()
self._min_stack.pop()
def top(self) -> int:
return self._stack[-1]
def getMin(self) -> int:
return self._min_stack[-1]
|