当前位置：首页 > java >正文

Python实现栈和队列及其应用场景解析

java 2025/8/12 16:27:10

在计算机科学中，栈（Stack）和队列（Queue）是两种基础且重要的数据结构，它们分别遵循后进先出（LIFO）和先进先出（FIFO）的原则。本文将详细介绍它们的实现方式和典型应用场景，并提供完整的Python代码示例。

1.栈（Stack）的实现与应用

1. 栈的基本实现

栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子。在Python中，可以使用列表（List）来简单实现：

class Stack:def __init__(self):
        self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):
        self.items.append(item)def pop(self):if self.is_empty():raise IndexError("pop from empty stack")return self.items.pop()def peek(self):if self.is_empty():raise IndexError("peek from empty stack")return self.items[-1]def size(self):return len(self.items)

2. 栈的核心操作

push(item): 将元素添加到栈顶
pop(): 移除并返回栈顶元素
peek(): 返回栈顶元素但不移除
is_empty(): 判断栈是否为空
size(): 返回栈的大小

3. 栈的典型应用场景

3.1 表达式求值

栈在计算表达式值时非常有用，特别是处理后缀表达式（逆波兰表达式）。例如，计算(3+4)2的后缀表达式3 4 + 2 ：

def evaluate_postfix(expression):
    stack = Stack()
    tokens = expression.split()for token in tokens:if token.isdigit():
            stack.push(int(token))else:
            b = stack.pop()
            a = stack.pop()
            result = eval(f"{a}{token}{b}")
            stack.push(result)return stack.pop()

3.2 递归调用模拟

函数调用栈是操作系统实现递归的基础。每次递归调用时，当前状态被压入栈中，返回时弹出：

# 递归计算阶乘
def factorial(n):if n == 0:return 1else:return n * factorial(n-1)# 等效的栈实现
def factorial_stack(n):
    stack = Stack()
    result = 1while n > 0:
        stack.push(n)
        n -= 1while not stack.is_empty():
        result *= stack.pop()return result

3.3 浏览器后退功能

浏览器的后退按钮使用栈来记录用户访问的网页顺序，每次访问新页面时将URL压入栈，点击后退时弹出：

# 简化的浏览器历史记录实现
history = Stack()def visit(url):
    history.push(url)print(f"访问: {url}")def back():if not history.is_empty():
        current = history.pop()if not history.is_empty():
            prev = history.peek()print(f"从 {current} 后退到 {prev}")else:print("已回到第一个页面")else:print("历史记录为空")

2.队列（Queue）的实现与应用

1. 队列的基本实现

队列是一种先进先出（FIFO）的数据结构，类似于排队。在Python中，推荐使用collections.deque（双端队列）来实现高效的队列操作：

from collections import dequeclass Queue:def __init__(self):
        self.items = deque()def is_empty(self):return len(self.items) == 0def enqueue(self, item):
        self.items.append(item)def dequeue(self):if self.is_empty():raise IndexError("dequeue from empty queue")return self.items.popleft()def peek(self):if self.is_empty():raise IndexError("peek from empty queue")return self.items[0]def size(self):return len(self.items)

2. 队列的核心操作

enqueue(item): 将元素添加到队列尾部
dequeue(): 移除并返回队列头部元素
peek(): 返回队列头部元素但不移除
is_empty(): 判断队列是否为空
size(): 返回队列的大小

3. 队列的典型应用场景

3.1 任务调度系统

队列常用于实现多任务调度，例如操作系统中的进程调度：

def task_scheduler(tasks, time_quantum):
    queue = Queue()for task in tasks:
        queue.enqueue(task.copy())    results = []while not queue.is_empty():
        current_task = queue.dequeue()
        name, remaining_time = current_task[0], current_task[1]        executed_time = min(time_quantum, remaining_time)
        remaining_time -= executed_timeprint(f"执行任务 {name} {executed_time} 个时间单位")if remaining_time > 0:
            queue.enqueue([name, remaining_time])else:
            results.append((name, executed_time))return results

3.2 消息队列系统

在分布式系统中，队列常用于实现异步通信的消息队列：

# 简化的消息队列实现
message_queue = Queue()def send_message(message):
    message_queue.enqueue(message)print(f"发送消息: {message}")def process_messages():while not message_queue.is_empty():
        message = message_queue.dequeue()print(f"处理消息: {message}")

3.3 广度优先搜索（BFS）

在图算法中，队列是实现广度优先搜索的核心数据结构：

from collections import dequedef bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)while queue:
        vertex = queue.popleft()print(f"访问节点: {vertex}")for neighbor in graph[vertex]:if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)# 示例图
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}bfs(graph, 'A')

3.栈与队列的对比

特性	栈 (Stack)	队列 (Queue)
数据访问顺序	后进先出 (LIFO)	先进先出 (FIFO)
主要操作	push, pop, peek	enqueue, dequeue, peek
适用场景	表达式求值、递归、浏览器后退	任务调度、消息队列、BFS
Python 实现方式	列表 (append/pop)	deque (append/popleft)
时间复杂度	O(1)	O(1)