Python 中**原生没有直接名为“堆栈”或“队列”的独立数据结构**，但可以通过**内置数据结构（如列表）**或**标准库模块（如 `collections`、`queue`）**轻松实现堆栈和队列的功能。以下是详细说明和示例： --- ### **1. 堆栈（Stack）的实现** 堆栈遵循 **LIFO（后进先出）** 原则，常用操作包括 `push`（入栈）和 `pop`（出栈）。 #### **(1) 使用列表（List）实现** - **特点**：简单直接，但性能在大规模数据时可能不如专用结构。 - **示例**： ```python stack = [] # 入栈（push） stack.append(1) stack.append(2) stack.append(3) print(stack) # 输出: [1, 2, 3] # 出栈（pop） top = stack.pop() print(top) # 输出: 3 print(stack) # 输出: [1, 2] ``` #### **(2) 使用 `collections.deque` 实现** - **特点**：`deque` 是双端队列，但也可高效实现堆栈（`append` 和 `pop` 操作时间复杂度为 O(1)）。 - **示例**： ```python from collections import deque stack = deque() stack.append(10) stack.append(20) print(stack.pop()) # 输出: 20 ``` #### **(3) 为什么不用 `list.pop(0)` 实现队列？** - `list.pop(0)` 的时间复杂度为 O(n)，而 `deque.popleft()` 是 O(1)。 --- ### **2. 队列（Queue）的实现** 队列遵循 **FIFO（先进先出）** 原则，常用操作包括 `enqueue`（入队）和 `dequeue`（出队）。 #### **(1) 使用 `collections.deque` 实现** - **特点**：推荐方式，`append` 和 `popleft` 操作高效。 - **示例**： ```python from collections import deque queue = deque() # 入队（enqueue） queue.append("A") queue.append("B") queue.append("C") print(queue) # 输出: deque(['A', 'B', 'C']) # 出队（dequeue） front = queue.popleft() print(front) # 输出: 'A' print(queue) # 输出: deque(['B', 'C']) ``` #### **(2) 使用 `queue.Queue`（线程安全）** - **特点**：适用于多线程环境，提供阻塞和超时功能。 - **示例**： ```python from queue import Queue q = Queue(maxsize=3) # 限制队列大小为3 # 入队 q.put(1) q.put(2) q.put(3) # q.put(4) # 队列满时会阻塞（若未设置超时） # 出队 print(q.get()) # 输出: 1 print(q.get()) # 输出: 2 ``` #### **(3) 其他队列变种** - **`queue.LifoQueue`**：后进先出队列（类似堆栈）。 - **`queue.PriorityQueue`**：优先级队列（按优先级出队）。 ```python from queue import PriorityQueue pq = PriorityQueue() pq.put((2, "Task 2")) # (优先级, 数据) pq.put((1, "Task 1")) print(pq.get()[1]) # 输出: "Task 1"（优先级低的先出） ``` --- ### **3. 堆栈与队列的对比** | 特性 | 堆栈（Stack） | 队列（Queue） | |--------------------|----------------------------|----------------------------| | **顺序原则** | LIFO（后进先出） | FIFO（先进先出） | | **常用操作** | `push`/`pop` | `enqueue`/`dequeue` | | **实现方式** | 列表或 `deque` | `deque` 或 `queue.Queue` | | **典型应用** | 函数调用栈、撤销操作 | 任务调度、消息队列 | --- ### **4. 性能与选择建议** - **单线程场景**： - 堆栈：优先用 `list`（简单）或 `deque`（高性能）。 - 队列：优先用 `collections.deque`（最快）。 - **多线程场景**： - 必须用 `queue.Queue` 及其变种（线程安全）。 - **优先级需求**： - 使用 `queue.PriorityQueue`。 --- ### **5. 示例：用堆栈实现括号匹配** ```python def is_valid_parentheses(s): stack = [] mapping = {")": "(", "]": "[", "}": "{"} for char in s: if char in mapping.values(): # 左括号入栈 stack.append(char) elif char in mapping.keys(): # 右括号检查 if not stack or stack.pop() != mapping[char]: return False return not stack # 栈为空则匹配 print(is_valid_parentheses("()[]{}")) # 输出: True print(is_valid_parentheses("([)]")) # 输出: False ``` --- ### **6. 示例：用队列实现广度优先搜索（BFS）** ```python from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) while queue: vertex = queue.popleft() if vertex not in visited: print(vertex, end=" ") visited.add(vertex) queue.extend(graph[vertex] - visited) # 扩展邻居节点 graph = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} } bfs(graph, 'A') # 输出: A B C D E F ``` --- ### **