第5章 栈与队列
5.1 栈（Stack）
5.1.1 栈的定义与基本特性
栈是一种限定仅在表尾进行插入和删除操作的线性表。表尾称为“栈顶”（Top），表头称为“栈底”（Bottom）。栈的核心特性是后进先出（Last In First Out，LIFO）：最后入栈的元素最先出栈，最早入栈的元素最后出栈。
生活中的栈：叠放的盘子（只能从顶端取放）、浏览器的“后退”功能（最近访问的页面最先被回溯）。
5.1.2 栈的基本操作
栈的操作围绕栈顶进行，核心操作包括：
入栈（Push）：在栈顶插入元素，又称“压栈”。
出栈（Pop）：删除并返回栈顶元素，又称“弹栈”。
查看栈顶（Peek）：返回栈顶元素但不删除。
判空（Is Empty）：判断栈是否不含任何元素。
获取大小（Size）：返回栈中元素的个数。
这些操作需满足：入栈和出栈仅在栈顶进行，不允许访问或修改栈中其他位置的元素。
5.1.3 栈的实现方式
栈的实现需基于线性数据结构（数组或链表），核心是通过限制操作位置（仅栈顶）实现LIFO特性。以下分别介绍基于Python列表和链表的实现。
5.1.3.1 基于列表的栈实现
Python列表（动态数组）可直接作为栈的底层存储，利用列表的append()（尾插，对应栈顶）和pop()（尾删）操作实现入栈和出栈。
实现思路：
栈顶对应列表尾部（lst[-1]），入栈用lst.append(val)，出栈用lst.pop()，均为O(1)操作。
栈底对应列表头部（lst[0]），但无需直接操作。
代码实现：
python

	class StackByList:
	def __init__(self):
	self._data = [] # 用列表存储栈元素，栈顶为列表尾部
	
	def push(self, val):
	"""入栈：在栈顶添加元素val"""
	self._data.append(val)
	
	def pop(self):
	"""出栈：删除并返回栈顶元素，若栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("pop from empty stack")
	return self._data.pop() # 列表pop()默认删除尾部元素（栈顶）
	
	def peek(self):
	"""查看栈顶元素，若栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty stack")
	return self._data[-1] # 列表[-1]为尾部元素（栈顶）
	
	def is_empty(self):
	"""判断栈是否为空"""
	return len(self._data) == 0
	
	def size(self):
	"""返回栈中元素个数"""
	return len(self._data)
	
	def __str__(self):
	"""返回栈的字符串表示（从栈底到栈顶）"""
	return "Stack: [" + ", ".join(map(str, self._data)) + "] (top)"

操作效率分析：
push()、pop()、peek()、is_empty()、size()均为O(1)时间复杂度（列表尾部操作）。
空间复杂度O(n)，n为栈中元素个数。
5.1.3.2 基于链表的栈实现
链表（第4章）也可实现栈，通常选择头插法和头删法（链表头部作为栈顶），此时入栈和出栈操作均为O(1)。
实现思路：
栈顶对应链表头部（头节点），入栈通过头插法添加节点，出栈通过头删法删除节点。
需维护头节点（栈顶）和栈大小（可选，便于快速获取size）。
代码实现（基于第4章的ListNode类）：
python

	class ListNode: # 复用第4章的单链表节点类
	def __init__(self, val=0, next=None):
	self.val = val
	self.next = next
	
	class StackByLinkedList:
	def __init__(self):
	self._top = None # 栈顶指针（头节点）
	self._size = 0 # 栈中元素个数
	
	def push(self, val):
	"""入栈：在栈顶（链表头部）插入节点"""
	new_node = ListNode(val)
	new_node.next = self._top # 新节点next指向原栈顶
	self._top = new_node # 更新栈顶为新节点
	self._size += 1
	
	def pop(self):
	"""出栈：删除并返回栈顶（链表头部）节点值，若栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("pop from empty stack")
	val = self._top.val
	self._top = self._top.next # 栈顶指针后移（删除头节点）
	self._size -= 1
	return val
	
	def peek(self):
	"""查看栈顶元素，若栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty stack")
	return self._top.val
	
	def is_empty(self):
	"""判断栈是否为空"""
	return self._size == 0
	
	def size(self):
	"""返回栈中元素个数"""
	return self._size
	
	def __str__(self):
	"""返回栈的字符串表示（从栈底到栈顶）"""
	result = []
	current = self._top
	while current:
	result.append(str(current.val))
	current = current.next
	return "Stack: [" + ", ".join(reversed(result)) + "] (top)" # reversed()转为栈底到栈顶

