AlgoScope

Deque

structurebeginnerTime O(1)Space O(n)

A queue that is open at both ends. Push or pop at the front, push or pop at the back, all in O(1). A ring buffer makes that cheap: the front index can step backward as easily as forward.

An empty deque. Items can join or leave at either end, the front or the back, in O(1).

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. pop-back: which value leaves?

    • 9
    • 3
    • 5

    Answer: 3. 3 is at the back. Unlike a queue, a deque can drop either end, and this call named the back.

  2. pop-front: which value leaves?

    • 7
    • 5
    • 9

    Answer: 7. 7 is at the front. Unlike a stack, a deque can drop either end, and this call named the front.

  3. pop-back: which value leaves?

    • 9
    • 5

    Answer: 5. 5 is at the back. Unlike a queue, a deque can drop either end, and this call named the back.

How it runs, step by step

  1. An empty deque. Items can join or leave at either end, the front or the back, in O(1).

    Empty deque with capacity 6. Running 8 operations: push-back 5, push-back 3, push-front 9, pop-back, peek-front, push-front 7, pop-front, pop-back.

  2. push-back 5: it joins at the back, and being the only item it is both ends. Size 1.

    push-back 5 at the back. The deque has 1 item.

  3. push-back 3: it joins at the back. Size 2.

    push-back 3 at the back. The deque has 2 items.

  4. push-front 9: it joins at the front. Size 3.

    push-front 9 at the front. The deque has 3 items.

  5. pop-back returns 3, the item at the back. The other end is untouched. Size 2.

    pop-back removes 3 from the back. 2 items remain.

  6. peek-front shows the front, 9, without removing it.

    peek-front shows 9 at the front. Nothing changes.

  7. push-front 7: it joins at the front. Size 3.

    push-front 7 at the front. The deque has 3 items.

  8. pop-front returns 7, the item at the front. The other end is untouched. Size 2.

    pop-front removes 7 from the front. 2 items remain.

  9. pop-back returns 5, the item at the back. The other end is untouched. Size 1.

    pop-back removes 5 from the back. 1 item remain.

  10. Done: 4 pushs, 3 pops. 1 item left, 9 at the front and 9 at the back. Every operation touched one end only, so each was O(1).

    Result: 4 pushes and 3 pops. The deque holds 1 item, with 9 at the front and 9 at the back.

Remember

  • Both ends are first class: a deque is a stack and a queue at the same time.
  • Every operation is O(1) because it only touches one end and never shifts the middle.
  • Sliding window maximum and work stealing both rely on popping from one end while pushing at the other.

Topics covered

Related

Where this is used

DatabasesRedis lists

A Redis list is a deque: LPUSH and RPUSH add at either end, LPOP and RPOP remove from either end, and all four are constant time no matter how long the list is. That is what lets one key act as a FIFO job queue, which is how Sidekiq and Celery hand work to their workers, and as a LIFO stack with no change of structure. Internally, once a list grows past a few small entries, it is a quicklist, a linked list of compact blocks, so both ends stay cheap without paying one allocation per element.

ConcurrencyWork-stealing schedulers

Java's ForkJoinPool, Rust's Rayon and the original Cilk runtime each give a worker thread its own deque of tasks. The owner pushes and pops at one end, so it runs the task it just created while that data is still in cache, and an idle thread steals from the other end, taking the oldest task, which is usually the largest and the least likely to be needed soon. Because owner and thief work at opposite ends, they only contend when the deque is nearly empty, so the ordinary case needs no lock at all.

Standard librariescollections.deque and ArrayDeque

Python's collections.deque and Java's ArrayDeque exist because a plain list or array makes one end cheap and the other O(n): removing the first element shifts every remaining one down. Java's documentation says ArrayDeque is likely to be faster than Stack used as a stack and faster than LinkedList used as a queue, which makes it the default for both. Python's version takes a maxlen, which turns it into a fixed-size rolling window: every push past the cap drops the item at the far end, so keeping the last 500 log lines or samples needs no trimming pass.

Operating systemsPage reclaim in the Linux kernel

The kernel holds file and anonymous pages on LRU lists that are worked from both ends: a page the kernel judges to be in use is moved to the head of the active list, while the reclaim scanner takes eviction candidates from the tail of the inactive one. The doubly linked list_head nodes make list_add, list_add_tail and removal from the middle all O(1), so promoting a page on a hit never walks the list. Every LRU cache has this shape, because the recently-used end and the eviction end both have to be cheap at the same time.

Why it works this way

Why (head - 1 + capacity) % capacity and not (head - 1) % capacity

In Kotlin, Java, C and most C-like languages the remainder keeps the sign of the left operand, so when head is 0 the shorter form gives -1 and the very next line indexes out of bounds. Adding capacity first makes the numerator non-negative before the wrap, and that extra term changes nothing when head is already above 0. Python is the exception: its % always returns a non-negative result for a positive divisor, so anyone who learned rings there never meets this bug.

Full and empty look identical unless you count

If you track only a head and a tail index, an empty ring and a completely full one both satisfy head == tail, and no comparison of those two values can separate them. Keeping an explicit size, as the code here does, settles it in one field and lets the deque use every slot. The other standard fix is to leave one slot permanently unused, so full means (tail + 1) % capacity == head: a slot traded for the counter.

popBack leaves the value sitting in the array

Decrementing size hides the slot from every later operation, but the array still holds the reference, so on the JVM that object stays alive until something overwrites the slot. With the small boxed integers stored here it hardly matters; with large objects it is a slow leak in a long-lived deque. Real implementations, java.util.ArrayDeque among them, write null into the slot they just vacated.

Why a ring and not a doubly linked list?

Both give O(1) at both ends, so the choice is about memory rather than asymptotics. The ring is one contiguous allocation with no per-element pointers, which the cache likes, but its capacity is fixed, which is why the code has to check before pushing, and growing means copying everything into a bigger array. A linked list grows without copying and pays an allocation plus a pointer chase per element instead; CPython splits the difference by linking blocks of 64 items. Rings also get a small bonus: if capacity is a power of two, the % collapses into a single & (capacity - 1).

Read more

Next up