第4章 栈与队列
4.1 引言
在程序设计中，许多问题的解决依赖于对数据处理顺序的严格控制。例如，编译器在解析表达式时需要匹配括号的嵌套关系，操作系统在调度任务时需要按提交顺序执行，这些场景都涉及到两种基础的线性数据结构——栈（Stack） 和队列（Queue）。
栈和队列的核心特征是操作受限：栈仅允许在一端进行插入和删除，队列则允许在两端分别进行插入和删除。这种“受限”并非设计缺陷，而是为了适配特定问题的逻辑，强制规范数据的访问顺序，从而简化操作流程并提升效率。正如工程师不会用瑞士军刀拧所有螺丝（而是选择适配的螺丝刀），数据结构的选择也需匹配问题的特性——栈适合处理“最近相关性”问题，队列适合处理“顺序依赖”问题。
本章将从基本定义出发，系统讲解栈与队列的核心特性、Python实现方式及典型工程应用，重点关注底层原理（如循环队列的指针设计）与实际问题的结合（如滑动窗口最大值的高效求解），为后续复杂数据结构的学习奠定基础。
4.2 栈的定义与核心特性
4.2.1 栈的基本概念
定义4.1 栈：一种线性数据结构，其元素的插入（称为“入栈”）和删除（称为“出栈”）操作仅允许在结构的一端进行，该端称为栈顶（Top），另一端称为栈底（Bottom）。栈中元素的处理遵循“后进先出”（LIFO，Last In First Out） 原则——最后入栈的元素最先出栈，最早入栈的元素最后出栈。
生活类比：堆叠的盘子。新盘子总是放在最上面（栈顶），取盘子时也只能从最上面拿，最下面的盘子（栈底）需等所有上方盘子被取走后才能取出。
4.2.2 栈的基本操作
栈的操作集围绕“栈顶”展开，核心操作如下（所有操作的时间复杂度均为O(1)，基于合理实现）：
入栈（Push）：将元素添加到栈顶，栈中元素数量（大小）加1。
出栈（Pop）：移除栈顶元素并返回其值，栈大小减1（若栈为空，操作无效，通常抛出异常）。
查看栈顶（Peek/Top）：返回栈顶元素的值但不删除该元素（若栈为空，操作无效）。
判空（IsEmpty）：判断栈是否为空，返回布尔值（空栈时大小为0）。
获取大小（Size）：返回栈中元素的数量。
4.3 栈的实现
在Python中，栈的实现主要有两种方式：基于列表（动态数组）或基于链表。由于列表的尾部操作（append和pop）为O(1)时间复杂度，且无需手动管理节点指针，实际应用中优先选择列表作为栈的底层存储结构。
4.3.1 基于列表的栈实现
利用Python列表的尾部作为栈顶，append方法实现入栈（尾部添加），pop方法实现出栈（尾部删除），列表的索引访问实现栈顶查看。
实现代码：
python

	class Stack: 
	def __init__(self): 
	"""初始化空栈，使用列表存储元素，尾部为栈顶""" 
	self._elements = [] # 私有列表，避免外部直接修改 
	
	def push(self, item): 
	"""入栈：将元素添加到栈顶""" 
	self._elements.append(item) 
	
	def pop(self): 
	"""出栈：移除并返回栈顶元素，栈为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("pop from empty stack") 
	return self._elements.pop() # 列表尾部弹出（栈顶） 
	
	def peek(self): 
	"""查看栈顶元素，栈为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("peek from empty stack") 
	return self._elements[-1] # 返回列表尾部元素（栈顶） 
	
	def is_empty(self): 
	"""判断栈是否为空""" 
	return len(self._elements) == 0 
	
	def size(self): 
	"""返回栈中元素个数""" 
	return len(self._elements) 
	
	def __str__(self): 
	"""格式化输出栈内容（栈顶在右侧，便于直观理解）""" 
	return f"Stack: [{', '.join(map(str, self._elements))}] (栈顶→)" 
	
	
	# 工程实践中的使用示例 
	if __name__ == "__main__": 
	# 初始化栈并执行基本操作 
	stack = Stack() 
	print("初始状态:", stack) # 输出：Stack: [] (栈顶→) 
	
	# 入栈操作（模拟函数调用入栈） 
	stack.push("函数A") 
	stack.push("函数B") 
	stack.push("函数C") # 函数C最后入栈，位于栈顶 
	print("入栈后:", stack) # 输出：Stack: [函数A, 函数B, 函数C] (栈顶→) 
	
	# 查看栈状态 
	print(f"栈顶元素: {stack.peek()}, 栈大小: {stack.size()}") # 输出：栈顶元素: 函数C, 栈大小: 3 
	
	# 出栈操作（模拟函数返回出栈） 
	print(f"出栈元素: {stack.pop()}") # 函数C先出栈，输出：出栈元素: 函数C 
	print(f"出栈后: {stack}") # 输出：Stack: [函数A, 函数B] (栈顶→) 
	
	# 边界情况处理（空栈出栈） 
	try: 
	while not stack.is_empty(): 
	stack.pop() 
	stack.pop() # 栈为空时执行pop 
	except IndexError as e: 
	print(f"异常捕获: {e}") # 输出：异常捕获: pop from empty stack