操作效率分析：
所有操作（push()、pop()等）均为O(1)时间复杂度（链表头部操作无需遍历）。
空间复杂度O(n)，n为栈中元素个数（含节点指针域开销）。
5.1.4 栈的应用场景
栈的LIFO特性使其在以下场景中广泛应用：
1.
函数调用栈：程序执行时，函数调用通过栈记录上下文。每调用一个函数，其栈帧（包含参数、局部变量、返回地址）入栈；函数返回时，栈帧出栈，恢复上一层函数执行。例如递归函数的调用过程本质是栈的连续入栈，递归返回是栈的连续出栈。
2.
3.
表达式求值与转换：数学表达式（如中缀表达式转后缀表达式）的解析依赖栈管理运算符优先级。例如，中缀表达式3 + 4 * 2转后缀表达式时，栈用于暂存运算符*，待高优先级运算完成后弹出。
4.
5.
括号匹配：验证代码中的括号（()、[]、{}）是否匹配，栈可暂存左括号，遇到右括号时弹出栈顶左括号检查匹配性。
6.
7.
撤销操作（Undo）：文本编辑器、图形软件的撤销功能，通过栈记录操作历史，撤销时弹出最近操作。
8.
5.1.5 栈的经典问题与实现
5.1.5.1 有效的括号匹配
问题描述：给定一个只包含'('、')'、'{'、'}'、'['、']'的字符串，判断字符串是否有效（左括号必须用相同类型的右括号闭合，且顺序正确）。
解题思路：
遍历字符串，遇到左括号（'('/'{'/'['）则入栈；
遇到右括号时，若栈空（无匹配左括号）或栈顶左括号类型不匹配，则无效；否则弹出栈顶左括号；
遍历结束后，栈必须为空（所有左括号均匹配）。
代码实现：
python

	def is_valid_parentheses(s: str) -> bool:
	stack = []
	# 右括号到左括号的映射，便于快速匹配
	mapping = {')': '(', '}': '{', ']': '['}
	
	for char in s:
	if char in mapping: # 遇到右括号
	if not stack: # 栈空，无匹配左括号
	return False
	top = stack.pop()
	if top != mapping[char]: # 类型不匹配
	return False
	else: # 遇到左括号，入栈
	stack.append(char)
	
	return len(stack) == 0 # 栈空则所有左括号均匹配

示例验证：

is_valid_parentheses("()[]{}") → True
is_valid_parentheses("(]") → False
is_valid_parentheses("([)]") → False

5.1.5.2 最小栈
问题描述：设计一个栈，支持push、pop、top操作，并能在常数时间内检索到最小元素。
解题思路：
用两个栈：主栈（存储所有元素）和辅助栈（存储当前最小元素）。
入栈时，若辅助栈为空或新元素≤辅助栈顶元素，则新元素同时入辅助栈（更新当前最小值）；
出栈时，若主栈顶元素等于辅助栈顶元素，则辅助栈同时出栈（最小值更新为次小元素）；
检索最小值时，直接返回辅助栈顶元素。
代码实现：
python

	class MinStack:
	def __init__(self):
	self._main_stack = [] # 主栈：存储所有元素
	self._min_stack = [] # 辅助栈：存储当前最小元素
	
	def push(self, val: int) -> None:
	self._main_stack.append(val)
	# 辅助栈为空或新元素≤当前最小值，入辅助栈
	if not self._min_stack or val <= self._min_stack[-1]:
	self._min_stack.append(val)
	
	def pop(self) -> None:
	if self._main_stack:
	val = self._main_stack.pop()
	# 若弹出的是当前最小值，辅助栈同步弹出
	if val == self._min_stack[-1]:
	self._min_stack.pop()
	
	def top(self) -> int:
	if self._main_stack:
	return self._main_stack[-1]
	raise IndexError("top from empty stack")
	
	def get_min(self) -> int:
	if self._min_stack:
	return self._min_stack[-1]
	raise IndexError("get_min from empty stack")

操作效率：所有操作均为O(1)时间复杂度，空间复杂度O(n)（最坏情况辅助栈存储所有元素）。
5.1.5.3 栈的压入、弹出序列
问题描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序（假设压入栈的所有数字均不相等）。
解题思路：
模拟入栈过程，按压入序列依次入栈；
每次入栈后，检查栈顶元素是否等于弹出序列当前元素，若是则弹出栈顶并移动弹出序列指针；
最终若栈为空，说明弹出序列有效。
代码实现：
python

	def validate_stack_sequences(pushed: list[int], popped: list[int]) -> bool:
	stack = []
	pop_idx = 0 # 弹出序列指针
	
	for val in pushed:
	stack.append(val) # 按压入序列入栈
	# 栈顶与弹出序列当前元素匹配，弹出并移动指针
	while stack and stack[-1] == popped[pop_idx]:
	stack.pop()
	pop_idx += 1
	
	return len(stack) == 0 # 栈空则弹出序列有效

