python deque双向队列

Python标准库中包含了四种队列，分别是queue.Queue、asyncio.Queue、multiprocessing.Queue、collections.deque。
可见deque是标准库collections中的

Deque队列是由栈或者queue队列生成的（发音是 “deck”，”double-ended queue”的简称）。
Deque 支持线程安全，内存高效添加(append)和弹出(pop)，从两端都可以，两个方向的大概开销都是 O(1) 复杂度。

虽然 list 对象也支持类似操作，不过这里优化了定长操作和 pop(0) 和 insert(0, v) 的开销。
它们引起 O(n) 内存移动的操作，改变底层数据表达的大小和位置。

如果 maxlen 没有指定或者是 None ，deques 可以增长到任意长度。
否则，deque就限定到指定最大长度。一旦限定长度的deque满了，当新项加入时，同样数量的项就从另一端弹出。
限定长度deque提供类似Unix filter tail 的功能。它们同样可以用与追踪最近的交换和其他数据池活动。

deque还支持迭代，清洗，len(d), reversed(d), copy.copy(d), copy.deepcopy(d), 成员测试 in 操作符，
和下标引用 d[-1] 。索引存取在两端的复杂度是 O(1)，在中间的复杂度比 O(n) 略低。要快速存取，使用list来替代。

实现

Data for deque objects is stored in a doubly-linked list of fixed
length blocks. This assures that appends or pops never move any
other data elements besides the one being appended or popped.

关键

fixed length blocks 好像能减少内存

_collectionsmodule.c

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;   
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

leftindex 是干嘛的？

ESON

python deque双向队列

实现

rotate