一、使用deque代替list
Python提供了两种结构来实现队列:list和deque。list在 Python 中实现的是一个支持动态数组大小的顺序表,而deque实现了一个双向队列,它除了实现了普通队列的所有方法外,还实现了在线性时间复杂度内在队列两端插入(也就是说在最左边插入和在最右边插入)元素的方法。
对比list,在进行任何元素的插入或者取出操作时,都会导致一些元素的“移动”,这样就会带来O(n)的复杂度,虽然对于小规模的数据并不会有很大的影响,但是当数据规模变大时就会变得不太优秀,更进一步,双向队列的实现有利于各种类型的算法。
下面是使用deque代替list的示例代码:
from collections import deque queue = deque() queue.append(1) queue.append(2) queue.append(3) queue.popleft()
二、使用队列实现广度优先搜索(BFS)
BFS(广度优先搜索)是一种在树、图等数据结构中很常见的搜索算法,广泛应用于最短路径、拓扑排序等领域。BFS基于队列先进先出的特性,使用队列可帮助我们快速且高效地实现BFS算法。
下面是使用队列实现BFS的示例代码:
from collections import deque def bfs(graph, start_node): visited = [] queue = deque([start_node]) while queue: node = queue.popleft() if node not in visited: visited.append(node) queue += graph[node] - set(visited) return visited
三、使用队列实现多线程
在Python中,使用了`Threading`、`Asyncio`等包来开发多线程程序,然而这些包的底层都是使用了队列来实现多线程操作,这是因为Python中的队列拥有高并发和高吞吐率的特性,是实现多线程高效的必备利器。
下面是使用有限制的队列(queue)实现多线程程序的示例代码:
import queue import threading q = queue.Queue() def worker(q, n): while True: item = q.get() if item is None: break print("任务 %s 开始处理 %s" % (n, item)) q.task_done() # 启动线程,开启多次任务并行处理 threads = [] for i in range(5): t = threading.Thread(target=worker, args=(q, i)) t.start() threads.append(t) # 入队任务 for i in range(20): q.put(i) # 阻塞,直到所有任务完成 q.join() # 停止线程,退出任务 for i in range(5): q.put(None) for t in threads: t.join()