Deque (Double-Ended Queue) in DSA Explained

A deque (pronounced “deck”, short for double-ended queue) is a linear structure that lets you add and remove elements from both ends — front and rear — each in O(1). It generalizes both the stack (LIFO, one end) and the queue (FIFO, two ends with fixed roles), making it the single most versatile of the three.

What a deque can do

A deque exposes four endpoint operations plus peeks — all O(1):

• pushFront(x) / pushBack(x) — add at the front or rear.
• popFront() / popBack() — remove from the front or rear.
• peekFront() / peekBack() — inspect either end.

Because of this, a deque is a stack (use one end) and is a queue (push back, pop front) at the same time.

#include <deque>
std::deque<int> dq;
dq.push_back(1);    // [1]
dq.push_front(0);   // [0, 1]
dq.push_back(2);    // [0, 1, 2]
int f = dq.front(); // 0
int b = dq.back();  // 2
dq.pop_front();     // [1, 2]
dq.pop_back();      // [1]

import java.util.*;
Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(1);          // [1]
dq.addFirst(0);         // [0, 1]
dq.addLast(2);          // [0, 1, 2]
int f = dq.peekFirst(); // 0
int b = dq.peekLast();  // 2
dq.pollFirst();         // [1, 2]
dq.pollLast();          // [1]

// JS arrays support both ends, but unshift/shift are O(n).
// Fine for small data; use a linked deque or index map for heavy use.
const dq = [];
dq.push(1);            // [1]
dq.unshift(0);         // [0, 1]   (O(n))
dq.push(2);            // [0, 1, 2]
const f = dq[0];       // 0
const b = dq[dq.length - 1]; // 2
dq.shift();            // [1, 2]   (O(n))
dq.pop();              // [1]

from collections import deque
dq = deque()
dq.append(1)        # [1]      push back
dq.appendleft(0)    # [0, 1]   push front
dq.append(2)        # [0, 1, 2]
f = dq[0]           # 0
b = dq[-1]          # 2
dq.popleft()        # [1, 2]   pop front
dq.pop()            # [1]      pop back

Language note: C++ std::deque, Java ArrayDeque, and Python collections.deque give true O(1) at both ends. JavaScript has no built-in deque — Array.unshift/shift are O(n), so for large inputs build one over a doubly linked list or an index-keyed object.

How it works under the hood

Most deques are built from either a doubly linked list (each node points both ways, so either end is O(1)) or a growable circular buffer with head and tail indices (like an extended circular queue). Both give O(1) endpoint operations; the circular-buffer version is more cache-friendly and is what ArrayDeque and std::deque use.

Complexity: O(1) for all four endpoint operations; O(n) for indexing into the middle (linked-list backing) or O(1) random access (buffer backing). Space is O(n).

Where deques shine

• Sliding-window maximum/minimum — a monotonic deque keeps candidate indices in order, giving O(n) over the whole window. Closely related to the monotonic stack.
• Both stack and queue at once — palindrome checking (compare front vs. back), undo with bounded history (drop the oldest from the front).
• Work-stealing schedulers — threads push/pop their own end while others steal from the opposite end.
• 0-1 BFS on graphs — push zero-weight edges to the front, one-weight to the back.

Going deeper: A deque with a capacity limit that drops the opposite end when full is a bounded deque — perfect for “keep the last N items” caches and rolling logs.

When to use a deque

Choose a deque whenever you need flexibility at both ends, or a sliding window. If you only ever touch one end, a plain stack or queue communicates intent better. If you serve by priority rather than position, use a priority queue.

Next: see the deque’s cousin, the monotonic stack, then practice on the exercises.