数据结构与算法：栈与队列

栈和队列是两种受限的线性数据结构，操作受限反而让它们在某些场景大放异彩。

一、栈（Stack）：后进先出 LIFO

栈像一摞盘子，只能在顶部操作：压入（push）、弹出（pop）、查看栈顶（peek）。

stack = []
stack.append(1)        # push
stack.append(2)
stack.pop()            # pop → 2
stack[-1]             # peek → 1

二、栈的应用

• 函数调用栈：程序执行的底层机制
• 括号匹配：编译器检查代码
• 表达式求值：后缀表达式
• 撤销功能（Undo）：编辑器、浏览器后退
• DFS 深度优先搜索

三、队列（Queue）：先进先出 FIFO

队列像排队买票，从队尾进、队头出。

from collections import deque
queue = deque()
queue.append(1)        # 入队
queue.append(2)
queue.popleft()        # 出队 → 1

Python 用 collections.deque 而非普通 list 实现队列，因为 list 的 pop(0) 是 O(n)，deque 的 popleft() 是 O(1)。

四、队列的应用

• 任务调度：操作系统的进程队列
• 消息队列：异步处理、解耦
• BFS 广度优先搜索
• 缓冲区：生产者-消费者模型

五、变体

• 双端队列（Deque）：两端都能进出
• 优先队列：按优先级出队（用堆实现）
• 循环队列：固定大小，环形缓冲

六、典型面试题

• 有效括号（栈）
• 用栈实现队列 / 用队列实现栈
• 滑动窗口最大值（双端队列）
• 最近的请求次数

七、复杂度

操作        栈      队列
入          O(1)    O(1)
出          O(1)    O(1)
查看        O(1)    O(1)
查找        O(n)    O(n)

八、小结

栈和队列看似简单，应用极广。理解"何时用栈、何时用队列"，能解决一大类算法问题。优先队列（堆）是进阶重点。