示例验证：

validate_stack_sequences([1,2,3,4,5], [4,5,3,2,1]) → True（压入1,2,3,4后弹出4，压入5后弹出5,3,2,1）
validate_stack_sequences([1,2,3,4,5], [4,3,5,1,2]) → False（弹出5后栈顶为2，无法弹出1）

5.2 队列（Queue）
5.2.1 队列的定义与基本特性
队列是另一种限定操作位置的线性表，仅允许在表尾插入元素（入队），在表头删除元素（出队）。表尾称为“队尾”（Rear），表头称为“队首”（Front）。队列的核心特性是先进先出（First In First Out，FIFO）：最早入队的元素最先出队。
生活中的队列：排队购票（先到先服务）、打印机任务队列（按提交顺序打印）。
5.2.2 队列的基本操作
队列的操作围绕队首和队尾进行，核心操作包括：
入队（Enqueue）：在队尾插入元素。
出队（Dequeue）：删除并返回队首元素。
查看队首（Peek/Front）：返回队首元素但不删除。
判空（Is Empty）：判断队列是否不含任何元素。
获取大小（Size）：返回队列中元素的个数。
与栈不同，队列的入队和出队操作分别在两端进行，需同时维护队首和队尾的位置。
5.2.3 队列的实现方式
队列的实现同样基于线性数据结构，需解决“队首删除效率低”的问题。以下介绍基于列表（含循环队列）和链表的实现。
5.2.3.1 基于列表的队列实现
Python列表可直接实现队列，但需注意队首删除的效率问题。
（1）简单队列（基于列表的朴素实现）
实现思路：
队尾对应列表尾部，入队用append(val)（O(1)）；
队首对应列表头部，出队用pop(0)（O(n)，需移动所有元素）。
代码实现：
python

	class QueueByListSimple:
	def __init__(self):
	self._data = [] # 列表存储队列元素，队首为[0]，队尾为[-1]
	
	def enqueue(self, val):
	"""入队：在队尾添加元素val"""
	self._data.append(val)
	
	def dequeue(self):
	"""出队：删除并返回队首元素，若队空则抛出异常"""
	if self.is_empty():
	raise IndexError("dequeue from empty queue")
	return self._data.pop(0) # 列表pop(0)删除头部元素（队首）
	
	def peek(self):
	"""查看队首元素，若队空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty queue")
	return self._data[0]
	
	def is_empty(self):
	"""判断队列是否为空"""
	return len(self._data) == 0
	
	def size(self):
	"""返回队列中元素个数"""
	return len(self._data)
	
	def __str__(self):
	"""返回队列的字符串表示（从队首到队尾）"""
	return "Queue: [" + ", ".join(map(str, self._data)) + "] (front -> rear)"

问题：dequeue()操作时间复杂度O(n)，当队列元素较多时效率低下。
（2）循环队列（基于列表的高效实现）
核心思想：
用固定大小的列表模拟队列，通过队首指针（front）和队尾指针（rear）记录位置，指针通过取模运算（% capacity）循环移动，避免元素移动。
队空条件：front == rear；
队满条件：(rear + 1) % capacity == front（预留一个空位置区分队空和队满）。
代码实现：
python

	class CircularQueue:
	def __init__(self, capacity: int):
	self._capacity = capacity + 1 # 预留一个空位置区分队空队满
	self._data = [None] * self._capacity
	self._front = 0 # 队首指针（指向队首元素）
	self._rear = 0 # 队尾指针（指向队尾元素的下一个位置）
	
	def enqueue(self, val: int) -> bool:
	"""入队：队尾添加元素，成功返回True，队满返回False"""
	if self.is_full():
	return False
	self._data[self._rear] = val
	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 peek(self) -> int:
	"""查看队首元素，队空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty queue")
	return self._data[self._front]
	
	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 "CircularQueue: [] (front -> rear)"
	# 计算有效元素范围
	if self._front < self._rear:
	elements = self._data[self._front:self._rear]
	else:
	elements = self._data[self._front:] + self._data[:self._rear]
	return f"CircularQueue: [{', '.join(map(str, elements))}] (front -> rear, capacity: {self._capacity - 1})"

