Python数据结构之栈、队列和堆使用

大家好，欢迎来到IT知识分享网。

在Python中，也有实现数据结构的办法，正如大学《数据结构》教材里编写的栈、队列和堆使用。

在互联网主流技术中，MQ消息队列更是利用了队列的特性而编制，作为堆栈的使用，其特性也被应用于广大场景。

学好数据结构，就掌握了编程的根基，本文将从栈、队列和堆来讲解其在Python中的用法。

分享之前，大家先安装Python环境，环境包推荐官方Anaconda环境包，开发工具使用PyCharm，也可以用jupyter notebook或者eclipse来编辑代码。

一、栈

它遵循后进先出（LIFO, Last In First Out）的原则。Python内置的数据结构如列表（list）可以很容易地模拟栈的行为。

示例：

stack = []

stack.append(1)

stack.append(2)

print(stack.pop())

1.1创建一个空栈

可以通过创建一个空列表来初始化一个栈：

stack = []

1.2压栈（Push）

向栈顶添加元素的操作称为压栈。使用列表的 append() 方法实现：

stack.append(1)

stack.append(2)

stack.append(3)

1.3弹栈（Pop）

从栈顶移除并返回元素的操作称为弹栈。使用列表的 pop() 方法实现：

if stack:

item = stack.pop()

print(item) # 输出: 3

else:

print(“栈为空”)

1.4查看栈顶元素（Peek）

查看栈顶元素而不移除它，可以通过索引访问：

if stack:

print(stack[-1]) # 输出: 2

else:

print(“栈为空”)

1.5判断栈是否为空

检查列表长度是否为0来判断栈是否为空：

if not stack:

print(“栈为空”)

else:

print(“栈不为空”)

1.6应用场景示例

一个常见的栈的应用是括号匹配问题，例如检查字符串中的括号是否正确配对：

def is_balanced(parentheses):

stack = []

for p in parentheses:

if p == ‘(‘:

stack.append(p)

elif p == ‘)’:

if not stack:

return False

stack.pop()

return len(stack) == 0

print(is_balanced(“((()))”)) # 输出: True

