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

前言

栈、队列和优先级队列都是非常基础的数据结构。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'
>&g<p>本文来源gao!%daima.com搞$代*!码9网(</p>t;> 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

喜欢 (0)赏

[搞代码]

分享 (0)