python中的deque.md

什么是deque

deque即队列队列的一种 — 双端队列（double-ended queue的缩写），是一种数据结构，它允许你在队列的两端进行添加（append）和弹出（pop）操作。

队列是操作受限的线性表，只允许在一端进行插入 (入队)，另一端进行删除 (出队)

操作特性：先进先出 FIFO
队头（Front）：允许删除的一端
队尾（Rear）：允许插入的一端
空队列：不含任何元素的空表

而双端队列就是在队列的基础上，两边都可以作对头和队尾。

Python中deque和列表有很多相似地方，基本使用非常类似。

如何实现

创建

from collections import deque

# 创建一个空队列
new_deque = deque()
print(new_deque)  # deque([])
# '''队列的形式是deque([***])'''
new_deque.clear()  # 清空队列

在创建队列时，我们可以将其他可迭代对象，迭代元素作为队列的元素，怎么理解呢？

队列的形式是deque([])，假如初始化时，里面是一个可迭代对象，那么队列会讲可迭代元素作为他的初始元素，这一点类似解包然后打包，可以通过如下例子看一下

new_deque = deque("hello")
print(new_deque)  # deque(['h', 'e', 'l', 'l', 'o'])
new_deque.clear()  # 清空队列

new_deque = deque(["hello"])
print(new_deque)  # deque(['hello'])
new_deque.clear()  # 清空队列

增删改查等操作

增删改查操作和列表基本一模一样，列表可以用的许多基本方法deque也可以使用(注意：队列没法切片)，这里举例说明.

# 队列中增加元素 --- 入队操作
'''
从下面的操作结果，我们可以看出，队列和列表一样，增加元素都是默认增加在右边的，而且append的操作完全一致
'''
new_deque = deque()
new_deque.append("first element")
new_deque.append("second element")
new_deque.append(["first list"])
print(new_deque)
# deque(['first element', 'second element', ['first list']])


'''队列有一种类型叫做双端队列，顾名思义，两端都可以执行入队出队操作，因此实际上我们也可以从左边执行入队操作'''
new_deque.clear()  # 清空队列
new_deque.appendleft("first element")
new_deque.appendleft("second element")
new_deque.appendleft(["first list"])
print(new_deque)
# deque([['first list'], 'second element', 'first element'])
new_deque.clear()

'''deque 和 list 一样，同样的也支持使用 extend 将「可迭代对象」的所有元素都依次添加进队列，和append类似，extend也可以从左边入队，即 extendleft'''
l1 = [1, 2, 3, 4]
l2 = [5, 6, 7, 8]
l3 = [0, -1, -2, -3]
new_deque = deque(l1)
print(new_deque)
# deque([1, 2, 3, 4])
new_deque.extend(l2)
print(new_deque)
# deque([1, 2, 3, 4, 5, 6, 7, 8])
new_deque.extendleft(l3)
print(new_deque)
# deque([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8])

# 队列的删除操作 --- 出队
'''队列的出队操作使用的方法也是 pop()，当然和入队操作一样，出队可以双端执行，默认也是从右端出队，可以通过如下示例理解'''
# 初始化队列
de = deque([1, 2, 3, 4, 5, 6, 7])
# 默认也是右端出队
print(de.pop())  # 7

# 左端出队
print(de.popleft())  # 1

'''
此外，队列支持许多列表中的方法，如下所示
* count(x)  计算元素x出现的次数
* index(x) - 查找出现给定值x的第一个位置
* remove(x) - 删除第一个x出现的值
* reverse() - 就地反转 deque 

同时，还有一个列表不支持的方法 --- rotate() 旋转，该方法如果理解循环队列就知道其作用了，就是让队列整个转一个元素
'''
rotate_deque = deque([1, 2, 3, 4])
rotate_deque.rotate()
print(rotate_deque)
# deque([4, 1, 2, 3])
'''rotate()默认参数 1 ，即顺时针旋转一个元素，我们可以修改参数来控制旋转的方向和旋转长度'''
rotate_deque.rotate(2)
print(rotate_deque)
# deque([2, 3, 4, 1])
rotate_deque.rotate(-3)
print(rotate_deque)
# deque([1, 2, 3, 4])

deque与list的区别

方法上的区别主要就是上面说的left以及旋转，这些都是针对队列特性做出的适应，队列的先进先出特性、双端队列、循环队列都可以实现。

从上面来看，队列的操作基本和列表一致，但是如果仅是如此的话，列表实现上述功能也是可以的，列表可以使用「切片」操作啊，那么队列的优势在哪？

在deque 中，可以从左侧有效地追加和弹出元素（而在列表中，随着列表的增长，追加和弹出元素的速度会变慢）
在 deque中，可以通过参数 maxlen 控制deque 的最大尺寸 — 这一特性可以帮我们实现一些特殊操作

#  deque 参数 maxlen 将限制 deque 的最大长度 --- 这是队列非常重要的一个特性
'''当队列中的元素已经达到 maxlen 时，此时再向其中添加元素，则会把先进去的元素挤出去 --- 先进先出特性'''
deque_size = 3
deque_max = deque([1, 2, 3], maxlen=deque_size)
print(deque_max)
# deque([1, 2, 3], maxlen=3)
deque_max.append(4)
print(deque_max)
# deque([2, 3, 4], maxlen=3)
'''如上所示，元素 4 将元素 1 挤出了队列'''

这一特性，在实践中非常有用 — 滑动窗口、缓冲区、历史记录 — 利用队列的「先进先出」特性

在处理数据流或时间序列时，你可能需要考虑一个固定大小的滑动窗口

# 滑动窗口
‘‘‘
计算最近 n 个数据点的平均值
’’’

from collections import deque

window_size = 5
window = deque(maxlen=window_size)

for data_point in data_stream:
    window.append(data_point)
    print(f"Current rolling average: {sum(window) / len(window)}")

由于使用的是生成器表达式和一次只能容纳一个元素的 deque ，这意味着您尽可能地节省了空间，这种方法应用到大文件中处理数据时，在空间上的效率就会非常方便

# 查找句子中的最后一个元音
from collections import deque

sentence = "The quick brown fox jumps over the last dog!"
# The last vowel is an 'o' --------------------------^

vowels = set("aeiouAEIOU")

last_vowel = deque((char for char in sentence if char in vowels), maxlen=1)
try:
    print(last_vowel.pop())  # o
except IndexError:
    print("No vowels found.")

在实现网络协议或处理I/O操作时，maxlen 可以作为一个缓冲区大小的限制，历史记录也是同理，存放一定数目的记录，越先记录的越先被删除

buffer = deque(maxlen=1024)  # 假设我们的最大缓冲区大小为1024字节

while receiving_data:
    buffer.append(new_data)
    # 处理buffer中的数据...

更多的例子可以看deque 教程这篇文章的最后一节。

苏格拉底不会写诗

python中的deque.md

什么是deque

如何实现

创建

增删改查等操作

deque与list的区别

reference