编辑“︁栈与队列”︁（章节）

= 栈与队列 =
'''栈（Stack）'''与'''队列（Queue）'''是两种重要的线性数据结构，其核心区别在于'''元素访问顺序'''的规则不同。栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。

== 栈（Stack） ==
=== 基本概念 ===
栈是一种仅允许在'''一端（称为栈顶）'''进行插入（压栈）和删除（弹栈）操作的线性表。其操作特性可类比摞盘子的过程：最后放入的盘子最先被取出。

'''核心操作：'''
* '''push(x)'''：将元素x压入栈顶
* '''pop()'''：移除并返回栈顶元素
* '''peek()'''：返回栈顶元素但不移除
* '''isEmpty()'''：检查栈是否为空

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

=== 代码实现 ===
以下是Python中使用列表实现栈的示例：

<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("弹出空栈")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("查看空栈")

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

# 示例使用
stack = Stack()
stack.push(10)  # 栈: [10]
stack.push(20)  # 栈: [10, 20]
print(stack.pop())  # 输出: 20
print(stack.peek()) # 输出: 10
</syntaxhighlight>

=== 实际应用 ===
1. '''函数调用栈'''：程序执行时保存函数调用上下文
2. '''括号匹配'''：检查代码中的括号是否成对出现
3. '''撤销操作'''（Undo）：文本编辑器的撤销功能使用栈存储操作历史

== 队列（Queue） ==
=== 基本概念 ===
队列是一种允许在'''队尾（rear）插入'''、在'''队首（front）删除'''的线性表。其操作特性类比排队购票：先来的人先获得服务。

'''核心操作：'''
* '''enqueue(x)'''：将元素x加入队尾
* '''dequeue()'''：移除并返回队首元素
* '''front()'''：获取队首元素但不移除
* '''isEmpty()'''：检查队列是否为空

<mermaid>
graph LR
    A[队首] --> B[元素1]
    B --> C[元素2]
    C --> D[元素3]
    D --> E[队尾]
</mermaid>

=== 代码实现 ===
Python中使用<code>collections.deque</code>实现高效队列：

<syntaxhighlight lang="python">
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        raise IndexError("空队列出队")

    def front(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("查看空队列")

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

# 示例使用
q = Queue()
q.enqueue("A")  # 队列: ["A"]
q.enqueue("B")  # 队列: ["A", "B"]
print(q.dequeue())  # 输出: "A"
print(q.front())    # 输出: "B"
</syntaxhighlight>

=== 变体队列 ===
* '''双端队列（Deque）'''：两端都可进行插入删除操作
* '''优先队列（Priority Queue）'''：元素按优先级出队
* '''循环队列'''：解决普通队列的假溢出问题

=== 实际应用 ===
1. '''任务调度'''：操作系统中的进程调度队列
2. '''消息队列'''：分布式系统中的异步通信
3. '''BFS算法'''：广度优先搜索使用队列存储待访问节点

== 复杂度分析 ==
{| class="wikitable"
|+ 操作时间复杂度对比
! 操作 !! 栈（平均） !! 队列（平均）
|-
| 插入 || <math>O(1)</math> || <math>O(1)</math>
|-
| 删除 || <math>O(1)</math> || <math>O(1)</math>
|-
| 访问顶部/首部 || <math>O(1)</math> || <math>O(1)</math>
|-
| 搜索 || <math>O(n)</math> || <math>O(n)</math>
|}

== 经典问题 ==
=== 用栈实现队列 ===
使用两个栈模拟队列操作：
<syntaxhighlight lang="python">
class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x):
        self.in_stack.append(x)

    def pop(self):
        self._transfer()
        return self.out_stack.pop()

    def _transfer(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
</syntaxhighlight>

=== 括号有效性检验 ===
栈的典型应用——检查括号是否匹配：
<syntaxhighlight lang="python">
def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack
</syntaxhighlight>

{{Tip|在算法面试中，栈和队列相关题目出现频率极高，建议熟练掌握它们的特性和相互转换方法。}}

== 延伸思考 ==
* 递归调用本质上是栈的应用
* 多级反馈队列（MLFQ）如何结合多种队列特性？
* 栈在编译器语法分析中的作用

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:数据结构基础]]