3 . python Collectio

语法：

class collections.deque([iterable[, maxlen]])

返回从左到右初始化的新deque对象（使用append()）和来自iterable（可迭代的）的数据。 如果未指定iterable(迭代)，则新的deque为空。

    Deques是堆栈和队列的概括（名称发音为“deck”，是“双端队列”的缩写）。 

    Deques支持线程安全，高效的内存追加和从"双端队列"的弹出，并且在任一方向都具有大致相同的O(1) [注：时间复杂度]性能。

    尽管列表对象支持类似的操作，但是它们针对快速固定长度操作进行了优化，并且会导致pop(0)和insert(0, v)操作的O(n)内存移动成本，这些操作改变底层数据表示的大小和位置。

    如果未指定maxlen或为None，则deques可能会增长到任意长度。 否则，deque被限制为指定的最大长度。一旦有限长度的deque已满，当添加新项目时，相应数量的项目将从相反的一端被丢弃。 有界长度deques提供类似于Unix中尾部过滤器的功能。 它们也可用于跟踪仅涉及最近活动的事物和其他数据池。

Deque对象支持以下方法：

append(x)                           将x添加到双端队列的右侧。

appendleft(x)                  将x添加到双端队列的左侧。

clear()                               删除deque中的所有元素，使其长度为0。

copy()                                 创建一个deque的浅表副本。3.5版本中的新功能。

count(x)                             计算deque元素的数量等于x。3.2版本中的新功能

extend(iterable)                 通过追加iterable参数中的元素来扩展双端队列的右侧。

extendleft(iterable)        通过追加iterable中的元素来扩展双端队列的左侧。请注意，一系列左边追加结果会颠倒迭代参数中元素的顺序。

index(x[, start[, stop]])       返回deque中的x的位置（在索引开始处或索引停止之前）。如果未找到，则返回第一个匹配或引发ValueError。

insert(i, x)                        将x插入位置i处的deque中。3.5版本中的新功能。如果插入会导致有界的deque超出maxlen，则会引发IndexError。

pop()                                   从deque的右侧移除并返回一个元素。 如果没有元素存在，则引发IndexError。

popleft()                          从deque的左侧移除并返回一个元素。 如果没有元素存在，则引发IndexError

remove(value)                   删除第一次出现的值。 如果找不到，则会引发ValueError。

reverse()                         反序排列deque的元素，然后返回None。New in version 3.2.

rotate(n=1)                     向右旋转deque n个步。 如果n为负数，则向左旋转。

解释：

当deque不为空时：

向右旋转一个等同于 d.appendleft(d.pop())

向左旋转一个等同于 d.append(d.popleft())

另，Deque对象还提供一个只读属性：

maxlen

        最大的deque的大小，如果×××限，则为None.    [3.1版本引入]

    除上述之外，deques支持迭代、pickling、len(d)、reverse(d)、copy.copy(d)、copy.deepcopy(d)，使用 in 运算符进行成员资格测试，以及下标引用，例如：d[-1]。

    索引访问在两端都是O(1)，但在中间减慢到O(n)。

    对于快速随机访问，请改用列表。

    从版本3.5开始，deques开始支持__add__(), __mul__(), __imul__()。

    下面是例子：

image.png

deque Recipes（食谱？？？黑人问号脸）

本节介绍处理deques的各种方法。

有界长度的deques提供了类似于Unix中尾部过滤器的功能：

image.png

#返回文件的最后n行

另一种使用deques的方法是通过向右追加并弹出到左边来维护一系列新添加的元素：

image.png

    rotate()方法提供了一种实现双端切片和删除的方法。

    例如，del d[n]的纯Python实现依赖于rotate()方法来定位要弹出的元素：

image.png

    为了实现deque切片，使用类似的方法来应用rotate( )来将目标元素置于双端队列的左侧。 

    使用popleft( )删除旧条目，使用extend( )添加新条目，然后反转旋转。 

    通过该方法的细微变化，很容易实现Forth样式的堆栈操作，如dup，drop，swap，over，pick，rot和roll。