栈

栈是一种线性数据结构，遵循后进先出 (LIFO) 原则。想象一叠盘子：最后放上去的盘子是第一个被取走的。在栈中，所有的插入和删除操作都发生在同一端，这一端被称为栈的“顶部”。

基本操作及其复杂度

操作	描述	时间复杂度
推入 (Push)	将元素添加到栈顶	$O(1)$
弹出 (Pop)	从栈顶移除元素	$O(1)$
查看栈顶元素 (Peek)	返回栈顶元素而不将其移除	$O(1)$
判断是否为空 (isEmpty)	检查栈是否为空	$O(1)$
判断是否已满 (isFull)	检查栈是否已满（对于有界栈）	$O(1)$

栈的实现

使用链表

在基于链表的栈中，头节点代表栈的顶部。元素从头部添加和移除，确保常数时间操作。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedListStack:
    def __init__(self):
        self._top = None
        self._size = 0

    def size(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._top is None

    def push(self, val: int):
        node = ListNode(val, self._top)
        self._top = node
        self._size += 1

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        val = self._top.val
        self._top = self._top.next
        self._size -= 1
        return val

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._top.val

    def to_list(self) -> list[int]:
        arr = []
        current = self._top
        while current:
            arr.append(current.val)
            current = current.next
        arr.reverse()
        return arr

使用数组（列表）

在基于数组的栈中，数组的末尾被视为栈的顶部。元素从末尾添加和移除，使得推入和弹出操作高效。

class ArrayStack:
    def __init__(self):
        self._stack = []

    def size(self) -> int:
        return len(self._stack)

    def is_empty(self) -> bool:
        return not self._stack

    def push(self, item: int):
        self._stack.append(item)

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack.pop()

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack[-1]

    def to_list(self) -> list[int]:
        return self._stack.copy()

两种实现的比较

支持的操作

两种实现都支持所有标准的栈操作，并且具有相同的时间复杂度。基于数组的栈允许索引访问，但在栈的使用中，随机访问并不常见。

时间效率

基于数组的实现：
- 推入和弹出： 通常更快，因为缓存性能更好。
- 调整大小开销： 可能需要调整数组大小，导致偶尔的 $O(n)$ 操作。然而，对于动态数组，此成本会在多次操作中被摊销。
基于链表的实现：
- 推入和弹出： 始终保持 $O(1)$ 时间，无需调整大小。
- 开销： 由于每个节点的动态内存分配，速度略慢。

空间效率

基于数组的实现：
- 内存使用： 由于预分配和调整大小策略，可能会分配比实际需要更多的内存。
- 每个元素的开销： 最小，因为只存储数据。
基于链表的实现：
- 内存使用： 仅使用元素所需的精确内存量。
- 每个元素的开销： 每个节点需要额外的指针内存。

优缺点

优点

简单性： 易于实现和理解。
效率： 推入和弹出操作的时间复杂度为 $O(1)$ 。
内存管理： 对于管理函数调用和局部变量非常有用，尤其是在递归算法中。

缺点

访问受限： 只能直接访问栈顶元素。
固定大小（基于数组）： 除非实现动态调整大小，否则可能导致溢出。
内存开销（基于链表）： 需要额外的指针内存。

应用场景

表达式求值： 评估后缀或前缀表达式。
表达式转换： 将中缀表达式转换为后缀或前缀表达式。
语法解析： 用于编译器的语法检查。
回溯： 在软件中实现撤销操作。
内存管理： 在递归编程中管理函数调用。
深度优先搜索 (DFS)： 用于图遍历算法。

示例：括号平衡

栈用于检查表达式中的括号是否平衡。

def is_balanced(expression: str) -> bool:
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    for char in expression:
        if char in pairs:
            stack.append(char)
        elif char in pairs.values():
            if not stack or pairs[stack.pop()] != char:
                return False
    return not stack

# Example usage
expression = "{[()()]}"
print(is_balanced(expression))  # Output: True

解释：

初始化： 使用一个空列表 stack 来模拟栈的行为。
迭代： 对于表达式中的每个字符：
- 左括号： 如果字符是左括号，将其推入栈中。
- 右括号： 如果是右括号，检查栈顶是否匹配。如果不匹配，则返回 False。
完成： 处理结束后，如果栈为空，则表达式是平衡的。

基本操作及其复杂度​

栈的实现​

使用链表​

使用数组（列表）​

两种实现的比较​

支持的操作​

时间效率​

空间效率​

优缺点​

优点​

缺点​

应用场景​

示例：括号平衡​