4.3.2 实现说明
底层存储：依赖Python列表的动态数组特性（第3章已介绍），列表尾部的append和pop操作均为O(1)时间复杂度（平均情况），因此栈的核心操作效率得以保证。
封装性：通过私有列表_elements避免外部直接修改栈内元素，仅暴露push、pop等操作接口，符合“最小权限原则”。
边界处理：对空栈执行pop或peek时抛出IndexError，与Python内置数据结构（如列表pop()空列表）的行为一致，便于开发者理解和调试。
4.3.3 栈的链表实现（扩展）
若需频繁在栈顶进行操作且内存动态分配需求较高（如嵌入式系统），可采用链表实现栈（以链表头部为栈顶，插入/删除节点的时间复杂度为O(1)）。但在Python中，列表实现已足够高效，链表实现更多用于理解原理。
实现思路：定义链表节点类ListNode，栈顶指针top指向头节点，push操作在头部插入新节点，pop操作删除头节点并返回值。
4.4 栈的典型应用：括号匹配问题
栈的“后进先出”特性使其天然适合解决具有“嵌套层次”的问题，括号匹配是工程中最常见的场景之一（如代码编译时的语法检查）。
4.4.1 问题描述
给定一个仅包含()、[]、{}的字符串，判断其中的括号是否匹配。匹配需满足两个条件：
1.类型匹配：左括号必须用相同类型的右括号闭合（如(对应)，而非]）；
2.顺序匹配：左括号必须以正确的顺序闭合（如"()[]{}"有效，"(]"无效，"([)]"无效）。
4.4.2 解题思路
1.遍历字符串：对每个字符执行以下操作：
o若为左括号（(、[、{），则入栈（等待后续右括号匹配）；
o若为右括号（)、]、}），则检查栈顶是否为对应的左括号：
若栈为空（无左括号等待匹配），或栈顶左括号类型不匹配，返回False；
若匹配，将栈顶左括号出栈（表示该对括号已匹配）；
2.遍历结束后：若栈为空（所有左括号均匹配），返回True；否则返回False（存在未匹配的左括号）。
核心逻辑：用栈存储“待匹配的左括号”，右括号的出现意味着需要“消解”最近的左括号（栈顶元素），符合栈的LIFO特性。
4.4.3 代码实现与解析
python

	def is_valid_brackets(s: str) -> bool: 
	"""判断字符串s中的括号是否匹配""" 
	stack = Stack() # 实例化栈，存储待匹配的左括号 
	# 右括号与左括号的映射关系，便于快速查找匹配的左括号 
	bracket_map = {')': '(', ']': '[', '}': '{'} 
	
	for char in s: 
	if char in bracket_map.values(): 
	# 情况1：遇到左括号，入栈等待匹配 
	stack.push(char) 
	elif char in bracket_map.keys(): 
	# 情况2：遇到右括号，检查匹配 
	if stack.is_empty(): 
	# 栈为空 → 无左括号匹配，直接返回False 
	return False 
	top_bracket = stack.pop() # 弹出栈顶左括号 
	if top_bracket != bracket_map[char]: 
	# 栈顶左括号与当前右括号类型不匹配 
	return False 
	# 注：题目假设输入仅含括号，非括号字符可忽略（实际工程中需根据需求处理） 
	
	# 遍历结束后，栈必须为空（所有左括号均被匹配） 
	return stack.is_empty() 
	
	
	# 工程测试用例（覆盖常见场景） 
	test_cases = [ 
	("()", True), # 基础匹配 
	("()[]{}", True), # 多种类型匹配 
	("(]", False), # 类型不匹配 
	("([)]", False), # 顺序不匹配 
	("{[]}", True), # 嵌套匹配 
	("", True), # 空字符串（视为有效） 
	("({[()]})", True), # 多层嵌套匹配 
	] 
	
	for s, expected in test_cases: 
	result = is_valid_brackets(s) 
	print(f"输入: {s!r} → 预期: {expected}, 实际: {result} → {'通过' if result == expected else '失败'}")

