双端队列（Deque），是一种类似于队列的元素的有序集合。它拥有两端，队首和队尾，并且元素保持在当前的位置。双端队列的一个不同点就是，添加和删除元素的位置不受限制。新元素可以在队首或者队尾添加。同样地，双端队列中的元素可以从两端弹出。在某种意义上，这种混合的线性结构同时具有栈和队列的性质。
很重要的一点，即使双端队列具有栈和队列的特性，但它不会被强制执行的LIFO和FIFO操作。这取决于你做出统一的添加和删除操作。
双端队列的操作如下：
|
1 2 3 4 5 6 7 |
Deque() 创建一个空的双端队列，无参数，返回值是空队列。 add_front(item) 在队首添加入一个元素，参数是数据项，无返回值。 add_rear(item) 在队尾添加入一个元素，参数是数据项，无返回值。 remove_front() 删除队首的元素，不需要参数，返回值是被删除的元素，队列本身有变化。 remove_rear() 删除队尾的元素，不需要参数，返回值是被删除的元素，队列本身有变化。 is_Empty() 检测队列是否为空。无参数，返回布尔值。 size() 返回队列元素的个数。无参数，返回一个整数。 |
双端队列操作举例：
| Deque Operation | Deque Contents | Return Value |
|---|---|---|
| d.isEmpty() | [] | True |
| d.addRear(4) | [4] | |
| d.addRear(‘dog’) | [‘dog’,4,] | |
| d.addFront(‘cat’) | [‘dog’,4,’cat’] | |
| d.addFront(True) | [‘dog’,4,’cat’,True] | |
| d.size() | [‘dog’,4,’cat’,True] | 4 |
| d.isEmpty() | [‘dog’,4,’cat’,True] | False |
| d.addRear(8.4) | [8.4,’dog’,4,’cat’,True] | |
| d.removeRear() | [‘dog’,4,’cat’,True] | 8.4 |
| d.removeFront() | [‘dog’,4,’cat’] | True |
列表 VS 双端队列
双端队列支持线程安全，在双端队列的任何一端执行添加和删除操作，它们的内存效率几乎相同（时间复杂度为O(1)）。
虽然list也支持类似的操作，但是它对定长列表的操作表现很不错，而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时，其时间复杂度就变为O(n)了。
在双端队列中最好不使用切片和索引，你可以用popleft和appendleft方法，双端队列对这些操作做了优化。在两端的索引访问时间复杂度为O(1)，但是访问中间元素的时间复杂度为O(n)，速度较慢，对于快速随机的访问，还是用列表代替。
列表用于随机访问和定长数据的操作，包括切片，而双端队列适用于在两端压入或弹出元素，索引（但不包括切片）的效率可能低于列表。
实现双端队列：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Deque: """模拟双端队列""" def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def addFront(self, item): self.items.append(item) def addRear(self, item): self.items.insert(0,item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) |
以下是测试代码：
|
1 2 3 4 5 6 7 8 9 10 11 |
d=Deque() print(d.isEmpty()) d.addRear(4) d.addRear('dog') d.addFront('cat') d.addFront(True) print(d.size()) print(d.isEmpty()) d.addRear(8.4) print(d.removeRear()) print(d.removeFront()) |
