deque
A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
In more detail
CPython implements deque as a doubly linked list of fixed-size blocks, so both ends are cheap. append and pop work on the right, appendleft and popleft on the left. Indexing into the middle is O(n), so a deque is a queue or sliding window, not a replacement for a list.
Example
q = deque(); q.append(job); q.popleft()Related terms
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
- maxlen — An optional deque setting that caps its length; once full, adding at one end silently drops an item from the other end.
- doubly linked list — A linked list in which each node points to both the next and the previous node, so it can be walked either way and any held node removed in O(1).
- Python list — Python's built-in ordered, growable sequence, implemented as a dynamic array of pointers to objects.
- sliding window — The most recent k items of a sequence or stream, which moves forward one item at a time as new data arrives.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers