Stack (堆疊) 是一種受限的線性資料結構，遵循先進後出 (Last-In-First-Out; LIFO) 的資料結構。你可想像有一疊盤子，最後放上去的盤子會最先被拿走，所以 Stack 只允許在「頂端」進行操作，簡單來說就是你不能看或是取非最上層的元素。

Stack 的基本操作

Stack 的操作相較 Linked List 簡單很多，因為他只能對頂端進行操作，常見的操作如下:

• push: 將元素放到 Stack 頂端
• pop: 將 Stack 頂端的元素移除並回傳 (取走)
• peek/top: 查看堆疊頂端的元素，但不移除
• is_empty: 檢查堆疊是否為空

自己建立一個 Stack

直接使用 Python 來自定義一個 Stack 的資料結構

• Create a Stack class

  起手式跟昨天一樣，建立建構子與實作 iter，透過 Python 的 list 來模擬。

class Stack:
    def __init__(self):
        self.data = []

    def __iter__(self):
        for item in reversed(self.data):
            yield item

• Create a push() method

  Stack 添加元素無法像 Linked List 有那麼多的操作，他一律只能放在最上面，可以想像一下，其實就是把元素加在最後面，再把 list 轉 90 度。

class Stack:
    def __init__(self):
        self.data = []

    def __iter__(self):
        for item in reversed(self.data):
            yield item
    
    def push(self, item):
	    self.data.append(item)

• Create a pop() method

  Stack 中的 pop() 就是把最上面的元素拿走，而且可以同時回傳被拿走的這個元素是什麼，就直接使用 list 中的 pop()。

class Stack:
    def __init__(self):
        self.data = []

    def __iter__(self):
        for item in reversed(self.data):
            yield item
    
    def push(self, item):
	    self.data.append(item)

    def pop(self):
        return self.data.pop()

• Create a peek() method

  Stack 中的 peek() 就是只看不拿，看最上面的元素是什麼，但是不把它拿走。

class Stack:
    def __init__(self):
        self.data = []

    def __iter__(self):
        for item in reversed(self.data):
            yield item
    
    def push(self, item):
	    self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

• Create an is_empty() method

  單純的檢查 Stack 是否為空。

class Stack:
    def __init__(self):
        self.data = []

    def __iter__(self):
        for item in reversed(self.data):
            yield item
    
    def push(self, item):
	    self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]
        
    def si_empty(self):
        return self.data == []

LeetCode

• LeetCode 20. Valid Parentheses

結語

今天介紹了 Stack，這是一種限制操作位置的線性資料結構，只能在頂端進行 push、pop、peek 等操作。雖然結構簡單，但它的應用場景極為廣泛，例如函式呼叫的呼叫堆疊 (call stack)、瀏覽器的返回功能、文字編輯器的復原 (Undo) 機制，以及括號匹配等演算法題。

實作上，Python 可以直接用 list 或 collections.deque 模擬，Java 則常用 ArrayDeque 取代傳統的 Stack 類別。無論哪種語言，Stack 的特性都一樣: 後進先出 (LIFO)，存取效率高 (大部分操作為 $O(1)$)。

掌握 Stack 的核心概念後，你會更容易理解 Queue (佇列)，因為它與 Stack 一樣是線性結構，但遵循的則是 先進先出 (FIFO) 規則。