The idea: a queue with a door at each end
A deque (double-ended queue, said "deck") lets you add and remove items at both ends: push_front, push_back, pop_front and pop_back, each in O(1). The usual way to store it is a circular buffer (ring buffer): one array whose last slot is treated as if it were followed by slot 0. Items never move when you push or pop; only two numbers change.
head, len and the modulo
The deque keeps an array buf of capacity cap, the index head of the front item, and the count len. Item number i of the deque, counting from the front, sits at buf[(head + i) % cap]. So the back item is at (head + len - 1) % cap, and the next push_back writes at tail = (head + len) % cap. The % cap is what makes the array a ring: from index 7 the next index is 0 (Demo: the back wraps around to index 0).
Keeping len (not just head and tail) tells a full buffer from an empty one: in both, tail equals head. Real libraries make cap a power of two so that % cap becomes the cheap bit mask & (cap - 1).
Push and pop at the front
push_front is the new part compared with a plain queue. It moves head one slot left, head = (head - 1) % cap, and writes there. From head = 0 that gives 7, the last slot, so the front wraps backwards around the ring. pop_front reads buf[head] and moves head one slot right. The back end works the same way with len: push_back writes at tail and adds 1 to len, pop_back takes 1 from len and reads the slot it now points past (Demo: push at both ends, head wraps to the end).
In the program's view, a push_front moves every item one place further from the front. In the array nothing moves at all. That is the whole trick: a Python list's insert(0, x) really shifts n items and costs O(n); deque.appendleft(x) costs O(1).
When the buffer is full: grow and unwrap
When len == cap every slot is in use, so the next push first grows the array: allocate 2 × cap slots and copy the items in deque order, the piece from head to the end of the old array first, then the piece that wrapped to the start. The new array does not wrap, so head becomes 0 (Demo: a full buffer doubles to 16 slots, which copies 5 + 3 = 8 items).
A grow costs O(n), but it happens only when the size has doubled since the last one, so n pushes cause fewer than 2n copies in total: O(1) per push amortized, the same argument as for a dynamic array.
Stack, queue, deque
Use only one end and a deque is a stack (last in, first out). Push at one end and pop at the other and it is a queue (first in, first out) (Demo: one end = stack, both ends = queue). That is why the standard libraries offer the deque as their stack and queue:
| Language | Type | front | back | pop on empty |
|---|---|---|---|---|
| Python | collections.deque | appendleft, popleft | append, pop | raises IndexError |
| Java | ArrayDeque | offerFirst, pollFirst | offerLast, pollLast | poll returns null, remove throws |
| Rust | VecDeque | push_front, pop_front | push_back, pop_back | returns None |
| C++ | std::deque | push_front, pop_front | push_back, pop_back | undefined behaviour |
Java's ArrayDeque and Rust's VecDeque are circular buffers like the one on the canvas. Python's deque and C++'s std::deque are built from fixed-size blocks instead (64 items per block in CPython), which avoids the big copy when growing but gives the same O(1) ends (Demo: pop from an empty deque returns None).
What deques are used for
Sliding-window maximum. To report the largest value in every window of k items, keep a deque of indices whose values decrease from front to back. For each new item, pop_back every index with a smaller or equal value, push_back the new index, and pop_front the index that has slid out of the window. The front is always the maximum, and each index is pushed and popped once, so the whole scan is O(n).
0-1 BFS. In a graph whose edges weigh 0 or 1, push a node reached by a 0-edge at the front and one reached by a 1-edge at the back; the deque then stays sorted by distance without a heap (see 0-1 BFS). Work stealing. Each worker thread pushes and pops its own tasks at one end of its deque, while idle threads steal from the other end, so they rarely collide (see Java ForkJoinPool and Work Stealing and The Go Scheduler).
See also Queues: Array Implementation (the same ring with only one door each way), Stack: Array Implementation and Queues: Linked List Implementation (a doubly linked list is the other way to get O(1) at both ends).
What the page leaves out
The canvas starts at 8 slots and stops at 16. It leaves out shrinking the buffer when it gets mostly empty, Rust's smarter grow (it copies only the shorter of the two pieces and may keep head where it is), Java's growth by 50% for big deques, the block layout of CPython and C++ deques, indexing into the middle (d[i]) and insert or remove in the middle (O(n)), iterators that are invalidated by a grow, and lock-free deques such as the Chase–Lev deque used for work stealing.
See where this page fits on the Basics mind map.