操作效率：所有操作均为O(1)时间复杂度，空间复杂度O(capacity)（需预分配固定容量）。
5.2.3.2 基于链表的队列实现
链表可实现动态容量的队列，通过维护头节点（队首）和尾节点（队尾），使入队和出队操作均为O(1)。
实现思路：
队首对应链表头节点，出队（dequeue）删除头节点；
队尾对应链表尾节点，入队（enqueue）在尾节点后添加新节点；
需处理空队列（头/尾节点均为None）和单节点队列的边界情况。
代码实现（基于第4章的ListNode类）：
python

	class ListNode: # 复用单链表节点类
	def __init__(self, val=0, next=None):
	self.val = val
	self.next = next
	
	class QueueByLinkedList:
	def __init__(self):
	self._front = None # 队首指针（头节点）
	self._rear = None # 队尾指针（尾节点）
	self._size = 0 # 队列元素个数
	
	def enqueue(self, val):
	"""入队：在队尾（链表尾部）添加节点"""
	new_node = ListNode(val)
	if self.is_empty(): # 空队列：头、尾指针均指向新节点
	self._front = new_node
	self._rear = new_node
	else: # 非空队列：尾节点next指向新节点，更新尾指针
	self._rear.next = new_node
	self._rear = new_node
	self._size += 1
	
	def dequeue(self):
	"""出队：删除并返回队首（链表头部）节点值，若队空则抛出异常"""
	if self.is_empty():
	raise IndexError("dequeue from empty queue")
	val = self._front.val
	self._front = self._front.next # 队首指针后移（删除头节点）
	self._size -= 1
	# 若队列为空，尾指针置空
	if self.is_empty():
	self._rear = None
	return val
	
	def peek(self):
	"""查看队首元素，若队空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty queue")
	return self._front.val
	
	def is_empty(self):
	"""判断队列是否为空"""
	return self._size == 0
	
	def size(self):
	"""返回队列中元素个数"""
	return self._size
	
	def __str__(self):
	"""返回队列的字符串表示（从队首到队尾）"""
	result = []
	current = self._front
	while current:
	result.append(str(current.val))
	current = current.next
	return "Queue: [" + ", ".join(result) + "] (front -> rear)"

操作效率：所有操作均为O(1)时间复杂度，空间复杂度O(n)（n为元素个数，含节点指针开销）。
5.2.4 队列的应用场景
队列的FIFO特性使其适用于“先到先服务”的场景：
1.
任务调度：操作系统的进程调度、线程池任务处理、打印机任务队列等，均通过队列管理待执行任务，保证按提交顺序处理。
2.
3.
广度优先搜索（BFS）：图或树的BFS算法依赖队列存储待访问节点，确保按层次（距离）顺序访问节点（如二叉树的层序遍历、最短路径问题）。
4.
5.
缓冲队列：网络通信中，数据接收速率可能高于处理速率，通过队列缓存数据（如TCP接收缓冲区），避免数据丢失。
6.
7.
消息队列：分布式系统中，通过消息队列（如RabbitMQ、Kafka）实现跨服务异步通信，消息按发送顺序存储，接收方按顺序消费。
8.
5.2.5 队列的经典问题与实现
5.2.5.1 用栈实现队列
问题描述：仅使用两个栈实现先入先出队列，支持队列的基本操作（push、pop、peek、empty）。
解题思路：
用两个栈：入队栈（in_stack）和出队栈（out_stack）；
push操作：元素入in_stack；
pop/peek操作：若out_stack为空，将in_stack所有元素弹出并压入out_stack（此时out_stack元素顺序与队列一致），再从out_stack弹出/查看栈顶。
代码实现：
python

	class MyQueue:
	def __init__(self):
	self._in_stack = [] # 入队栈
	self._out_stack = [] # 出队栈
	
	def push(self, x: int) -> None:
	"""元素x入队"""
	self._in_stack.append(x)
	
	def _transfer(self):
	"""将in_stack元素转移到out_stack（仅当out_stack为空时）"""
	if not self._out_stack:
	while self._in_stack:
	self._out_stack.append(self._in_stack.pop())
	
	def pop(self) -> int:
	"""出队并返回队首元素"""
	self._transfer()
	if not self._out_stack:
	raise IndexError("pop from empty queue")
	return self._out_stack.pop()
	
	def peek(self) -> int:
	"""查看队首元素"""
	self._transfer()
	if not self._out_stack:
	raise IndexError("peek from empty queue")
	return self._out_stack[-1]
	
	def empty(self) -> bool:
	"""判断队列是否为空"""
	return not self._in_stack and not self._out_stack

操作效率：push为O(1)；pop/peek均摊O(1)（每个元素转移一次）。
5.2.5.2 用队列实现栈
问题描述：仅使用两个队列实现后入先出栈，支持栈的基本操作（push、pop、top、empty）。
解题思路：
用两个队列：主队列（q1）和辅助队列（q2）；
push操作：元素入q1；
pop操作：将q1前n-1个元素转移到q2，q1剩余元素为栈顶，弹出后交换q1和q2。
代码实现：
python

	from collections import deque # 用deque实现队列（高效）
	
	class MyStack:
	def __init__(self):
	self._q1 = deque()
	self._q2 = deque()
	
	def push(self, x: int) -> None:
	"""元素x入栈"""
	self._q1.append(x)
	
	def pop(self) -> int:
	"""出栈并返回栈顶元素"""
	if self.empty():
	raise IndexError("pop from empty stack")
	# 将q1前n-1个元素转移到q2
	while len(self._q1) > 1:
	self._q2.append(self._q1.popleft())
	# q1剩余元素为栈顶
	top_val = self._q1.popleft()
	# 交换q1和q2，保证下次操作q1为主队列
	self._q1, self._q2 = self._q2, self._q1
	return top_val
	
	def top(self) -> int:
	"""查看栈顶元素"""
	if self.empty():
	raise IndexError("top from empty stack")
	# 复用pop操作逻辑，获取栈顶后重新入队
	top_val = self.pop()
	self.push(top_val)
	return top_val
	
	def empty(self) -> bool:
	"""判断栈是否为空"""
	return len(self._q1) == 0

优化实现（单队列）：
仅用一个队列，入队后将前n-1个元素出队并重新入队，使队尾元素（新入队元素）移至队首，实现栈顶效果：
python

	class MyStackSingleQueue:
	def __init__(self):
	self._q = deque()
	
	def push(self, x: int) -> None:
	self._q.append(x)
	# 将前n-1个元素出队并重新入队，使新元素（栈顶）位于队首
	for _ in range(len(self._q) - 1):
	self._q.append(self._q.popleft())
	
	def pop(self) -> int:
	if self.empty():
	raise IndexError("pop from empty stack")
	return self._q.popleft() # 队首即栈顶
	
	def top(self) -> int:
	if self.empty():
	raise IndexError("top from empty stack")
	return self._q[0] # 队首即栈顶
	
	def empty(self) -> bool:
	return len(self._q) == 0

5.2.5.3 滑动窗口最大值
问题描述：给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的k个数字，滑动窗口每次只向右移动一位，返回滑动窗口中的最大值。
解题思路（单调队列）：
维护一个单调递减队列（存储元素索引），队列头部为当前窗口最大值的索引；
入队规则：新元素大于等于队尾元素时，删除队尾元素，直至队列为空或新元素小于队尾元素，再入队新元素索引；
出队规则：若队首索引超出当前窗口左边界，删除队首；
每个窗口的最大值为队首元素值。
代码实现：
python

	from collections import deque
	
	def max_sliding_window(nums: list[int], k: int) -> list[int]:
	if not nums or k == 0:
	return []
	q = deque() # 单调递减队列（存储索引）
	result = []
	
	for i in range(len(nums)):
	# 1. 移除窗口外的元素（索引 <= i - k）
	while q and q[0] <= i - k:
	q.popleft()
	
	# 2. 维护队列单调递减：新元素 >= 队尾元素则删除队尾
	while q and nums[i] >= nums[q[-1]]:
	q.pop()
	q.append(i)
	
	# 3. 窗口形成（i >= k - 1），记录最大值（队首元素）
	if i >= k - 1:
	result.append(nums[q[0]])
	
	return result

示例验证：
max_sliding_window([1,3,-1,-3,5,3,6,7], 3) → [3,3,5,5,6,7]
操作效率：每个元素入队/出队各一次，时间复杂度O(n)，空间复杂度O(k)（队列最多存储k个元素）。
小结
本章系统介绍了栈与队列的定义、特性、实现方式及应用。栈是LIFO结构，支持在栈顶高效插入和删除，适用于函数调用、括号匹配等场景；队列是FIFO结构，支持在队尾插入、队首删除，适用于任务调度、BFS等场景。
实现层面，栈可基于列表（尾部操作）或链表（头部操作）实现，队列可基于列表（循环队列）或链表（头尾指针）实现，核心是确保操作时间复杂度为O(1)。经典问题（如用栈实现队列、滑动窗口最大值）的解决依赖对数据结构特性的深入理解和灵活运用，需重点掌握单调队列、辅助栈等技巧。
栈与队列作为基础线性结构，是后续学习树、图等复杂数据结构的重要基础，其设计思想（如限制操作位置、双栈/双队列模拟）也为解决复杂问题提供了启发。<|FCResponseEnd|># 第5章 栈与队列
5.1 栈（Stack）
5.1.1 栈的定义与基本特性
栈是一种限定仅在表尾进行插入和删除操作的线性表。表尾称为“栈顶”（Top），表头称为“栈底”（Bottom）。栈的核心特性是后进先出（Last In First Out，LIFO）：最后入栈的元素最先出栈，最早入栈的元素最后出栈。
例如，叠放的盘子只能从顶端取放，浏览器的“后退”功能回溯最近访问的页面，均遵循栈的LIFO特性。
5.1.2 栈的基本操作
栈的所有操作均围绕栈顶进行，核心操作包括：
入栈（Push）：在栈顶插入元素。
出栈（Pop）：删除并返回栈顶元素。
查看栈顶（Peek）：返回栈顶元素但不删除。
判空（Is Empty）：判断栈是否不含元素。
获取大小（Size）：返回栈中元素个数。
5.1.3 栈的实现方式
栈的实现需基于线性数据结构（数组或链表），通过限制操作位置（仅栈顶）实现LIFO特性。
5.1.3.1 基于列表的栈实现
Python列表（动态数组）可直接作为栈的底层存储，利用列表的append()（尾插，对应栈顶）和pop()（尾删）操作实现入栈和出栈，时间复杂度均为O(1)。
代码实现：
python

	class StackByList:
	def __init__(self):
	self._data = [] # 栈元素存储列表，栈顶为列表尾部
	
	def push(self, val):
	"""入栈：在栈顶添加元素val"""
	self._data.append(val)
	
	def pop(self):
	"""出栈：删除并返回栈顶元素，栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("pop from empty stack")
	return self._data.pop() # 列表pop()默认删除尾部元素（栈顶）
	
	def peek(self):
	"""查看栈顶元素，栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty stack")
	return self._data[-1] # 列表[-1]为栈顶元素
	
	def is_empty(self):
	"""判断栈是否为空"""
	return len(self._data) == 0
	
	def size(self):
	"""返回栈中元素个数"""
	return len(self._data)
	
	def __str__(self):
	"""返回栈的字符串表示（从栈底到栈顶）"""
	return f"Stack: [{', '.join(map(str, self._data))}] (top)"

5.1.3.2 基于链表的栈实现
链表实现栈时，通常选择头插法和头删法（链表头部作为栈顶），此时入栈和出栈操作均为O(1)。需维护头节点（栈顶）和栈大小。
代码实现（基于第4章ListNode类）：
python

	class ListNode:
	def __init__(self, val=0, next=None):
	self.val = val
	self.next = next
	
	class StackByLinkedList:
	def __init__(self):
	self._top = None # 栈顶指针（头节点）
	self._size = 0 # 栈元素个数
	
	def push(self, val):
	"""入栈：在栈顶（链表头部）插入节点"""
	new_node = ListNode(val)
	new_node.next = self._top # 新节点next指向原栈顶
	self._top = new_node # 更新栈顶为新节点
	self._size += 1
	
	def pop(self):
	"""出栈：删除并返回栈顶节点值，栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("pop from empty stack")
	val = self._top.val
	self._top = self._top.next # 栈顶指针后移（删除头节点）
	self._size -= 1
	return val
	
	def peek(self):
	"""查看栈顶元素，栈空则抛出异常"""
	if self.is_empty():
	raise IndexError("peek from empty stack")
	return self._top.val
	
	def is_empty(self):
	return self._size == 0
	
	def size(self):
	return self._size
	
	def __str__(self):
	"""返回栈的字符串表示（从栈底到栈顶）"""
	elements = []
	current = self._top
	while current:
	elements.append(str(current.val))
	current = current.next
	return f"Stack: [{', '.join(reversed(elements))}] (top)" # reversed()转为栈底到栈顶

