栈的实现方式[编辑 | 编辑源代码]

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。本节将详细讲解栈的四种主流实现方式：数组实现、链表实现、动态扩容实现及语言内置实现。

基本概念[编辑 | 编辑源代码]

栈的核心操作包括：

push(item)：元素入栈
pop()：移除并返回栈顶元素
peek()：查看栈顶元素（不移除）
is_empty()：判断栈是否为空

实现方式[编辑 | 编辑源代码]

1. 数组实现[编辑 | 编辑源代码]

固定大小的数组是最简单的栈实现方式，适合已知最大容量的场景。

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1  # 栈顶指针

    def push(self, item):
        if self.top == self.capacity - 1:
            raise Exception("Stack Overflow")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise Exception("Stack Underflow")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            return None
        return self.stack[self.top]

    def is_empty(self):
        return self.top == -1

# 测试用例
stack = ArrayStack(3)
stack.push(10)  # 栈: [10]
stack.push(20)  # 栈: [10, 20]
print(stack.pop())  # 输出: 20

2. 链表实现[编辑 | 编辑源代码]

使用链表可避免固定大小的限制，但需要额外存储指针空间。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class LinkedStack {
    private ListNode top;

    public void push(int item) {
        ListNode newNode = new ListNode(item);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (top == null) throw new RuntimeException("Empty Stack");
        int val = top.val;
        top = top.next;
        return val;
    }

    public int peek() {
        if (top == null) throw new RuntimeException("Empty Stack");
        return top.val;
    }
}

3. 动态扩容实现[编辑 | 编辑源代码]

当数组空间不足时自动扩容（通常2倍增长），是工业级实现方案。

class DynamicStack:
    def __init__(self):
        self.stack = []
        self.capacity = 1

    def push(self, item):
        if len(self.stack) == self.capacity:
            self._resize(2 * self.capacity)
        self.stack.append(item)

    def _resize(self, new_capacity):
        new_stack = [None] * new_capacity
        for i in range(len(self.stack)):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

时间复杂度分析：

均摊 $O (1)$ 时间复杂度的push操作

4. 语言内置实现[编辑 | 编辑源代码]

主流语言均提供栈的实现：

// JavaScript数组直接作为栈使用
const stack = [];
stack.push(1);  // 入栈
stack.pop();    // 出栈

应用案例[编辑 | 编辑源代码]

案例1：括号匹配检查 检查表达式中的括号是否成对出现：

bool isBalanced(const string& expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[') s.push(c);
        else if (c == ')') {
            if (s.empty() || s.top() != '(') return false;
            s.pop();
        }
        // 其他括号类型类似处理...
    }
    return s.empty();
}

案例2：浏览器历史记录 浏览器的后退功能使用栈存储访问记录：

复杂度对比[编辑 | 编辑源代码]

不同实现方式对比
实现方式	入栈时间复杂度	出栈时间复杂度	空间复杂度
固定数组	$O (1)$	$O (1)$	$O (n)$
链表	$O (1)$	$O (1)$	$O (n)$
动态数组	均摊 $O (1)$	$O (1)$	$O (n)$

常见问题[编辑 | 编辑源代码]

Q：何时选择数组实现而非链表实现？ A：当栈大小可预估且需要更快的随机访问时选择数组实现。

Q：动态扩容的实现为什么是2倍增长？ A：2倍扩容能在时间复杂度和空间浪费之间取得平衡（1.5倍也是常见选择）。