栈与队列 (Stack and Queue)
栈与队列 (Stack & Queue)
栈和队列是两种基础的线性数据结构,分别遵循LIFO(后进先出)和FIFO(先进先出)原则。
基础概念
栈(Stack)
操作示意:
Push 1: | 1 | Pop: | 3 |
----- | 2 |
| 1 |
Push 2: | 2 | -----
| 1 |
-----
Push 3: | 3 |
| 2 |
| 1 |
-----
基本操作:
- push(x): 将元素x压入栈顶
- pop(): 移除并返回栈顶元素
- top(): 返回栈顶元素但不移除
- isEmpty(): 检查栈是否为空
应用场景:
- 函数调用栈
- 表达式求值
- 括号匹配
- 深度优先搜索
- 撤销操作
队列(Queue)
基本队列:
Enqueue: 1 -> 2 -> 3 Front: 1 Rear: 3
Dequeue: 2 -> 3 Front: 2 Rear: 3
循环队列:
Front
↓
[1] [2] [3] [4] [ ] [ ]
↑
Rear
基本操作:
- enqueue(x): 将元素x加入队尾
- dequeue(): 移除并返回队首元素
- front(): 返回队首元素但不移除
- isEmpty(): 检查队列是否为空
应用场景:
- 任务调度
- 广度优先搜索
- 缓冲区管理
- 消息队列
经典问题
1. 有效的括号
LeetCode 20 - Valid Parentheses
使用栈匹配括号:
输入: ( { [ ] } )
步骤1: ( | ( |
步骤2: ({ | ({ |
步骤3: ({[ |({[ |
步骤4: ({[] |({ | 匹配 ]
步骤5: ({[]} | ( | 匹配 }
步骤6: ({[]}) | | 匹配 )
def isValid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '({[':
stack.append(char)
elif char in ')}]':
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
2. 用栈实现队列
LeetCode 232 - Implement Queue using Stacks
使用两个栈实现队列:
入队 3,2,1:
栈1: | 1 | 栈2: | |
| 2 | | |
| 3 | | |
----- -----
出队操作时翻转到栈2:
栈1: | | 栈2: | 3 |
| | | 2 |
| | | 1 |
----- -----
class MyQueue:
def __init__(self):
self.s1 = [] # 用于入队
self.s2 = [] # 用于出队
def push(self, x):
self.s1.append(x)
def pop(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
3. 滑动窗口最大值
LeetCode 239 - Sliding Window Maximum
使用双端队列(单调队列):
数组: [1, 3, -1, -3, 5, 3, 6, 7] 窗口大小: 3
步骤1: [1 3 -1] -3 5 3 6 7 最大值: 3
队列: [3, -1]
步骤2: 1 [3 -1 -3] 5 3 6 7 最大值: 3
队列: [3, -1, -3]
步骤3: 1 3 [-1 -3 5] 3 6 7 最大值: 5
队列: [5]
步骤4: 1 3 -1 [-3 5 3] 6 7 最大值: 5
队列: [5, 3]
def maxSlidingWindow(nums, k):
from collections import deque
result = []
q = deque() # 存储下标
for i in range(len(nums)):
# 移除窗口左侧超出范围的元素
if q and q[0] < i - k + 1:
q.popleft()
# 移除所有小于当前元素的值
while q and nums[q[-1]] < nums[i]:
q.pop()
q.append(i)
# 当窗口形成时添加结果
if i >= k - 1:
result.append(nums[q[0]])
return result
4. 最小栈
使用辅助栈跟踪最小值:
操作序列:
push(3): 主栈 |3| 最小栈 |3|
push(2): 主栈 |2|3| 最小栈 |2|3|
push(5): 主栈 |5|2|3| 最小栈 |2|2|3|
pop(): 主栈 |2|3| 最小栈 |2|3|
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
高级主题
单调栈
- 用于解决下一个更大/更小元素问题
- 栈内元素保持单调递增或递减
- 示例问题:LeetCode 739 - Daily Temperatures
单调队列
- 用于维护滑动窗口中的最大/最小值
- 队列元素保持单调性
- 示例问题:上述滑动窗口最大值
优先队列(堆)
- 能够在O(1)时间获取最大/最小值
- 插入和删除操作为O(log n)
- 示例问题:LeetCode 215 - Kth Largest Element
常见技巧
- 使用栈处理括号和嵌套结构
- 使用队列进行层次遍历
- 双栈实现队列,双队列实现栈
- 单调栈解决下一个更大元素
- 优先队列处理第K个元素
相关题目
- LeetCode 394 - Decode String
- LeetCode 739 - Daily Temperatures
- LeetCode 225 - Implement Stack using Queues
- LeetCode 503 - Next Greater Element II
- LeetCode 215 - Kth Largest Element in an Array