编辑“︁栈的实现方式”︁

{{Note|本文介绍栈的多种实现方式，适合初学者及需要复习基础的程序员。所有代码示例均提供详细解释和测试用例。}}

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

== 基本概念 ==
栈的核心操作包括：
* <code>push(item)</code>：元素入栈
* <code>pop()</code>：移除并返回栈顶元素
* <code>peek()</code>：查看栈顶元素（不移除）
* <code>is_empty()</code>：判断栈是否为空

<mermaid>
graph LR
    A[栈顶] --> B[元素1]
    B --> C[元素2]
    C --> D[...]
    D --> E[元素n]
</mermaid>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

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

<syntaxhighlight lang="java">
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;
    }
}
</syntaxhighlight>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

时间复杂度分析：
* 均摊<math>O(1)</math>时间复杂度的push操作

=== 4. 语言内置实现 ===
主流语言均提供栈的实现：

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

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

<syntaxhighlight lang="cpp">
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();
}
</syntaxhighlight>

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

<mermaid>
sequenceDiagram
    用户->>浏览器: 访问页面A
    浏览器->>历史栈: push(A)
    用户->>浏览器: 访问页面B
    浏览器->>历史栈: push(B)
    用户->>浏览器: 点击后退
    浏览器->>历史栈: pop() → 返回A
</mermaid>

== 复杂度对比 ==
{| class="wikitable"
|+ 不同实现方式对比
! 实现方式 !! 入栈时间复杂度 !! 出栈时间复杂度 !! 空间复杂度
|-
| 固定数组 || <math>O(1)</math> || <math>O(1)</math> || <math>O(n)</math>
|-
| 链表 || <math>O(1)</math> || <math>O(1)</math> || <math>O(n)</math>
|-
| 动态数组 || 均摊<math>O(1)</math> || <math>O(1)</math> || <math>O(n)</math>
|}

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]