之前看公司python的代码居然看到了双端队列，这一点我很惊奇，因为这个数据结构看上去有用，但是生产从来没用过的东西，后来我才知道，项目中使用了双端队列来做一个redis连接池。但是我见过其它的一些连接池实现也是使用双端队列，具体为什么是双端队列而不是普通队列，我觉得还需要自己再去研究考证。
这篇博客主要写写python的双端队列。
python的collections包中有一个deque的数据类型，也就是我们常说的双端队列。双端队列中的元素可以从两端弹出，也可以从两端插入。也就是插入和弹出都在两端进行，所以是一种具有队列和栈的性质的数据结构。
也就是你可以通过如下方式找到得到一个deque
1 | from collections import deque |
以下内容我翻译自python官方文档。
deque能通过传入的一个可迭代对象，将此可迭代对象，从左至右的初始化一个deque。
双端队列deques，算是栈和队列的结合体，deques其实是double-ended queue的缩写。双端队列是线程安全的，支持从两侧高效追加和弹出元素，在任意一方的操作，表现都是O(1).
虽然python的list，能提供类似的操作，但都是基于固定内存长度的优化。而且pop(0)和insert(0)将有O(n)的内存移动成本，因为它改变了内存大小和数据的底层表示。
在version2.4版本。如果没有指定deques的长度，或者deques的长度为空。那么deques是可以增长到任意长度的。否则，deque将以maximum为界，成为一个有界deque，当有界deque的一边添加了新的元素，对应数量的元素将会从deque的另一端被丢弃。有界的deque提供类似unix的tail过滤器的功能，此功能也可以用于被追踪事务和最近在数据池中活跃的数据。
基本用法
你dir(deque)这个数据结构，就会发现，这些可用的方法就和你所理解的deque一个样。可以在两边插入和弹出，所以才说具有栈和队列的性质。
这里注意一个
1 | ['append', 'appendleft', 'clear', 'count', 'extend', 'extendleft', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', ‘rotate'] |
有一个非常有趣的方法是rotate，实际上，就是将这个双端队列，向右推一位，并把最右边的元素插入到最左边。看上去就像是从牌堆的最上方，拿出一张牌，放到最底下（变魔术的可能经常这么说。）
底层实现
我一直好奇双端队列的底层实现，查阅了一些资料后，发现实际上deque是一个块状链表，这样的话，只有内存不够了，才会申请一块新的内存，只有整个内存块都没了，才回去将其释放，而且实际上，还是一个双端链表。一个节点64个指针，一个指向前一个指向后，剩下就是62个指针用来指向对象。