栈结构

栈（Stack）是一种遵循后进先出（Last In, First Out, LIFO）原则的线性数据结构。栈的操作限定在栈顶进行，主要包括压栈（Push）和弹栈（Pop）两种基本操作。栈在计算机科学中应用广泛，例如函数调用、表达式求值、内存管理等场景。

基本概念

栈的特性

栈的核心特性如下：

• 后进先出（LIFO）：最后入栈的元素最先被移除。
• 操作受限：只能在栈顶进行插入（Push）和删除（Pop）操作。
• 动态大小：栈的大小可随元素增减动态变化（除非实现为固定大小的栈）。

栈的操作

栈支持以下基本操作：

• Push(x)：将元素 x 压入栈顶。
• Pop()：移除并返回栈顶元素（若栈非空）。
• Peek() / Top()：返回栈顶元素但不移除。
• isEmpty()：检查栈是否为空。
• size()：返回栈中元素数量。

栈的实现

栈可以通过数组或链表实现。以下是两种常见实现方式的代码示例：

基于数组的实现

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

    def push(self, item):  
        self.items.append(item)  

    def pop(self):  
        if not self.is_empty():  
            return self.items.pop()  
        raise IndexError("Pop from empty stack")  

    def peek(self):  
        if not self.is_empty():  
            return self.items[-1]  
        raise IndexError("Peek from empty stack")  

    def is_empty(self):  
        return len(self.items) == 0  

    def size(self):  
        return len(self.items)  

# 示例用法  
stack = Stack()  
stack.push(10)  
stack.push(20)  
print(stack.pop())  # 输出: 20  
print(stack.peek()) # 输出: 10

基于链表的实现

  
class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None  

class LinkedListStack:  
    def __init__(self):  
        self.top = None  

    def push(self, item):  
        new_node = Node(item)  
        new_node.next = self.top  
        self.top = new_node  

    def pop(self):  
        if not self.is_empty():  
            popped = self.top.data  
            self.top = self.top.next  
            return popped  
        raise IndexError("Pop from empty stack")  

    def peek(self):  
        if not self.is_empty():  
            return self.top.data  
        raise IndexError("Peek from empty stack")  

    def is_empty(self):  
        return self.top is None  

# 示例用法  
ll_stack = LinkedListStack()  
ll_stack.push(5)  
ll_stack.push(15)  
print(ll_stack.pop())  # 输出: 15

栈的复杂度分析

时间复杂度（平均情况）

操作	数组实现	链表实现
Push	$O(1)$	$O(1)$
Pop	$O(1)$	$O(1)$
Peek	$O(1)$	$O(1)$

实际应用案例

1. 函数调用栈

程序执行时，函数调用通过栈管理：

• 调用函数时，其返回地址和局部变量压入栈。
• 函数返回时，栈顶帧弹出。

2. 括号匹配

检查表达式中的括号是否成对出现：

  
def is_balanced(expr):  
    stack = []  
    mapping = {')': '(', '}': '{', ']': '['}  
    for char in expr:  
        if char in mapping.values():  
            stack.append(char)  
        elif char in mapping:  
            if not stack or stack.pop() != mapping[char]:  
                return False  
    return not stack  

print(is_balanced("{[()]}"))  # 输出: True

3. 浏览器历史记录

浏览器的“后退”按钮使用栈存储访问记录：

• 每次访问新页面时，URL 压入栈。
• 点击“后退”时，弹出栈顶 URL 并加载前一个页面。

栈的可视化

graph LR A[Push 10] --> B[栈: 10] C[Push 20] --> D[栈: 20, 10] D --> E[Pop → 20] E --> F[栈: 10]

进阶主题

单调栈

用于解决“下一个更大元素”类问题：

  
def next_greater_element(nums):  
    stack = []  
    result = [-1] * len(nums)  
    for i in range(len(nums)):  
        while stack and nums[stack[-1]] < nums[i]:  
            result[stack.pop()] = nums[i]  
        stack.append(i)  
    return result  

print(next_greater_element([4, 2, 8, 1]))  # 输出: [8, 8, -1, -1]

栈与递归

递归函数隐式使用调用栈，可显式用栈替代递归（如 DFS 的非递归实现）。

常见问题

• 栈溢出：递归过深或压栈过多导致栈空间耗尽（如无限递归）。
• 线程安全：多线程环境下需同步栈操作（如 Java 的 `ConcurrentLinkedDeque`）。

总结

栈是基础且强大的数据结构，其 LIFO 特性适合需要“撤销”或“反向处理”的场景。掌握栈的实现与应用是算法学习的关键步骤。