栈与队列的实现与应用

引言

无论是日常开发还是面试挑战，掌握栈与队列的实现及其应用场景都是每个程序员必备的技能。在这篇文章中，我将基于自己20年的实战经验，分享一些实用技巧和案例，帮助你从理论到实践全面理解栈与队列。

基础语法介绍

栈

栈是一种先进后出（LIFO, Last In First Out）的数据结构。在Python中，可以使用列表（List）来模拟栈的行为。

核心概念

入栈（Push）: 向栈顶添加元素。
出栈（Pop）: 移除栈顶元素。
查看栈顶元素（Peek）: 不移除的情况下查看栈顶元素。
判断栈是否为空（Is Empty）: 检查栈中是否还有元素。

基本操作

class Stack:def __init__(self):self.items = []def push(self, item):"""向栈中添加元素"""self.items.append(item)def pop(self):"""从栈中移除顶部元素"""return self.items.pop()def peek(self):"""返回栈顶元素但不移除"""return self.items[-1] if self.items else Nonedef is_empty(self):"""检查栈是否为空"""return len(self.items) == 0

队列

队列则是一种先进先出（FIFO, First In First Out）的数据结构，在Python中同样可以通过列表或内置模块queue来实现。

核心概念

入队（Enqueue）: 在队尾添加元素。
出队（Dequeue）: 移除队首元素。
查看队首元素（Front）: 不移除的情况下查看队首元素。
判断队列是否为空（Is Empty）: 检查队列中是否还有元素。

基本操作

from queue import Queueclass MyQueue(Queue):def __init__(self):super().__init__()def enqueue(self, item):"""向队列中添加元素"""self.put(item)def dequeue(self):"""从队列中移除头部元素"""return self.get()def front(self):"""返回队首元素但不移除"""with self.not_empty:item = self.queue[0]return itemdef is_empty(self):"""检查队列是否为空"""return self.empty()

基础实例

假设我们需要一个简单的日志记录系统，每次新的日志信息到来时就将其存入一个数据结构中，并且允许我们随时查看最近的日志条目。这里就可以使用栈来实现。

# 日志记录系统
log_stack = Stack()def log(message):log_stack.push(message)print(f"新日志已记录: {message}")def show_last_log():last_log = log_stack.peek()print(f"最近的日志是: {last_log}")log("用户登录")
log("文件上传成功")
show_last_log()  # 输出: 最近的日志是: 文件上传成功

进阶实例

接下来，让我们看看如何利用队列解决一个更复杂的问题：模拟银行系统的排队叫号功能。

# 模拟银行排队系统
bank_queue = MyQueue()def new_customer(customer_id):bank_queue.enqueue(customer_id)print(f"新客户{customer_id}加入队伍")def serve_next():served_customer = bank_queue.dequeue()print(f"正在服务客户{served_customer}")new_customer(1001)
new_customer(1002)
serve_next()  # 输出: 正在服务客户1001

实战案例

在现实世界的应用程序开发中，栈与队列常常扮演着关键角色。例如，在Web服务器处理请求时，通常会使用队列来管理客户端的连接请求；而在编译器中，则可能利用栈来跟踪函数调用的历史。

案例描述

假设我们要为一个简单的在线购物网站开发后台管理系统，其中一个核心需求是能够追踪用户的购物车历史记录。这里，我们可以使用栈来保存用户的购买行为。

解决方案与代码实现

class ShoppingCartHistory:def __init__(self):self.history = Stack()def add_to_cart(self, product_id):self.history.push(product_id)print(f"产品{product_id}已添加至购物车")def view_recent(self):recent_item = self.history.peek()print(f"最近添加的产品是: {recent_item}")def remove_last_item(self):removed_item = self.history.pop()print(f"已移除最后添加的产品: {removed_item}")cart_history = ShoppingCartHistory()
cart_history.add_to_cart("A123")
cart_history.add_to_cart("B456")
cart_history.view_recent()  # 输出: 最近添加的产品是: B456
cart_history.remove_last_item()  # 输出: 已移除最后添加的产品: B456