今天继续写一写那些某种程度上可以（并且应该）代替列表工作的数据结构：
队列（们）
本菜鸡一直都记得在数据结构课上第一次接触堆栈时对它们的逻辑和操作油然而生的一种类似于膜拜的情绪——当然这种情绪在现在看来多少有点青涩，毕竟很多时候为了特殊的需求，连堆栈都是不那么首选的方法，但无论如何，先进先出、后进先出这种简单的逻辑，还是有必要说一下：
利用.append()和.pop(0)的方法，列表也可以当作栈或队列使用（事实上本菜鸡前两天做leetcode就是这么过来的），但是我们有时候要删除一个序列的第一个元素或者在第一个元素前面加元素，列表就会耗费大量时间，因为列表为了实现这个功能会在物理层移动列表中所有的元素，要知道，列表在实际情况使用的时候和leetcode甚至我们上课做的小题还不一样，元素个数经常是以“几个零”为单位的。
为了解决这个问题，我们将使用双向队列来进行弥补；
学过（基于任何语言的）数据结构的读者应该对这种类型不陌生，从本菜鸡寥落的经验来看，这种数据结构的优势让几乎所有语言都努力通过某种方式实现它，所以如果你已经简单看过C++或者什么语言的参考书，那么应该对以下的操作方法驾轻就熟：
1 from collections import deque
2 dq = deque(range(0, 10), maxlen=10)
3 dq.rotate(3)
4 dq.appendleft(55555)
5 dq.append(66666)
6 dq.extendleft([33333,44444])
7 dq.extend([77777,88888,99999])
# 假设234567行后面都有print，结果：
2 deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
3 deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
4 deque([55555, 7, 8, 9, 0, 1, 2, 3, 4, 5], maxlen=10)
5 deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 66666], maxlen=10)
6 deque([44444, 33333, 7, 8, 9, 0, 1, 2, 3, 4], maxlen=10)
7 deque([8, 9, 0, 1, 2, 3, 4, 77777, 88888, 99999], maxlen=10)
虽说这些操作方法看上去都很熟悉，但有些操作的内在逻辑就有些令人模糊，我们逐个解释：
2 maxlen的值：maxlen代表这个双向队列的最大长度，由于Python中对指针的忽视，队列确实是有最大长度的，而且一旦设定就不能改变；
3 rotate函数：整体移动函数，接受一个参数n，当参数为正时，把后n个元素提调到前面，当为负数时，把前n个元素放到后面，在放的过程中，自元素段内部的顺序不变；
4 appendleft函数：由于双端队列要支持在两端进行加入、删除，所以在append后加一个left一以示标记；
5 append函数，没啥好说的，但和appendleft一样，当队列已经满了还要加，会把另一头的元素“顶”出来；
6 extendleft函数：也会顶元素，但从我们的例子中很容易看得出，extend一个列表（没错，extend的是一个列表）是逆序加入的，这也许是因为调用了迭代器的原因；
7 extend函数：没什么好说的；
当然，我们也显然可见，双向队列的优化基本上都是对于头、尾元素或子队列而言，所以在队列中间要进行操作时，速度就会有点不尽如人意，因此，双向队列的引入一般应用于以下情况：
需要频繁的对一组元素在头尾进行简单操作，或者搞一个数据类型来存放“最近用到的几个元素”；
当然，Python也通过其他方式实现了一些其他类型队列，包括queue、multiprocessing、asyncio、heapq等等，这些队列（或者类队列）各有特色，我们用到的时候再说不迟；
网友评论