Python 数据结构实现指南
栈的实现
基于列表实现后进先出的栈结构。
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
raise IndexError("栈为空")
def peek(self):
if not self.is_empty():
return self.items[-1]
raise IndexError("栈为空")
def size(self):
return len(self.items)
队列的实现
使用 deque 实现高效的队列操作。
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
raise IndexError("队列为空")
def front(self):
if not self.is_empty():
return self.items[0]
raise IndexError("队列为空")
def size(self):
return len(self.items)
优先队列实现
使用 heapq 实现优先队列。
import heapq
class PriorityQueue:
def __init__(self):
self.items = []
def push(self, item, priority):
heapq.heappush(self.items, (-priority, item))
def pop(self):
if self.items:
return heapq.heappop(self.items)[1]
raise IndexError("优先队列为空")
def peek(self):
if self.items:
return self.items[0][-1]
raise IndexError("优先队列为空")
双端队列实现
支持两端操作的队列实现。
class Deque:
def __init__(self):
self.items = deque()
def add_front(self, item):
self.items.appendleft(item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if not self.is_empty():
return self.items.popleft()
raise IndexError("双端队列为空")
def remove_rear(self):
if not self.is_empty():
return self.items.pop()
raise IndexError("双端队列为空")
def is_empty(self):
return len(self.items) == 0
实际应用示例
使用栈实现括号匹配。
def is_balanced(expression):
stack = Stack()
brackets = {")": "(", "]": "[", "}": "{"}
for char in expression:
if char in "({[":
stack.push(char)
elif char in ")}]":
if stack.is_empty():
return False
if stack.pop() != brackets[char]:
return False
return stack.is_empty()
使用队列实现任务调度。
class TaskScheduler:
def __init__(self):
self.tasks = Queue()
def add_task(self, task):
self.tasks.enqueue(task)
def execute_tasks(self):
while not self.tasks.is_empty():
task = self.tasks.dequeue()
print(f"执行任务 {task}")