栈与队列
栈和队列是两种重要的线性数据结构，它们遵循不同的操作规则。栈遵循 LIFO（Last In First Out，后进先出），队列遵循 FIFO（First In First Out，先进先出）。掌握栈和队列的应用对于解决许多算法问题至关重要。
栈（Stack）
栈的特点
- LIFO 原则：最后进入的元素最先出来
- 基本操作：push（入栈）、pop（出栈）、peek（查看栈顶）
- 应用场景：表达式求值、括号匹配、函数调用栈、DFS
栈的实现
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
栈的应用
1. 括号匹配
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
else:
stack.append(char)
return not stack
2. 表达式求值
def evaluate_expression(tokens):
stack = []
for token in tokens:
if token in ['+', '-', '*', '/']:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
队列（Queue）
队列的特点
- FIFO 原则：最先进入的元素最先出来
- 基本操作：enqueue（入队）、dequeue（出队）、front（查看队首）
- 应用场景：BFS、任务调度、消息队列
队列的实现
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items.popleft()
def front(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
队列的应用
BFS（广度优先搜索）
def bfs(graph, start):
queue = deque([start])
visited = {start}
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
单调栈（Monotonic Stack）
单调栈是一种特殊的栈，栈中的元素保持单调性（递增或递减）。
应用场景
- 找到每个元素左边/右边第一个比它大/小的元素
- 计算最大矩形面积
- 接雨水问题
示例：找到每个元素右边第一个更大的元素
def next_greater_element(nums):
stack = []
result = [-1] * len(nums)
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
index = stack.pop()
result[index] = nums[i]
stack.append(i)
return result
示例：最大矩形面积
def largest_rectangle_area(heights):
stack = []
max_area = 0
for i, height in enumerate(heights):
while stack and heights[stack[-1]] > height:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
while stack:
h = heights[stack.pop()]
w = len(heights) if not stack else len(heights) - stack[-1] - 1
max_area = max(max_area, h * w)
return max_area
单调队列（Monotonic Queue）
单调队列是一种特殊的队列，队列中的元素保持单调性。
应用场景
- 滑动窗口最大值/最小值
- 动态规划优化
示例：滑动窗口最大值
from collections import deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
# 移除窗口外的元素
while dq and dq[0] < i - k + 1:
dq.popleft()
# 维护单调递减队列
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# 窗口大小达到 k 时，记录最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result
优先队列（Priority Queue / Heap）
优先队列是一种特殊的队列，元素按照优先级出队。
堆（Heap）实现
import heapq
# 最小堆（默认）
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 1
# 最大堆（使用负数）
heap = []
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -2)
print(-heapq.heappop(heap)) # 3
应用场景
- Top K 问题
- 合并 K 个有序链表
- 中位数查找
示例：合并 K 个有序链表
import heapq
def merge_k_lists(lists):
heap = []
# 初始化堆
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
常见题目
1. 有效的括号
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
else:
stack.append(char)
return not stack
2. 每日温度
def daily_temperatures(temperatures):
stack = []
result = [0] * len(temperatures)
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
index = stack.pop()
result[index] = i - index
stack.append(i)
return result
3. 滑动窗口最大值
from collections import deque
def max_sliding_window(nums, k):
dq = deque()
result = []
for i in range(len(nums)):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
总结
栈和队列是算法面试中的重要数据结构：
- 栈：LIFO 原则，用于括号匹配、表达式求值、DFS
- 队列：FIFO 原则，用于 BFS、任务调度
- 单调栈：维护单调性，用于找更大/更小元素
- 单调队列：滑动窗口问题
- 优先队列：Top K 问题、合并有序序列
掌握这些数据结构及其应用，能够帮助你解决许多算法问题。
接下来，让我们学习树、字典树和堆，这是更复杂的树形数据结构。