双端队列(Deque),是一种类似于队列的元素的有序集合。它拥有两端,队首和队尾,并且元素保持在当前的位置。双端队列的一个不同点就是,添加和删除元素的位置不受限制。新元素可以在队首或者队尾添加。同样地,双端队列中的元素可以从两端弹出。在某种意义上,这种混合的线性结构同时具有栈和队列的性质。

很重要的一点,即使双端队列具有栈和队列的特性,但它不会被强制执行的LIFO和FIFO操作。这取决于你做出统一的添加和删除操作。

双端队列的操作如下:

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),速度较慢,对于快速随机的访问,还是用列表代替。

列表用于随机访问和定长数据的操作,包括切片,而双端队列适用于在两端压入或弹出元素,索引(但不包括切片)的效率可能低于列表。

实现双端队列:

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)

以下是测试代码:

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())