输出结果：

	输入: '()' → 预期: True, 实际: True → 通过 
	输入: '()[]{}' → 预期: True, 实际: True → 通过 
	输入: '(]' → 预期: False, 实际: False → 通过 
	输入: '([)]' → 预期: False, 实际: False → 通过 
	输入: '{[]}' → 预期: True, 实际: True → 通过 
	输入: '' → 预期: True, 实际: True → 通过 
	输入: '({[()]})' → 预期: True, 实际: True → 通过

4.4.4 复杂度分析
时间复杂度：O(n)，n为字符串长度。每个字符最多入栈和出栈各一次（栈操作O(1)），遍历过程为线性时间。
空间复杂度：O(n)，最坏情况（如字符串全为左括号）栈中存储n个元素。
4.5 队列的定义与核心特性
4.5.1 队列的基本概念
定义4.2 队列：一种线性数据结构，其元素的插入（称为“入队”）操作仅允许在结构的一端（称为队尾（Rear））进行，删除（称为“出队”）操作仅允许在另一端（称为队头（Front））进行。队列中元素的处理遵循“先进先出”（FIFO，First In First Out） 原则——最早入队的元素最先出队，最晚入队的元素最后出队。
生活类比：排队购票。新来的人排在队尾（入队），队头的人购票后离开（出队），先到的人先购票。
4.5.2 队列的基本操作
队列的操作集围绕“队头”和“队尾”展开，核心操作如下（时间复杂度均为O(1)，基于合理实现）：
入队（Enqueue）：将元素添加到队尾，队列大小加1。
出队（Dequeue）：移除队头元素并返回其值，队列大小减1（队列为空时操作无效）。
查看队头（Front）：返回队头元素的值但不删除该元素（队列为空时操作无效）。
判空（IsEmpty）：判断队列是否为空，返回布尔值。
获取大小（Size）：返回队列中元素的数量。
4.6 队列的实现
队列的实现需解决“队头出队效率”问题：若用Python列表直接实现（队尾append入队，队头pop(0)出队），出队操作的时间复杂度为O(n)（需移动所有元素）。为解决该问题，工程中常用循环队列或双端队列。
4.6.1 基于列表的简单实现（适合小规模数据）
实现思路：列表尾部作为队尾（入队用append，O(1)），列表头部作为队头（出队用pop(0)，O(n)）。
代码实现：
python

	class SimpleQueue: 
	def __init__(self): 
	"""初始化空队列""" 
	self._elements = [] # 列表尾部为队尾，头部为队头 
	
	def enqueue(self, item): 
	"""入队：将元素添加到队尾""" 
	self._elements.append(item) 
	
	def dequeue(self): 
	"""出队：移除并返回队头元素，队列为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("dequeue from empty queue") 
	return self._elements.pop(0) # 列表头部出队（O(n)时间复杂度） 
	
	def front(self): 
	"""返回队头元素，队列为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("front from empty queue") 
	return self._elements[0] 
	
	def is_empty(self): 
	return len(self._elements) == 0 
	
	def size(self): 
	return len(self._elements) 
	
	def __str__(self): 
	return f"Queue: [{', '.join(map(str, self._elements))}] (队头→队尾)" 
	
	
	# 使用示例（仅适合数据量小的场景） 
	if __name__ == "__main__": 
	q = SimpleQueue() 
	q.enqueue("任务A") 
	q.enqueue("任务B") 
	q.enqueue("任务C") 
	print(q) # 输出：Queue: [任务A, 任务B, 任务C] (队头→队尾) 
	print("出队元素:", q.dequeue()) # 任务A先出队，输出：出队元素: 任务A 
	print(q) # 输出：Queue: [任务B, 任务C] (队头→队尾)

