Python中栈、队列和优先级队列的实现

关于我

编程界的一名小小程序猿，目前在一个创业团队任team lead，技术栈涉及Android、 Python 、 Java 和Go，这个也是我们团队的主要技术栈。 联系：hylinux1024@gmail.com

栈、队列和优先级队列都是非常基础的数据结构。 Python 作为一种“编码高效”的语言，对这些基础的数据结构都有比较好的实现。在业务需求开发过程中，不应该重复造轮子，今天就来看看些数据结构都有哪些实现。

0x00 栈(Stack)

栈是一种 LIFO (后进先出)的数据结构，有入栈( push )、出栈( pop )两种操作，且只能操作栈顶元素。

在 Python 中有多种可以实现栈的数据结构。

1、list

list 是 Python 内置的列表数据结构，它支持栈的特性，有入栈和出栈操作。只不过用 list 实现栈性能不是特别好。

因为 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 中它就是一个双向列表，可以以常用时间在两端执行添加和删除元素的操作，非常高效，所以它既可以实现栈也可以实现队列。

如果要在 Python 实现一个栈，那么应该优先选择 deque ，而不是 list 。

deque 的入栈和出栈方法也分别是 append() 和 pop() 。

>>> 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 。 它入栈和出栈操作是使用 put() 和 get() ，其中 get() 在 LifoQueue 为空时会阻塞。

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

队列是一种 FIFO (先进先出)的数据结构。它有入队( enqueue )、出队( dequeue )两种操作，而且也是常数时间的操作。

在 Python 中可以使用哪些数据结构来实现一个队列呢？

1、list

list 可以实现一个队列，但它的入队、出队操作就不是非常高效了。因为 list 是一个动态列表，在队列的头部执行出队操作时，会发生整个元素的移动。

使用 list 来实现一个队列时，用 append() 执行入队操作，使用 pop(0) 方法在队列头部执行出队操作。由于在 list 的第一个元素进行操作，所以后续的元素都会向前移动一位。因此 用 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 类似，入队和出队操作分别是 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)

一个近乎 排序 的序列里可以使用优先级队列这种数据结构，它能高效获取最大或最小的元素。

在调度问题的场景中经常会用到优先级队列。它主要有获取最大值或最小值的操作和入队操作。

1、list

使用 list 可以实现一个优先级队列，但它并不高效。因为当要获取最值时需要排序，然后再获取最值。一旦有新的元素加入，再次获取最值时，又要重新排序。所以并推荐使用。

2、heapq

一般来说，优先级队列都是使用堆这种数据结构来实现。而 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 总结一下

很多基础的数据结构在 Python 中已经实现了的，我们不应该重复造轮子，应该选择这些数据结构来实现业务需求。

collections.deque 是一种双向链表，在单线程的情况下，它可以用来实现 Stack 和 Queue 。而 heapq 模块可以帮我们实现高效的优先级队列。

如果要在多并发的情况下使用 Stack 、 Queue 和 PriorityQueue 的话，那么应该选用 queue 模块下类：

• 实现 Stack 的 queue.LifoQueue
• 实现 Queue 的 queue.Queue 或 multiprocessing.Queue
• 实现 PriorityQueue 的 queue.PriorityQueue
• 以上这些类都有 put() 和 get() 方法，且 get() 会在栈/队列为空时阻塞。