Stack/QueueData structureaka double-ended queue, head-tail linked list

Deque

A queue that supports O(1) insertion and removal at both the front and the back.

▶ Visualize Pattern: Sliding Window Practice (1)

Progress

Definition

A deque (pronounced "deck") generalizes both the Stack and the Queue: you can pushFront, pushBack, popFront, and popBack, all in O(1). Restricting to one end gives a stack; restricting to push-back/pop-front gives a queue.

Production deques (collections.deque, std::deque, ArrayDeque) are typically growable Circular Queue buffers or blocks of arrays linked together. A Doubly Linked List also works but with worse constants.

Deques are the backbone of Monotonic Queue (sliding window maximum), 0-1 BFS, and work-stealing schedulers.

double-endedO(1)ring buffersliding window0-1 BFS

Intuition

A mental model before the formal terms.

A train platform where carriages can be coupled or uncoupled at either end. The middle carriages are untouchable without first removing the ends.

A ring buffer where the "start" can move backwards as well as forwards: pushing to the front just decrements head (mod capacity) and writes there.

How it works

Keep a ring buffer buf, a head index, and a size. back = (head + size - 1) % cap.
pushBack(x): grow if full, then buf[(head + size) % cap] = x, size++.
pushFront(x): grow if full, then head = (head - 1 + cap) % cap, buf[head] = x, size++.
popFront(): read buf[head], head = (head + 1) % cap, size--.
popBack(): read buf[(head + size - 1) % cap], size--.
Growing: allocate a buffer twice as large and copy elements in logical order starting from head, then reset head = 0.

Why it works

Because both ends are just indices into a circular buffer, moving either one is a single modular increment or decrement — no shifting.

Doubling on growth makes the copy cost amortize to O(1) per push, exactly as for a Dynamic Array.

Operations

Operation	Description	Cost
pushFront(x)	Insert at the front.	O(1) amortized
pushBack(x)	Insert at the back.	O(1) amortized
popFront()	Remove and return the front element.	O(1)
popBack()	Remove and return the back element.	O(1)
front() / back()	Peek either end.	O(1)
get(i)	Random access by logical index (ring-buffer implementation).	O(1)

Recognition

How to tell a problem wants this.

You need both stack and queue behaviour in the same structure.
A sliding-window problem asks for the max/min of each window — see Monotonic Queue.
Edge weights are only 0 or 1: 0-1 BFS pushes 0-weight neighbours to the front, 1-weight to the back.
Palindrome checks by comparing and removing from both ends.

“contiguous subarray” → Sliding Window “minimum steps” → Breadth-First Search

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — Comma separated: pushfront N, pushback N, popfront, popback

1/13A deque supports O(1) insertion and removal at both ends, so it can act as a stack, a queue, or both at once.

Just pushedBeing poppedFrontBack

PseudocodeLearn Deque →

1push_front(x): items.insert(0, x)
2push_back(x): items.append(x)
3pop_front(): return items.pop_front()
4pop_back(): return items.pop()

Variables

size0

Complexity

access O(1)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class Deque:
2  buf = array(cap); head = 0; size = 0
3  pushBack(x): grow if full; buf[(head + size) % cap] = x; size++
4  pushFront(x): grow if full; head = (head - 1 + cap) % cap; buf[head] = x; size++
5  popFront(): v = buf[head]; head = (head + 1) % cap; size--; return v
6  popBack(): v = buf[(head + size - 1) % cap]; size--; return v

Implementation

1from typing import Generic, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class Deque(Generic[T]):
71 · Growable ring buffer state
8    def __init__(self, capacity: int = 8) -> None:
9        self._buf: list[Optional[T]] = [None] * capacity
10        self._head = 0  # index of the front
11        self._n = 0     # number of stored elements
12 
132 · Grow by un-wrapping into a fresh buffer
14    def _grow(self) -> None:
15        old, cap = self._buf, len(self._buf)
16        self._buf = [None] * (cap * 2)
17        for i in range(self._n):
18            self._buf[i] = old[(self._head + i) % cap]
19        self._head = 0
20 
213 · Push at either end
22    def push_back(self, x: T) -> None:
23        if self._n == len(self._buf):
24            self._grow()
25        self._buf[(self._head + self._n) % len(self._buf)] = x
26        self._n += 1
27 
28    def push_front(self, x: T) -> None:
29        if self._n == len(self._buf):
30            self._grow()
31        self._head = (self._head - 1) % len(self._buf)  # Python % wraps negatives
32        self._buf[self._head] = x
33        self._n += 1
34 
354 · Pop at either end
36    def pop_front(self) -> T:
37        if self._n == 0:
38            raise IndexError("pop from empty deque")
39        x = self._buf[self._head]
40        self._buf[self._head] = None
41        self._head = (self._head + 1) % len(self._buf)
42        self._n -= 1
43        return x  # type: ignore[return-value]
44 
45    def pop_back(self) -> T:
46        if self._n == 0:
47            raise IndexError("pop from empty deque")
48        i = (self._head + self._n - 1) % len(self._buf)
49        x = self._buf[i]
50        self._buf[i] = None
51        self._n -= 1
52        return x  # type: ignore[return-value]
53 
545 · Peek and size
55    def front(self) -> Optional[T]:
56        return self._buf[self._head] if self._n else None
57 
58    def back(self) -> Optional[T]:
59        return self._buf[(self._head + self._n - 1) % len(self._buf)] if self._n else None
60 
61    def __len__(self) -> int:
62        return self._n