5.1.4 栈的应用场景
1.函数调用栈：程序执行时，函数调用通过栈记录上下文。调用函数时栈帧入栈，返回时栈帧出栈，恢复上一层执行（如递归函数依赖栈实现）。
2.表达式求值：中缀表达式转后缀表达式（如3+4*2转3 4 2 * +）需用栈管理运算符优先级。
3.括号匹配：验证代码中括号是否匹配（如()、[]、{}），栈暂存左括号，遇右括号弹出匹配。
4.撤销操作：文本编辑器的“撤销”功能通过栈记录操作历史，撤销时弹出最近操作。
5.1.5 栈的经典问题与实现
5.1.5.1 有效的括号匹配
问题：判断字符串中的括号是否匹配（左括号与右括号类型一致且顺序正确）。
思路：遍历字符串，左括号入栈；右括号时，若栈空或栈顶左括号类型不匹配则无效，否则弹出栈顶。遍历结束栈需为空。
代码实现：
python

	def is_valid_parentheses(s: str) -> bool:
	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 len(stack) == 0 # 栈空则所有左括号均匹配

5.1.5.2 最小栈
问题：设计一个栈，支持push、pop、top操作，并能在O(1)时间内检索最小元素。
思路：用两个栈，主栈存储元素，辅助栈存储当前最小元素。入栈时，若新元素≤辅助栈顶则同步入辅助栈；出栈时，若主栈顶等于辅助栈顶则同步出辅助栈。
代码实现：
python

	class MinStack:
	def __init__(self):
	self._main_stack = [] # 主栈：存储所有元素
	self._min_stack = [] # 辅助栈：存储当前最小元素
	
	def push(self, val: int) -> None:
	self._main_stack.append(val)
	if not self._min_stack or val <= self._min_stack[-1]:
	self._min_stack.append(val)
	
	def pop(self) -> None:
	if self._main_stack:
	val = self._main_stack.pop()
	if val == self._min_stack[-1]:
	self._min_stack.pop()
	
	def top(self) -> int:
	if self._main_stack:
	return self._main_stack[-1]
	raise IndexError("top from empty stack")
	
	def get_min(self) -> int:
	if self._min_stack:
	return self._min_stack[-1]
	raise IndexError("get_min from empty stack")

