Python中栈、队列与优先级队列的实现方法

Python栈、队列与优先级队列实现详解

前言

栈、队列和优先级队列是计算机科学中极为常见的基础数据结构。Python作为一门注重开发效率的语言，内置了多种高效的数据结构实现。在实际业务开发中，遵循“不要重复造轮子”的原则，直接利用这些标准库提供的数据结构是最佳实践。本文将深入探讨这些数据结构的具体实现方式及其适用场景。

0x00 栈(Stack)的实现方式

0x00 栈(Stack)

栈是一种遵循LIFO（后进先出）原则的数据结构，主要包含入栈（push）和出栈（pop）两种操作，且所有操作仅针对栈顶元素进行。在Python中，有多种方式可以实现栈的功能。

1、list

Python内置的list（列表）数据结构天然支持栈的特性，具备入栈和出栈操作。然而，使用list来实现栈并非性能最优的选择。

这是因为list底层基于动态扩容数组实现。当元素数量增减时，可能触发数组扩容；若在列表头部进行元素的增加或减少，还需要移动整个列表的元素，导致性能损耗。

若坚持使用list实现栈，可调用其append()方法执行入栈操作，使用pop()方法执行出栈操作。

>>> s = []
>>> s.append('one')
>>> s.append('two')
>>> s.append(3)
>>> s
['one', 'two', 3]
>>> s.pop()
3
>>> s.pop()
'two'
>>> s.pop()
'one'
>>> s.pop()
IndexError: pop from empty list

2、collections.deque

deque（双端队列）类在Python中表现为一个双向列表，支持在两端以常数时间复杂度高效地添加和删除元素。因此，deque既适合实现栈，也适合实现队列。

在Python中实现栈时，推荐优先选择deque而非list，以获得更好的性能表现。

deque实现栈的入栈和出栈方法同样为append()和pop()，但其底层优化使得操作效率远高于list。

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: pop from an empty deque

3、queue.LifoQueue

顾名思义，LifoQueue专用于实现栈。其显著特点是线程安全，因此在多线程并发环境下使用栈时，应首选LifoQueue。

其入栈和出栈操作分别通过put()和get()方法完成。需要注意的是，当LifoQueue为空时，get()方法会阻塞线程，直到栈中有新元素加入。

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')
>>> s
<queue.LifoQueue object at 0x109dcfe48>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get()
# 阻塞并一直等待直到栈不为空

0x01 队列(Queue)的实现方式

0x01 队列(Queue)

队列是一种遵循FIFO（先进先出）原则的数据结构，包含入队（enqueue）和出队（dequeue）两种操作，且理想情况下应为常数时间复杂度。接下来探讨Python中实现队列的几种方案。

1、list

虽然list可以实现队列功能，但其入队和出队操作效率较低。由于list是动态列表，在队列头部执行出队操作时，需要移动剩余的所有元素，造成性能瓶颈。

使用list实现队列时，通常用append()进行入队，用pop(0)在头部进行出队。由于每次pop(0)都会导致后续元素前移，因此不推荐使用list来实现队列。

>>> q = []
>>> q.append('1')
>>> q.append('2')
>>> q.append('three')

>>> q.pop(0)
'1'
>>> q.pop(0)
'2'
>>> q.pop(0)
'three'
>>> q.pop(0)
IndexError: pop from empty list

2、collections.deque

前文已述，deque作为双向列表，支持在两端以常数时间进行元素的添加和删除。因此，使用deque来实现队列是高效且推荐的做法。

deque实现队列时，入队使用append()方法，而出队则使用popleft()方法，确保从左侧（头部）移除元素。

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
# 使用popleft出队
>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'
>>> q.popleft()
IndexError: pop from an empty deque

3、queue.Queue

同样地，若需在多线程并发环境下使用队列，应选择线程安全的queue.Queue。

与LifoQueue类似，queue.Queue的入队和出队操作分别对应put()和get()方法。当队列为空时，get()会阻塞线程，直到有元素入队为止。

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<queue.Queue object at 0x110564780>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
# 队列为空不要执行等待
>>> q.get_nowait()
_queue.Empty
>>> q.put('111')
>>> q.get_nowait()
'111'
>>> q.get()
# 队列为空时，会一直阻塞直到队列不为空

4、multiprocessing.Queue

这是专为多进程环境设计的队列。若业务场景涉及多进程间的数据通信，应选用multiprocessing.Queue。

其入队和出队操作同样为put()和get()。当队列为空时，get()会一直阻塞，直到队列中不再为空。

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<multiprocessing.queues.Queue object at 0x110567ef0>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
>>> q.get_nowait()
_queue.Empty
>>> q.get()
# 队列为空时，会一直阻塞直到队列不为空

0x02 优先级队列(PriorityQueue)的实现方式

0x02 优先级队列(PriorityQueue)

优先级队列适用于需要高效获取最大或最小元素的近乎排序序列场景。

在任务调度等场景中，优先级队列应用广泛。其核心操作包括入队以及获取当前优先级最高（最大或最小）的元素。

1、list

使用list可以实现优先级队列，但效率低下。因为获取最值需要排序，而每次新元素加入后再次获取最值时需重新排序，开销巨大。因此，不推荐使用list实现优先级队列。

2、heapq

通常，优先级队列基于堆数据结构实现。Python标准库中的heapq模块提供了堆的实现，默认情况下构建的是最小堆。

入队操作使用heappush()，出队（获取最小元素）操作使用heappop()。

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, 'code'))
>>> heapq.heappush(q, (1, 'eat'))
>>> heapq.heappush(q, (3, 'sleep'))
>>> q
[(1, 'eat'), (2, 'code'), (3, 'sleep')]
>>> while q:
	next_item = heapq.heappop(q)
	print(next_item)

	
(1, 'eat')
(2, 'code')
(3, 'sleep')

3、queue.PriorityQueue

queue.PriorityQueue内部封装了heapq，其不同之处在于提供了线程安全机制。在并发环境下，应选择使用PriorityQueue。

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, 'code'))
>>> q.put((1, 'eat'))
>>> q.put((3, 'sleep'))
>>> while not q.empty():
	next_item = q.get()
	print(next_item)

(1, 'eat')
(2, 'code')
(3, 'sleep')

0x03 总结与并发场景建议

0x03 总结一下

Python中已实现了许多基础数据结构，开发者应避免重复造轮子，直接选用这些数据结构来满足业务需求。collections.deque作为一种双向链表结构，在单线程场景下，可高效用于实现Stack和Queue。而heapq模块则能提供高效的优先级队列支持。

若需在多并发环境下使用Stack、Queue和PriorityQueue，应选用queue模块下的相应类：

• 实现Stack的queue.LifoQueue
• 实现Queue的queue.Queue或multiprocessing.Queue
• 实现PriorityQueue的queue.PriorityQueue
• 上述类均提供put()和get()方法，且get()在栈/队列为空时会阻塞线程。

0x04 推荐学习资料

0x04 学习资料

Python Tricks: A Buffet of Awesome Python Features

——Dan Bader

以上即为本文的全部内容，希望这些内容对您的学习或工作有所助益。感谢支持。