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

Taught in

References