5.1.5.3 栈的压入、弹出序列
问题：判断弹出序列是否为栈的合法弹出顺序（假设压入元素不重复）。
思路：模拟入栈过程，按压入序列入栈；每次入栈后，若栈顶等于弹出序列当前元素，则弹出并移动弹出指针。最终栈空则合法。
代码实现：
python

	def validate_stack_sequences(pushed: list[int], popped: list[int]) -> bool:
	stack = []
	pop_idx = 0 # 弹出序列指针
	
	for val in pushed:
	stack.append(val)
	# 栈顶与弹出序列匹配则弹出
	while stack and stack[-1] == popped[pop_idx]:
	stack.pop()
	pop_idx += 1
	
	return len(stack) == 0 # 栈空则弹出序列有效

5.2 队列（Queue）
5.2.1 队列的定义与基本特性
队列是限定仅在表尾插入、表头删除的线性表。表尾称为“队尾”（Rear），表头称为“队首”（Front）。核心特性是先进先出（First In First Out，FIFO）：最早入队的元素最先出队。
例如，排队购票、打印机任务队列均遵循FIFO特性。
5.2.2 队列的基本操作
入队（Enqueue）：在队尾插入元素。
出队（Dequeue）：删除并返回队首元素。
查看队首（Peek）：返回队首元素但不删除。
判空（Is Empty）：判断队列是否为空。
获取大小（Size）：返回队列中元素个数。
5.2.3 队列的实现方式
5.2.3.1 基于列表的队列实现
简单队列：队尾用append()入队（O(1)），队首用pop(0)出队（O(n)，需移动所有元素），效率低。
循环队列（高效实现）：用固定大小列表，通过队首/队尾指针和取模运算实现循环，避免元素移动。队空条件：front == rear；队满条件：(rear + 1) % capacity == front（预留一个空位置区分）。
代码实现：
python

	class CircularQueue:
	def __init__(self, capacity: int):
	self._capacity = capacity + 1 # 预留空位置区分队空队满
	self._data = [None] * self._capacity
	self._front = 0 # 队首指针（指向队首元素）
	self._rear = 0 # 队尾指针（指向队尾元素下一个位置）
	
	def enqueue(self, val: int) -> bool:
	"""入队，队满返回False"""
	if self.is_full():
	return False
	self._data[self._rear] = val
	self._rear = (self._rear + 1) % self._capacity # 队尾指针循环后移
	return True
	
	def dequeue(self) -> bool:
	"""出队，队空返回False"""
	if self.is_empty():
	return False
	self._front = (self._front + 1) % self._capacity # 队首指针循环后移
	return True
	
	def peek(self) -> int:
	if self.is_empty():
	raise IndexError("peek from empty queue")
	return self._data[self._front]
	
	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

