前言

在程式設計與演算法學習的過程中，堆疊（Stack）是必不可少的資料結構。它簡單卻強大，廣泛應用於函數呼叫管理、字串處理、復原功能以及數學表達式計算。若把資料結構比喻為建築工法，那麼堆疊就是最常見的「模板」，學會它能讓你更容易理解後續更複雜的資料結構與演算法。

堆疊的核心概念

什麼是堆疊？

堆疊是一種線性資料結構，只允許在「頂部」進行操作。這意味著：

• Push（推入）：將元素添加到頂部
• Pop（彈出）：移除頂部元素並返回其值
• Peek（查看）：檢視頂部元素但不移除

日常生活中的例子包括：

• 書桌上的書堆
• 餐廳裡疊放的盤子
• 軟體中的復原（Undo）與重做（Redo）功能

三大基本操作

1. Push 推入
   • 將新元素加入堆疊頂部
   • 新元素成為新的頂部
   • 堆疊大小增加
2. Pop 彈出
   • 移除並返回堆疊頂部元素
   • 堆疊大小減少
3. Peek 查看
   • 返回頂部元素的值，但不移除
   • 堆疊內容保持不變

建立基礎 Stack 類別

首先建立 Stack 類別，並初始化頂部節點：

class Stack:
    def __init__(self):
      self.top_item = None

此時，top_item 追蹤堆疊的頂部節點，初始狀態為空。

實作 Peek 方法

peek() 方法讓我們能夠查看堆疊頂部的值，而不會改變堆疊的內容。這在我們需要檢查下一個要處理的項目時特別有用。

def peek(self):
    return self.top_item.get_value()

實作 Push 操作

將元素添加到堆疊頂部

push() 方法是堆疊最重要的操作之一。它將新的元素添加到堆疊的頂部，並正確地重新鏈接所有節點。

實作步驟：

1. 建立新的 Node 實例
2. 設定新節點的 next 指向當前頂部
3. 更新 top_item 為新節點

def push(self, value):
    item = Node(value)
    item.set_next_node(self.top_item)
    self.top_item = item

實作 Pop 操作

pop() 方法從堆疊頂部移除元素並返回其值。這是一個具有破壞性的操作，會永久改變堆疊的內容。

保存要移除的項目

將當前的 top_item 儲存到 item_to_remove 變數中

更新頂部指標

將 top_item 設定為 item_to_remove 的下一個節點

返回移除的值

使用 get_value() 方法返回被移除元素的值

def pop(self):
 item_to_remove = self.top_item
 self.top_item = item_to_remove.get_next_node()
 return item_to_remove.get_value()

為什麼需要控制大小？

在實際應用中，記憶體是有限的資源。如果我們不限制堆疊的大小，程式可能會：

• 消耗過多記憶體
• 導致系統效能下降
• 引發堆疊溢位錯誤
• 造成程式崩潰

因此，我們加入追蹤機制：

def __init__(self, limit=1000):
    self.top_item = None
    self.limit = limit
    self.size = 0

改良後的方法

Push

def push(self, value):
    if self.has_space():
        item = Node(value)
        item.set_next_node(self.top_item)
        self.top_item = item
        self.size += 1
    else:
        print("空間不足！")

Pop

def pop(self):
    if not self.is_empty():
        item_to_remove = self.top_item
        self.top_item = item_to_remove.get_next_node()
        self.size -= 1
        return item_to_remove.get_value()
    else:
        print("堆疊為空！")

Peek

def peek(self):
    if not self.is_empty():
        return self.top_item.get_value()
    else:
        print("堆疊為空！")

結語

堆疊雖然是一種基礎資料結構，但它在程式世界中的地位卻相當關鍵。從函數呼叫堆疊到軟體的復原功能，甚至演算法中的表達式運算與括號檢查，堆疊都扮演著核心角色。