跳到主要内容

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}")