5.2.3.2 基于链表的队列实现
通过链表头节点（队首）和尾节点（队尾）实现，入队（尾插）和出队（头删）均为O(1)。
代码实现（基于第4章ListNode类）：
python

	class QueueByLinkedList:
	def __init__(self):
	self._front = None # 队首指针（头节点）
	self._rear = None # 队尾指针（尾节点）
	self._size = 0 # 元素个数
	
	def enqueue(self, val):
	"""入队：队尾添加节点"""
	new_node = ListNode(val)
	if self.is_empty():
	self._front = new_node
	self._rear = new_node
	else:
	self._rear.next = new_node
	self._rear = new_node
	self._size += 1
	
	def dequeue(self):
	"""出队：删除队首节点，返回值"""
	if self.is_empty():
	raise IndexError("dequeue from empty queue")
	val = self._front.val
	self._front = self._front.next
	self._size -= 1
	if self.is_empty(): # 队空时尾指针置空
	self._rear = None
	return val
	
	def peek(self):
	if self.is_empty():
	raise IndexError("peek from empty queue")
	return self._front.val
	
	def is_empty(self):
	return self._size == 0
	
	def size(self):
	return self._size

5.2.4 队列的应用场景
1.任务调度：操作系统进程调度、线程池任务处理、打印机队列等，按提交顺序处理任务。
2.广度优先搜索（BFS）：图/树的BFS用队列存储待访问节点，保证按层次顺序访问（如二叉树层序遍历、最短路径）。
3.缓冲队列：网络通信中，用队列缓存数据（如TCP接收缓冲区），避免接收速率高于处理速率导致数据丢失。
4.消息队列：分布式系统中，消息队列（如Kafka）实现跨服务异步通信，消息按发送顺序存储和消费。
5.2.5 队列的经典问题与实现
5.2.5.1 用栈实现队列
问题：仅用两个栈实现队列的push、pop、peek、empty操作。
思路：入队栈（in_stack）存储元素；出队时，若出队栈（out_stack）为空，将入队栈元素弹出并压入出队栈（此时出队栈元素顺序与队列一致），再从出队栈弹出。
代码实现：
python

	class MyQueue:
	def __init__(self):
	self._in_stack = []
	self._out_stack = []
	
	def push(self, x: int) -> None:
	self._in_stack.append(x)
	
	def _transfer(self):
	"""将in_stack元素转移到out_stack（仅out_stack为空时）"""
	if not self._out_stack:
	while self._in_stack:
	self._out_stack.append(self._in_stack.pop())
	
	def pop(self) -> int:
	self._transfer()
	return self._out_stack.pop()
	
	def peek(self) -> int:
	self._transfer()
	return self._out_stack[-1]
	
	def empty(self) -> bool:
	return not self._in_stack and not self._out_stack

