python collections deque解析（双端队列、双向队列）（用于实现高效队列和栈）（头尾插删比List效率高，下标访问、中间插入操作效率较低）（maxlen自动限制长度）_python中提供了双端队列deque,可以将一个deque对象st作为栈,其栈操作是,取栈

Python3 deque解析

在Python中，deque是一个线程安全、可以快速从两端添加或者删除元素的数据类型。它可以被用来创建一种特殊类型的容器，如队列和栈。在这篇文章中，将会深入探讨Python中deque的实现，包括其基本操作，用法，以及如何利用deque进行高效的数据处理。

deque 的概述

deque（双端队列）是python collections模块的一部分，提供了从列表的首尾两端进行append和pop的高效方法。相比于list，deque提供了更高效的表头插入和删除操作。

from collections import deque
dq = deque([1,2,3,4,5])
1
2

基本操作

添加元素

deque支持从两端添加元素，使用append()方法从尾部添加，使用appendleft()方法从头部添加。

dq.append(6)  # 添加到尾部
dq.appendleft(0)  # 添加到头部
1
2

删除元素

同样地，deque也支持从两端删除元素，使用pop()方法从尾部删除，使用popleft()方法从头部删除。

dq.pop()  # 从尾部删除
dq.popleft()  # 从头部删除
1
2

deque数据结构不直接提供了通过下标（索引）删除元素的方法。但可以通过组合使用其它方法达到类似效果。

一种方法是利用rotate()函数配合popleft()或者pop()方法，将要删除的元素移动到deque的一端然后进行删除：

from collections import deque

dq = deque([1, 2, 3, 4, 5])

def delete_by_index(dq, index):
    dq.rotate(-index)
    dq.popleft()
    dq.rotate(index)

delete_by_index(dq, 2)  # 删除第三个元素
print(dq)  # 输出：deque([1, 2, 4, 5])
1
2
3
4
5
6
7
8
9
10
11

在上述代码中，rotate(n)函数会将deque中的元素向右循环移动n步。如果n为负数，则元素会向左循环移动。因此，rotate(-index)可以将要删除的元素移动到deque的最左边，然后使用popleft()进行删除。

这种方法可能会改变deque中元素的顺序。在删除操作完成后，需要再次调用rotate(index)恢复原来的顺序。

另外一种方式是，先将deque转换为列表，进行删除操作后再转回deque：

dq = deque([1, 2, 3, 4, 5])
list_dq = list(dq)
del list_dq[2]  # 删除第三个元素
dq = deque(list_dq)
print(dq)  # 输出：deque([1, 2, 4, 5])
1
2
3
4
5

这种方法相对直观简单，但是，频繁地在deque和list之间进行转换可能会引入额外的性能开销。

访问元素

deque支持索引访问，但不建议这么做，因为在deque中这是一个慢速操作。

dq[1]  # 访问第二个元素
1

插入元素

deque也提供了插入元素的方法，名为insert(i, x)。这个方法可以在deque中的指定位置插入一个元素。

dq = deque([1, 2, 3, 4, 5])
dq.insert(2, 'a')  # 在第三个位置插入字符'a'
print(dq)  # 输出：deque([1, 2, 'a', 3, 4, 5])
1
2
3

需要注意的是，尽管deque提供了插入操作，但由于其内部实现的特性，插入操作的效率相对较低，特别是当插入位置靠近deque中间时。如果需要频繁进行插入操作，可能需要考虑使用其他数据结构，如list。

另外，如果尝试在超过deque长度的位置插入元素，将会抛出IndexError异常。

dq.insert(10, 'b')  # IndexError: deque index out of range
1

所以在执行插入操作之前，建议先检查索引是否在deque的长度范围内。可以使用len()函数来获取deque的长度。

if 10 < len(dq):
    dq.insert(10, 'b')
else:
    print('Insertion index is out of range.')
1
2
3
4

高级用法

deque限长列表

deque可以设置最大长度，当超出设定长度时，新加入元素会挤掉旧元素。

dq = deque(maxlen=3)
for i in range(5):
    dq.append(i)
print(dq)  # 输出：deque([2, 3, 4], maxlen=3)
1
2
3
4

使用deque实现队列和栈

deque非常适合用于实现队列和栈数据结构。对于栈，可以使用append()和pop()方法来添加和删除元素。对于队列，可以使用append()和popleft()方法来添加和删除元素。

# 栈的实现
stack = deque()
stack.append('a')
stack.append('b')
stack.append('c')
print(stack.pop())  # 输出：'c'

# 队列的实现
queue = deque()
queue.append('a')
queue.append('b')
queue.append('c')
print(queue.popleft())  # 输出：'a'
1
2
3
4
5
6
7
8
9
10
11
12
13

deque与list的性能对比

在许多操作中，deque提供了比list更高效的方法。特别是当涉及到添加或删除元素时，deque的性能明显优于list。

参考以下测试代码：

import time
from collections import deque

n = 10**6

def test_deque(n):
    d = deque()
    for i in range(n):
        d.append(i)
    while len(d)>0:
        d.popleft()

def test_list(n):
    l = list()
    for i in range(n):
        l.append(i)
    while len(l)>0:
        l.pop(0)

start = time.time()
test_deque(n)
print('deque:', time.time()-start)

start = time.time()
test_list(n)
print('list:', time.time()-start)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

在上述代码中，将会比较在deque和list中分别添加和删除1百万个元素所需的时间。从实验结果可以看出，deque的性能明显优于list（0.26s vs 516s）：

结论

在Python中，deque是一个非常强大的数据结构，它提供了许多有用的方法来处理数据。尤其是当需要频繁地在表头插入或删除数据时，deque比传统的list更具优势。同时，由于其高效的性能，deque也适合用于实现其他复杂的数据结构，如队列和栈。

参考文献：

Python docs - collections.deque

Python data structures: deque