6.1 堆疊的定義及其特性
堆疊 是一種抽象的資料結構，代表一組依照 "後進先出" (Last In, First Out, LIFO) 原則組織的元素集合。堆疊可以像一疊書一樣：最後加入的書在頂部，會最先被移走/取走。
堆疊的特性：
- LIFO (Last In, First Out): 最後添加的元素最先提取。
- 有限操作： 堆疊僅支援添加 (push)、刪除 (pop) 和查看 (peek) 頂部元素。
- 單向訪問： 只能從堆疊頂部訪問元素。
- 實現簡單： 堆疊可以輕鬆通過數組或連結清單實現。
- 記憶體管理： 可以以相反順序存儲和提取臨時數據或狀態。
LIFO 原則運作：
- 添加元素 (push): 新元素添加到堆疊頂部。
- 刪除元素 (pop): 最後添加的元素從堆疊頂部刪除。
- 查看頂部 (peek): 可以看到頂部的元素而不將其刪除。
堆疊的元素僅從一側添加和刪除，這一側被稱為頂部 (top)。因此，最後添加的元素總是在頂部，並將最先被移除。
6.2 主要操作
主要操作： push, pop, peek
操作 push: 在堆疊頂部添加新元素。
時間複雜度： O(1)。
使用 Python 中的 list 類模擬堆疊的示例：
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # 輸出: [10, 20]
操作 pop: 刪除並返回堆疊頂部的元素。
時間複雜度： O(1)。
使用 Python 中的 list 類模擬堆疊的示例：
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # 輸出: 20
print(stack) # 輸出: [10]
操作 peek: 返回堆疊頂部的元素而不將其刪除。
時間複雜度： O(1)。
實現範例：
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # 輸出: 10
6.3 堆疊的使用示例
讓我們來看看一些堆疊的使用例子：
函數調用管理
在 Python 中，堆疊用來在程序執行期間跟蹤函數。每當調用一個函數時，其返回地址和本地變量會被放入堆疊中。當函數完成執行時，控制權返回到調用它的函數，並將數據從堆疊中提取。
堆疊調用的使用示例：
在這個範例中，遞迴調用函數 factorial 使用調用堆疊來存儲每次調用的狀態，直到達到基本條件 (n == 1)。
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 輸出: 120
操作撤銷 (Undo)
堆疊用於文本編輯器和其他應用程式的操作撤銷功能。當用戶執行一個操作時，它會被保存到堆疊中。當執行 Undo 操作時，最後一個操作會從堆疊中提取並被撤銷。
使用堆疊實現操作撤銷的示例：
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# 使用範例：
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # 輸出: "Hello World"
editor.undo()
print(editor.text) # 輸出: "Hello"
editor.undo()
print(editor.text) # 輸出: ""
GO TO FULL VERSION