棧：先進後出的數據結構

一、棧的基本定義

棧(Stack)是一種線性數據結構，它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據(最後入棧的數據最先彈出)。棧可以簡單地看做是一種限制性的單向鏈表，它限制了只能在鏈表的一端進行插入和刪除操作，這一端稱之為棧頂(top)，另一端稱之為棧底(bottom)。

二、棧的操作

對棧的操作主要有兩個：壓入和彈出。在棧中壓入元素的操作稱為push，而彈出元素的操作稱為pop。

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

    def push(self, item):
        # 壓入元素
        self.stack.append(item)

    def pop(self):
        # 彈出元素
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        # 返回棧頂元素
        if not self.is_empty():
            return self.stack[-1]

    def size(self):
        # 返回棧大小
        return len(self.stack)

    def is_empty(self):
        # 判斷棧是否為空
        return len(self.stack) == 0

三、棧的應用

1. 表達式求值

棧可以用來求表達式的值，由於表達式的優先級問題，我們需要把中綴表達式轉化為後綴表達式。比如a+b*c-d，可以轉化為abc*+d-

def evaluate_postfix_expression(expression: str) -> int:
    stack = Stack()
    for i in expression:
        if i.isdigit():
            stack.push(i)
        else:
            num2, num1 = int(stack.pop()), int(stack.pop())
            if i == '+':
                stack.push(num1 + num2)
            elif i == '-':
                stack.push(num1 - num2)
            elif i == '*':
                stack.push(num1 * num2)
            elif i == '/':
                stack.push(num1 / num2)
    return stack.pop()

2. 括號匹配

棧也可以用來匹配括號，比如，判斷括號序列是否合法，(()())合法，(()非法。

def is_valid_brackets(s: str) -> bool:
    stack = Stack()
    for i in s:
        if i == '(':
            stack.push(i)
        elif i == ')':
            if stack.is_empty():
                return False
            else:
                stack.pop()
    return stack.is_empty()

3. 函數調用的系統棧

函數的調用關係也可以看做是一種棧的結構，每當一個函數被調用時，系統就會在棧頂記錄下來當前的函數調用信息，同時棧指針上移一位，而在一個函數執行完以後，棧頂的函數返回並彈出，此時系統將把執行權向下移交給當前的棧頂函數。

四、棧的優缺點

1. 優點

1. 棧能夠保證基本操作的時間複雜度為O(1)。

2. 棧是一種先進後出的數據結構，特別適用於需要倒序輸出或倒序執行操作的場景。

3. 棧可以解決一些複雜的問題，比如函數調用等。

2. 缺點

1. 棧的空間固定，一旦棧滿就不能再去push數據，容易產生棧溢出的問題。

2. 棧的操作受限，只有棧頂元素可以進行操作，其他位置的元素不能進行操作。

3. 棧不支持隨機訪問，只能從棧頂往下遍歷。

五、總結

本文詳細介紹了棧的定義、操作、應用及其優缺點，棧是一種非常重要和實用的數據結構，廣泛應用於計算機科學領域。