编辑“︁栈结构”︁

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

== 基本概念 ==  
=== 栈的特性 ===  
栈的核心特性如下：  
* '''后进先出（LIFO）'''：最后入栈的元素最先被移除。  
* '''操作受限'''：只能在栈顶进行插入（Push）和删除（Pop）操作。  
* '''动态大小'''：栈的大小可随元素增减动态变化（除非实现为固定大小的栈）。  

=== 栈的操作 ===  
栈支持以下基本操作：  
* '''Push(x)'''：将元素 x 压入栈顶。  
* '''Pop()'''：移除并返回栈顶元素（若栈非空）。  
* '''Peek() / Top()'''：返回栈顶元素但不移除。  
* '''isEmpty()'''：检查栈是否为空。  
* '''size()'''：返回栈中元素数量。  

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

=== 基于数组的实现 ===  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

=== 基于链表的实现 ===  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

== 栈的复杂度分析 ==  
{| class="wikitable"  
|+ 时间复杂度（平均情况）  
! 操作 !! 数组实现 !! 链表实现  
|-  
| Push || <math>O(1)</math> || <math>O(1)</math>  
|-  
| Pop || <math>O(1)</math> || <math>O(1)</math>  
|-  
| Peek || <math>O(1)</math> || <math>O(1)</math>  
|}  

== 实际应用案例 ==  
=== 1. 函数调用栈 ===  
程序执行时，函数调用通过栈管理：  
* 调用函数时，其返回地址和局部变量压入栈。  
* 函数返回时，栈顶帧弹出。  

=== 2. 括号匹配 ===  
检查表达式中的括号是否成对出现：  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

=== 3. 浏览器历史记录 ===  
浏览器的“后退”按钮使用栈存储访问记录：  
* 每次访问新页面时，URL 压入栈。  
* 点击“后退”时，弹出栈顶 URL 并加载前一个页面。  

== 栈的可视化 ==  
<mermaid>  
graph LR  
    A[Push 10] --> B[栈: 10]  
    C[Push 20] --> D[栈: 20, 10]  
    D --> E[Pop → 20]  
    E --> F[栈: 10]  
</mermaid>  

== 进阶主题 ==  
=== 单调栈 ===  
用于解决“下一个更大元素”类问题：  
<syntaxhighlight lang="python">  
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]  
</syntaxhighlight>  

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

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

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

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