Walkthrough

The ring stores Optional[T] slots; _head and _n define the live window.
_grow un-wraps into a doubled list and resets _head to 0.
push_front can use a bare (head - 1) % len(buf) because Python's % returns non-negative results.
Pops clear the slot to None and use type: ignore[return-value] where the occupancy invariant outruns the type checker.
__len__ supports len(d) and truthiness (while d:).

Complexity (this implementation)

time O(1) amortized push, O(1) pop/peek · space O(n)

collections.deque is the same idea in C (a doubly linked list of 64-slot blocks) — O(1) ends, O(n) middle, and no Python-level resize pauses.

Language notes

collections.deque is the answer in real code: append, appendleft, pop, popleft, plus rotate and maxlen.
Indexing deque[i] is O(n) in the middle — it is a block list, not an array; use list when random access dominates.
This hand-rolled ring is for understanding; interviews expect you to *name* deque and use it.

Common mistakes in this language

Building a deque on list with insert(0, x)/pop(0) — both O(n).
Assuming deque[k] is O(1) like a list index — it is O(k) from the nearer end.
Returning the Optional[T] slot type from pops instead of asserting occupancy, spreading None checks everywhere.

Language differences that matter here

Standard library: C++ std::deque and Python collections.deque are ready-made (block-based, not single rings); JS/TS must hand-roll — unshift/shift are O(n).
Negative modulo: Python alone allows (head - 1) % cap directly; C++ (unsigned size_t) and JS (sign-preserving %) must add the capacity first.
Random access: the ring gives O(1) get(i) in all languages; std::deque keeps O(1) indexing but Python deque[i] is O(n) in the middle.
Growth: this ring pauses to un-wrap on resize in every language; the block-based stdlib deques never move existing elements.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	By index in ring-buffer form; O(n) for linked form.
Search	O(n)	O(n)
Insert	O(1)	O(n)	At either end; O(n) only on resize (amortized O(1)). Middle insert is O(n).
Delete	O(1)	O(1)	At either end.
Update	O(1)	O(1)	By index in ring-buffer form.
Push front / back	O(1)	O(n)	Amortized O(1).
Pop front / back	O(1)	O(1)
Peek front / back	O(1)	O(1)
Space	O(n)

Advantages & disadvantages

Advantages

Constant-time operations at both ends; strictly more flexible than a stack or queue.
Ring-buffer implementations give O(1) random access and good cache locality.
Available in every major standard library (collections.deque, ArrayDeque, std::deque).

Disadvantages

Insertion or deletion in the middle is O(n).
Slightly more complex than a plain queue; growth requires an un-wrapping copy.
JavaScript has no built-in deque — unshift is O(n), so you must implement one.

Use cases

Sliding window maximum/minimum via a Monotonic Queue.
0-1 BFS on graphs with edge weights in {0, 1}.
Work-stealing thread pools (owner pops from one end, thieves steal from the other).
Undo/redo histories with bounded size (drop from the far end when full).

Use it when

You need constant-time operations at both ends (sliding windows, 0-1 BFS, bounded histories).
You want a fast general-purpose queue or stack in Python (collections.deque beats list for queues).
Implementing a Monotonic Queue.

Avoid it when

You need frequent insertion/deletion in the middle — use a Doubly Linked List with node handles, or a balanced tree.
You need ordering by priority rather than position — use a Priority Queue.
A plain Stack or Queue suffices and simplicity matters more.

Alternatives

Queue Stack Circular Queue Doubly Linked List

Common mistakes

Using Array.unshift()/shift() in JavaScript as a deque — both are O(n).
Forgetting + cap before % cap when decrementing head, yielding a negative index.
Copying the raw buffer on growth instead of un-wrapping from head.
In sliding-window problems, storing values instead of indices in the deque, making it impossible to know when the front has left the window.

Interview patterns

Sliding window maximum: monotonic deque of indices, pop back while smaller, pop front when out of window.
0-1 BFS: pushFront for weight-0 edges, pushBack for weight-1 edges.
Shortest subarray with sum ≥ K: monotonic deque over prefix sums.
Check palindrome by popping from both ends and comparing.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner

Mock interviews

Minimum Size Subarray SumIntermediate
Longest Substring Without Repeating CharactersIntermediate
Course ScheduleIntermediate

Interview problems

Sliding Window Maximumhard

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related