5.2.5.2 滑动窗口最大值
问题：给定数组和滑动窗口大小k，返回每个窗口的最大值。
思路：用单调递减队列（存储元素索引），队首为当前窗口最大值索引。入队时删除小于新元素的队尾元素；出队时移除窗口外索引。
代码实现：
python

	from collections import deque
	
	def max_sliding_window(nums: list[int], k: int) -> list[int]:
	q = deque() # 单调递减队列（存储索引）
	result = []
	
	for i in range(len(nums)):
	# 移除窗口外元素（索引 <= i - k）
	while q and q[0] <= i - k:
	q.popleft()
	
	# 维护队列递减：新元素 >= 队尾则删除队尾
	while q and nums[i] >= nums[q[-1]]:
	q.pop()
	q.append(i)
	
	# 窗口形成（i >= k-1），记录队首最大值
	if i >= k - 1:
	result.append(nums[q[0]])
	
	return result

小结
栈和队列是两种基础线性结构，栈遵循LIFO，队列遵循FIFO。栈的实现可基于列表（尾部操作）或链表（头部操作），队列可基于循环列表或链表（头尾指针），核心是保证操作O(1)时间复杂度。
应用上，栈适用于函数调用、括号匹配等场景，队列适用于任务调度、BFS等场景。经典问题（如最小栈、滑动窗口最大值）需结合数据结构特性设计高效算法，如单调队列、辅助栈等技巧。掌握栈与队列是理解复杂数据结构（如树、图）的基础。

来源: