栈与队列

栈与队列

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

栈（Stack）

基本概念

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

核心操作：

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

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

代码实现

以下是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

实际应用

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

队列（Queue）

基本概念

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

核心操作：

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

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

代码实现

Python中使用collections.deque实现高效队列：

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"

变体队列

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

实际应用

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

复杂度分析

操作时间复杂度对比

操作	栈（平均）	队列（平均）
插入	$O(1)$	$O(1)$
删除	$O(1)$	$O(1)$
访问顶部/首部	$O(1)$	$O(1)$
搜索	$O(n)$	$O(n)$

经典问题

用栈实现队列

使用两个栈模拟队列操作：

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())

括号有效性检验

栈的典型应用——检查括号是否匹配：

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

延伸思考

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