Python队列双端队列模块及用法

栈是一种特殊的线性表，只允许在一端进行插入和删除操作。这一端称为栈顶（top），另一端称为栈底（bottom）。

从栈顶插入一个元素称为压入栈，向栈顶插入一个元素称为“压入栈”，对应的英文术语是push；相应地，从栈顶删除一个元素称为弹出，从栈顶删除一个元素称为“出栈”，对应的英文术语是pop。

就栈而言，首先压入栈的元素是在栈底，而栈底的元素只有在上面的所有元素都出栈后才能出栈的堆栈。所以堆栈是一种后进先出（LIFO）线性列表。图 1 显示了堆栈操作的示意图。

队列也是一种特殊的线性表，它只允许对表的前面进行删除操作，对表的后面进行插入操作。执行插入操作的一侧称为队尾，执行删除操作的一侧称为队头。

对于一个队列来说，每个元素总是从队列的后端进入队列，然后等待该元素之前的所有元素出队，当前元素才能出队。因此，队列是一种先进先出（FIFO）的线性列表。队列示意图如图2所示。

双端队列（即此处介绍的 deque）代表一种特殊的队列，它可以在两端同时进行插入、删除操作，如图 3 所示。

对于双端队列，它可以从两端进行插入和删除操作。如果程序把所有的插入和删除操作都固定在一端，那么这个双端队列就变成了栈；如果固定在一端只添加元素，另一端只移除元素，那么它就变成了一个队列。因此，deque 既可以用作队列，也可以用作堆栈。

deque 位于 collections 包下，首先在交互解释器中导入 collections 包，然后输入 [e for e in dir(collections.deque) if not e.startswith('_')] 命令查看所有的deque方法，可以看到如下输出：

>>> from collections import deque
>>> [e for e in dir(deque) if not e.startswith('_')]
['append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate']

从上面的方法可以看出，deque方法基本上有两个版本，体现了它作为双端队列的特点。 deque 的左（left）相当于它的队列的前端，而右（right）相当于它的后端：

append 和 appendleft：在双端队列的右边或左边添加元素，即默认将元素添加到队列的末尾。

pop 和 popleft：在 deque 的右侧或左侧弹出元素，即默认弹出队列末尾的元素。

extend和extendleft：向deque的右边或左边添加多个元素，即默认向队列尾部添加多个元素。

deque中的clear()方法用于清空队列：insert()方法是线性表方法，用于在指定位置插入元素。

如果程序想把deque当作栈使用，就意味着元素只在一端添加和删除，所以只需要调用append和pop方法即可。例如，以下程序：

从上面的方法可以看出，deque方法基本上有两个版本，体现了它作为双端队列的特点。 deque 的左（left）相当于它的队列的前端，而右（right）相当于它的后端：

append 和 appendleft：在双端队列的右边或左边添加元素，即默认将元素添加到队列的末尾。

pop 和 popleft：在 deque 的右侧或左侧弹出元素，即默认弹出队列末尾的元素。

extend和extendleft：向deque的右边或左边添加多个元素，即默认向队列尾部添加多个元素。

deque中的clear()方法用于清空队列：insert()方法是线性表方法，用于在指定位置插入元素。

如果程序想把deque当作栈使用，就意味着元素只在一端添加和删除，所以只需要调用append和pop方法即可。例如，以下程序：

from collections import deque
stack = deque(('Kotlin', 'Python'))
# 元素入栈
stack.append('Erlang')
stack.append('Swift')
print('stack中的元素：' , stack)
# 元素出栈，后添加的元素先出栈
print(stack.pop())
print(stack.pop())
print(stack)

运行上面程序，可以看到如下运行结果：

stack中的元素： deque(['Kotlin', 'Python', 'Erlang', 'Swift'])
Swift
Erlang
deque(['Kotlin', 'Python'])

从上面的运行结果可以看出，程序最后入栈的元素“Swift”最先出栈，这体现了栈的 LIFO 的特征。

假如程序要把 deque 当成队列使用，则意味着一端只用来添加元素，另一端只用来删除元素，因此调用 append、popleft 方法即可。例如如下程序：

from collections import deque
q = deque(('Kotlin', 'Python'))
# 元素加入队列
q.append('Erlang')
q.append('Swift')
print('q中的元素：' , q)
# 元素出队列，先添加的元素先出队列
print(q.popleft())
print(q.popleft())
print(q)

运行上面程序，可以看到如下运行结果：

q中的元素： deque(['Kotlin', 'Python', 'Erlang', 'Swift'])
Kotlin
Python
deque(['Erlang', 'Swift'])

从上面的运行结果可以看出，程序最先加入的元素“Katlin”最先出队，体现了队列的FIFO特性。

此外，deque还有一个rotate()方法，用于将队尾的元素移动到队头，使它们首尾相接。例如，以下程序：

from collections import deque
q = deque(range(5))
print('q中的元素：' , q)
# 执行旋转，使之首尾相连
q.rotate()
print('q中的元素：' , q)
# 再次执行旋转，使之首尾相连
q.rotate()
print('q中的元素：' , q)

运行上面程序，可以看到如下输出结果：

q中的元素： deque([0, 1, 2, 3, 4])
q中的元素： deque([4, 0, 1, 2, 3])
q中的元素： deque([3, 4, 0, 1, 2])

从上面的输出结果来看，每执行一次rotate()方法，都会将deque队列末尾的元素移动到队列的头部，从而形成端到端的效果。