print(is_balanced(“(()”)) # 输出: False

1.7完整示例

打开PyCharm工具，打开chatglm-demo项目，新建chapter03包：

在chapter03包下新建demo01.py文件:

拷贝以下代码到demo01.py文件中：

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()

else:

raise IndexError(“pop from empty stack”)

def peek(self):

if not self.is_empty():

return self.items[-1]

else:

return None

def size(self):

return len(self.items)

def is_balanced(parentheses):

stack = Stack()

for p in parentheses:

if p in “([{“:

stack.push(p)

elif p in “)]}”:

if stack.is_empty():

return False

top = stack.pop()

if (p == “)” and top != “(“) or \

(p == “]” and top != “[“) or \

(p == “}” and top != “{“):

return False

return stack.is_empty()

# 测试代码

test_cases = [

“()”,

“([])”,

“{[()]}”,

“([)]”,

“({[})”,

“((()))”,

“(()”,

“)(“

]

for case in test_cases:

result = is_balanced(case)

print(f”{case}: {result}”)

透过截图来分析：

创建Stack栈类，依据缩进来创建类和方法：

栈大小：

检查栈是否平衡：

测试代码并执行：

右键运行demo01.py文件，查看结果：

揭示了堆栈的使用。

二、队列

它是一种常见的数据结构，它遵循先进先出（FIFO, First In First Out）的原则。Python提供了多种方式来实现队列，包括标准库中的queue模块和内置的数据结构如列表（list）或双端队列（deque）。

示例：

from queue import Queue

q = Queue()

q.put(1)

q.put(2)

print(q.get())

2.1使用列表实现队列

虽然列表可以用来实现队列，但它的效率不高，因为插入和删除操作在列表两端的时间复杂度不同。具体来说：

append() 在列表末尾添加元素，时间复杂度为 O(1)。

pop(0) 从列表开头移除元素，时间复杂度为 O(n)。

因此，使用列表实现队列并不是最佳选择，但在某些简单场景下仍然可以使用。

queue = []

# 入队（Enqueue）

queue.append(1)

queue.append(2)

queue.append(3)

# 出队（Dequeue）

if queue:

item = queue.pop(0)

print(item) # 输出: 1

else:

print(“队列为空”)

新建demo02.py文件，拷贝以上代码：

右键运行demo02.py，查看结果：

2.2使用双端队列（deque）

collections.deque 是一种高效的数据结构，支持两端的快速插入和删除操作。使用 deque 可以更高效地实现队列。

from collections import deque

queue = deque()

# 入队（Enqueue）

queue.append(1)

queue.append(2)

queue.append(3)

# 出队（Dequeue）

if queue:

item = queue.popleft()

print(item) # 输出: 1

else:

print(“队列为空”)

新建demo03.py文件，拷贝以上代码:

右键运行demo03.py，查看运行结果：

2.3使用标准库 queue.Queue

Python 标准库中的 queue.Queue 提供了一个线程安全的队列实现，适用于多线程环境。

import queue

q = queue.Queue()

# 入队（Enqueue）

q.put(1)

q.put(2)

q.put(3)

# 出队（Dequeue）

try:

item = q.get(block=False)

print(item) # 输出: 1

except queue.Empty:

print(“队列为空”)

创建demo04.py文件，拷贝以上代码：

右键运行demo04.py文件，查看结果：

2.4完整示例

队列还可应用于任务调度场景：

import queue

import threading

def worker(q):

while True:

try:

task = q.get(block=False)

print(f”处理任务: {task}”)

q.task_done()

except queue.Empty:

break

# 创建队列

tasks = queue.Queue()

# 入队任务

tasks.put(“任务1”)

tasks.put(“任务2”)

tasks.put(“任务3”)

# 创建并启动线程

threads = []

for _ in range(3):

t = threading.Thread(target=worker, args=(tasks,))

threads.append(t)

t.start()

# 等待所有任务完成

tasks.join()

# 等待所有线程结束

for t in threads:

t.join()

print(“所有任务处理完毕”)

新建demo05.py文件，拷贝以上代码：

右键运行demo05.py文件，查看结果：

三、堆

堆（Heap）是一种非常重要的数据结构，通常用于实现优先队列（Priority Queue）。Python的标准库heapq提供了高效的操作堆的方法。堆的特点是父节点的值总是小于或等于（对于最小堆）或大于或等于（对于最大堆）其子节点的值。

示例：

import heapq

heap = []

heapq.heappush(heap, 3)

heapq.heappush(heap, 1)

print(heapq.heappop(heap))

3.1使用 heapq 模块实现最小堆

import heapq

# 创建一个空堆

heap = []

# 入堆（Push）

heapq.heappush(heap, 5)

heapq.heappush(heap, 3)

heapq.heappush(heap, 8)

heapq.heappush(heap, 1)

# 出堆（Pop）

while heap:

item = heapq.heappop(heap)

print(item)

# 输出: 1, 3, 5, 8

新建demo06.py文件，拷贝以上代码：

右键运行demo06.py文件，查看结果：

3.2使用 heapq 模块实现最大堆

默认情况下，heapq 模块实现的是最小堆。为了实现最大堆，可以使用负数进行转换。

import heapq

# 创建一个空堆

max_heap = []

# 入堆（Push）

heapq.heappush(max_heap, -5)

heapq.heappush(max_heap, -3)

heapq.heappush(max_heap, -8)

heapq.heappush(max_heap, -1)

# 出堆（Pop）

while max_heap:

item = -heapq.heappop(max_heap)

print(item)

# 输出: 8, 5, 3, 1

新建demo07.py文件，拷贝以上代码：

右键运行demo07.py文件，查看结果：

3.3使用 heapq 模块实现优先队列

优先队列是一种常用的数据结构，其中每个元素都有一个优先级。heapq 可以很方便地实现优先队列。

import heapq

# 创建一个空堆

pq = []

# 入队（Push）

heapq.heappush(pq, (2, ‘任务2’))

heapq.heappush(pq, (1, ‘任务1’))

heapq.heappush(pq, (3, ‘任务3’))

# 出队（Pop）

while pq:

priority, task = heapq.heappop(pq)

print(task)

# 输出: 任务1, 任务2, 任务3

新建demo08.py文件，拷贝以上代码：

右键运行demo08.py文件，查看结果：

3.4使用 heapq 模块实现堆排序

堆排序是一种高效的排序算法，利用堆的特性进行排序。

import heapq

# 创建一个列表

arr = [5, 3, 8, 1, 9, 2]

# 将列表转换成堆

heapq.heapify(arr)

# 堆排序

sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]

print(sorted_arr) # 输出: [1, 2, 3, 5, 8, 9]

将以上代码拷贝至demo09.py文件：

右键运行demo09.py文件，查看结果：

3.5使用 heapq 模块实现堆的其他操作

除了基本的入堆和出堆操作外，heapq 还提供了其他一些有用的操作。

import heapq

# 创建一个空堆

heap = []

# 入堆（Push）

heapq.heappush(heap, 5)

heapq.heappush(heap, 3)

heapq.heappush(heap, 8)

heapq.heappush(heap, 1)

# 获取堆顶元素（不弹出）

print(heapq.nsmallest(1, heap)[0]) # 输出: 1

# 获取前k个最小元素

print(heapq.nsmallest(2, heap)) # 输出: [1, 3]

# 获取前k个最大元素

print(heapq.nlargest(2, heap)) # 输出: [8, 5]

新建demo10.py文件，拷贝以上代码：

右键运行demo10.py文件，查看结果：

以上就是栈、队列和堆使用的文档讲解，更多Python和AI技术学习欢迎关注博主，目前是打好Python基础时期。