缺点：pop(0)操作需将列表中所有元素向前移动一位（时间复杂度O(n)），当队列规模较大（如n>10⁴）时，效率显著下降，因此仅适合小规模数据场景。
4.6.2 循环队列：高效队列实现
核心思想：用固定大小的数组（或列表）存储元素，通过两个指针（front记录队头索引，rear记录队尾索引的下一个位置）实现“环形”逻辑，解决队头出队O(n)的效率问题。
设计要点
容量（Capacity）：数组的固定大小（初始化时指定），决定队列的最大存储元素个数。
空队列：front == rear（队头和队尾指针重合）。
满队列：(rear + 1) % capacity == front（故意浪费一个数组空间，避免与空队列状态混淆）。
环形逻辑：指针移动时通过取模运算（% capacity）实现“绕回”数组开头。
实现代码
python

	class CircularQueue: 
	def __init__(self, capacity: int): 
	"""初始化循环队列，指定容量（最多存储capacity-1个元素）""" 
	if capacity <= 0: 
	raise ValueError("容量必须为正整数") 
	self._capacity = capacity # 数组容量（固定大小） 
	self._elements = [None] * capacity # 存储元素的数组 
	self._front = 0 # 队头指针（指向队头元素） 
	self._rear = 0 # 队尾指针（指向队尾元素的下一个位置） 
	
	def enqueue(self, item) -> bool: 
	"""入队：将元素添加到队尾，成功返回True，队列满时返回False""" 
	if self.is_full(): 
	return False # 队列满，入队失败 
	self._elements[self._rear] = item # 存储元素到队尾指针位置 
	self._rear = (self._rear + 1) % self._capacity # 队尾指针后移（环形） 
	return True 
	
	def dequeue(self) -> bool: 
	"""出队：移除队头元素，成功返回True，队列为空时返回False""" 
	if self.is_empty(): 
	return False # 队列为空，出队失败 
	self._front = (self._front + 1) % self._capacity # 队头指针后移（环形） 
	return True 
	
	def front(self): 
	"""返回队头元素，队列为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("front from empty queue") 
	return self._elements[self._front] 
	
	def rear(self): 
	"""返回队尾元素，队列为空时抛出IndexError""" 
	if self.is_empty(): 
	raise IndexError("rear from empty queue") 
	# 队尾元素索引 = (rear - 1) % capacity（因rear指向队尾的下一个位置） 
	return self._elements[(self._rear - 1) % self._capacity] 
	
	def is_empty(self) -> bool: 
	"""判断队列是否为空""" 
	return self._front == self._rear 
	
	def is_full(self) -> bool: 
	"""判断队列是否满""" 
	return (self._rear + 1) % self._capacity == self._front 
	
	def size(self) -> int: 
	"""返回队列元素个数""" 
	return (self._rear - self._front + self._capacity) % self._capacity 
	
	def __str__(self): 
	"""格式化输出队列元素（队头到队尾）""" 
	if self.is_empty(): 
	return f"CircularQueue: [] (容量: {self._capacity})" 
	# 根据front和rear的位置拼接元素（分两种情况） 
	if self._front <= self._rear: 
	# 元素在front到rear之间（无绕回） 
	elements = self._elements[self._front:self._rear] 
	else: 
	# 元素分两段：front到数组末尾，数组开头到rear（绕回） 
	elements = self._elements[self._front:] + self._elements[:self._rear] 
	return f"CircularQueue: [{', '.join(map(str, elements))}] (容量: {self._capacity}, 大小: {self.size()})" 
	
	
	# 工程使用示例 
	if __name__ == "__main__": 
	# 初始化容量为4的循环队列（最多存储3个元素） 
	cq = CircularQueue(capacity=4) 
	print("初始状态:", cq) # 输出：CircularQueue: [] (容量: 4) 
	
	# 入队操作 
	cq.enqueue("任务1") 
	cq.enqueue("任务2") 
	cq.enqueue("任务3") 
	print("入队后:", cq) # 输出：CircularQueue: [任务1, 任务2, 任务3] (容量: 4, 大小: 3) 
	print("队列是否满:", cq.is_full()) # 输出：True（此时(rear+1)%4=front） 
	
	# 入队满队列（预期失败） 
	print("入队任务4（队列满）:", cq.enqueue("任务4")) # 输出：False 
	
	# 出队操作 
	cq.dequeue() # 任务1出队 
	print("出队后:", cq) # 输出：CircularQueue: [任务2, 任务3] (容量: 4, 大小: 2) 
	
	# 入队新元素（此时队列未满） 
	cq.enqueue("任务4") 
	print("入队任务4后:", cq) # 输出：CircularQueue: [任务2, 任务3, 任务4] (容量: 4, 大小: 3) 
	
	# 查看队头和队尾 
	print(f"队头元素: {cq.front()}, 队尾元素: {cq.rear()}") # 输出：队头元素: 任务2, 队尾元素: 任务4

实现说明
环形指针：通过(rear + 1) % capacity和(front + 1) % capacity实现指针绕回，当rear到达数组末尾（索引capacity-1）时，(rear + 1) % capacity为0，指针回到数组开头。
空满判断：故意浪费一个数组空间（即队列满时数组中仍有一个位置为空），通过(rear + 1) % capacity == front判断满队列，避免与front == rear（空队列）的状态混淆。
效率：入队和出队操作仅需移动指针（O(1)时间复杂度），解决了列表实现的效率问题，适合大规模数据场景。
4.6.3 双端队列：两端可操作的队列
定义4.3 双端队列（Deque）：允许在队头和队尾同时进行入队和出队操作的队列，兼具栈和队列的特性。Python标准库collections.deque提供了双端队列的高效实现，所有两端操作均为O(1)时间复杂度。
核心操作（collections.deque）：

使用示例：
python

	from collections import deque 
	
	# 初始化双端队列 
	dq = deque() 
	
	# 队尾入队 
	dq.append("A") 
	dq.append("B") 
	print("队尾入队后:", dq) # 输出：deque(['A', 'B']) 
	
	# 队头入队 
	dq.appendleft("C") 
	print("队头入队后:", dq) # 输出：deque(['C', 'A', 'B']) 
	
	# 队尾出队 
	dq.pop() 
	print("队尾出队后:", dq) # 输出：deque(['C', 'A']) 
	
	# 队头出队 
	dq.popleft() 
	print("队头出队后:", dq) # 输出：deque(['A'])

工程应用：双端队列适合实现“双端操作”场景，如滑动窗口、缓存淘汰策略（LRU缓存的简化实现）等。
4.7 队列的典型应用：滑动窗口最大值
滑动窗口最大值问题是队列（尤其是双端队列）高效应用的经典案例，其核心是利用双端队列维护“候选最大值”集合，将暴力解法的O(nk)时间复杂度优化为O(n)。
4.7.1 问题描述
给定一个整数数组nums和滑动窗口大小k，找出每个滑动窗口中的最大值。
示例：

输入：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3
输出：[3, 3, 5, 5, 6, 7]

解释：
滑动窗口依次为：

[1, 3, -1] → 最大值3
[3, -1, -3] → 最大值3
[-1, -3, 5] → 最大值5
[-3, 5, 3] → 最大值5
[5, 3, 6] → 最大值6
[3, 6, 7] → 最大值7

4.7.2 解题思路
暴力解法：对每个窗口遍历k个元素求最大值，时间复杂度O(nk)，当k接近n时退化为O(n²)，效率低下。
优化思路：用双端队列维护窗口内的“候选最大值”索引，队列中元素对应的数组值单调递减。具体步骤如下：
1.入队规则：对于当前元素nums[i]，从队尾移除所有值 ≤ nums[i]的索引（这些元素不可能是后续窗口的最大值，因为nums[i]更大且更靠后），然后将i入队。
2.出队规则：若队头索引 ≤ i - k（超出窗口范围），将其从队头移除。
3.记录最大值：窗口形成后（i >= k - 1），队头索引对应的元素即为当前窗口的最大值。
4.7.3 代码实现与解析
python

	from collections import deque 
	
	def max_sliding_window(nums, k): 
	"""返回滑动窗口最大值数组""" 
	if not nums or k == 0: 
	return [] 
	dq = deque() # 双端队列，存储索引，对应元素值单调递减 
	result = [] 
	
	for i, num in enumerate(nums): 
	# 步骤1：移除队尾 <= 当前元素的索引（它们不可能是最大值） 
	# 原因：若nums[j] <= num且j < i，则在包含i的窗口中，j不可能是最大值 
	while dq and nums[dq[-1]] <= num: 
	dq.pop() 
	# 步骤2：当前元素索引入队 
	dq.append(i) 
	# 步骤3：移除队头超出窗口范围的索引（窗口左边界为i - k + 1） 
	# 若队头索引 <= i - k，说明其不在当前窗口内（i - k + 1 <= 索引 <= i） 
	while dq[0] <= i - k: 
	dq.popleft() 
	# 步骤4：窗口形成（i >= k-1）后，队头即为当前窗口最大值 
	if i >= k - 1: 
	result.append(nums[dq[0]]) 
	
	return result 
	
	
	# 测试用例 
	nums = [1, 3, -1, -3, 5, 3, 6, 7] 
	k = 3 
	print("滑动窗口最大值:", max_sliding_window(nums, k)) # 输出：[3, 3, 5, 5, 6, 7]

4.7.4 复杂度分析
时间复杂度：O(n)，n为数组长度。每个元素最多入队和出队各一次（双端队列操作O(1)），遍历过程为线性时间。
空间复杂度：O(k)，队列中最多存储k个元素（窗口大小）。
4.8 本章总结
栈是“后进先出”（LIFO）结构，核心操作（push、pop）均在栈顶，适合处理“最近相关性”问题（如括号匹配、函数调用栈）。Python中推荐用列表实现，尾部操作效率为O(1)。
队列是“先进先出”（FIFO）结构，核心操作（enqueue、dequeue）分别在队尾和队头，适合处理“顺序依赖”问题（如任务调度、滑动窗口）。循环队列通过环形指针设计解决了列表出队O(n)的效率问题，双端队列（collections.deque）则提供了两端高效操作的能力。
工程实践要点：
o栈的列表实现需注意尾部操作的O(1)特性，避免在头部插入/删除（O(n)）；
o队列的选择需根据规模：小规模数据用列表简单实现，大规模数据用循环队列或deque；
o双端队列的单调特性（如滑动窗口最大值中的递减队列）是优化“范围最值”问题的关键思想。
栈和队列作为基础线性结构，不仅是日常开发中的常用工具，也是理解树、图等复杂数据结构的重要基础，其“操作受限”的设计思想为特定问题提供了简洁高效的解决方案。
思考题

如何用两个栈实现一个队列？要求支持enqueue（入队）、dequeue（出队）和front（查看队头）操作，且每个操作的平均时间复杂度为O(1)。

设计一个最小栈：支持push、pop、top操作，并能在常数时间内检索到最小元素。（提示：用辅助栈存储当前最小值）

循环队列中，若不浪费空间（即允许存储capacity个元素，而非capacity-1个），如何区分空队列和满队列？（提示：增加一个变量记录队列大小，或在元素中嵌入标记）
用双端队列实现一个单调递增队列，并解决“下一个更大元素”问题：给定数组nums，找出每个元素右侧第一个比它大的元素（若不存在则为-1）。例如，nums = [2, 1, 2, 4, 3]，输出[4, 2, 4, -1, -1]。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49289.html