如何在Python中实现搜索算法所需的栈（Stack）与队列（Queue）？

嘿，这个问题问到点子上了——栈和队列是深度优先搜索（DFS）、广度优先搜索（BFS）这类算法的核心依赖，而最佳优先搜索则会用到优先队列（本质是堆结构）。我来给你拆解Python里的实现方式，还有它们在搜索场景里的实际用法：

一、栈（Stack）：后进先出（LIFO），适配DFS #

栈的核心逻辑是“最后加入的元素最先被取出”，完美匹配DFS的遍历逻辑——一条路走到黑，走不通再回溯。

实现方式1：用Python内置列表直接实现 #

Python列表的append()（在尾部添加）和pop()（从尾部取出）操作都是O(1)时间复杂度，刚好符合栈的需求，甚至不需要额外封装类：

# 初始化栈
stack = []

# 入栈操作（push）
stack.append("节点A")
stack.append("节点B")
stack.append("节点C")

# 出栈操作（pop）
top_node = stack.pop()  # 取出"节点C"
print(top_node)

# 查看栈顶元素（peek），不弹出
if stack:
    print(stack[-1])  # 输出"节点B"

# 判断栈是否为空
print(len(stack) == 0)  # False

实现方式2：封装成自定义Stack类（更规范） #

如果需要更清晰的接口，可以封装一个类：

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """入栈"""
        self.items.append(item)
    
    def pop(self):
        """出栈，若栈为空返回None"""
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        """查看栈顶元素"""
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        """判断栈是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回栈的大小"""
        return len(self.items)

# 使用示例
dfs_stack = Stack()
dfs_stack.push("起始节点")
dfs_stack.push("子节点1")
print(dfs_stack.pop())  # 子节点1

二、队列（Queue）：先进先出（FIFO），适配BFS #

队列的逻辑是“最先加入的元素最先被取出”，对应BFS的层级遍历逻辑——先遍历完当前层的所有节点，再进入下一层。

注意：别用列表做队列！ #

Python列表的pop(0)操作是O(n)时间复杂度（因为要移动所有元素），数据量大时效率极低。推荐用collections.deque（双端队列），它的popleft()是O(1)操作，专门为高效的首尾操作设计。

实现方式1：直接用collections.deque #

from collections import deque

# 初始化队列
queue = deque()

# 入队操作（enqueue）
queue.append("节点A")
queue.append("节点B")
queue.append("节点C")

# 出队操作（dequeue）
front_node = queue.popleft()  # 取出"节点A"
print(front_node)

# 查看队首元素
if queue:
    print(queue[0])  # 输出"节点B"

# 判断队列是否为空
print(len(queue) == 0)  # False

实现方式2：封装成自定义Queue类 #

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """入队"""
        self.items.append(item)
    
    def dequeue(self):
        """出队，若队列为空返回None"""
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def front(self):
        """查看队首元素"""
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        """判断队列是否为空"""
        return len(self.items) == 0
    
    def size(self):
        """返回队列大小"""
        return len(self.items)

# BFS使用示例
bfs_queue = Queue()
bfs_queue.enqueue("起始节点")
bfs_queue.enqueue("邻居节点1")
bfs_queue.enqueue("邻居节点2")
print(bfs_queue.dequeue())  # 起始节点

三、最佳优先搜索：优先队列（Priority Queue） #

最佳优先搜索（比如A*算法）需要每次取出优先级最高的节点，这时候就要用到优先队列，Python里可以用heapq模块实现最小堆（默认弹出值最小的元素，若要最大堆可以存负值）。

import heapq

# 初始化优先队列（堆）
priority_queue = []

# 入队：存储(优先级, 节点)，heapq会自动按优先级排序
heapq.heappush(priority_queue, (3, "节点C"))
heapq.heappush(priority_queue, (1, "节点A"))
heapq.heappush(priority_queue, (2, "节点B"))

# 出队：弹出优先级最高（值最小）的元素
while priority_queue:
    priority, node = heapq.heappop(priority_queue)
    print(f"取出优先级{priority}的节点：{node}")
# 输出顺序：节点A（1）→节点B（2）→节点C（3）

内容的提问来源于stack exchange，提问作者user9419734