Deques — Complete DSA Deque Theory

Learning Progress. Work top to bottom: theory → operations → the interactive visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a Deque?

A Deque (double-ended queue, pronounced "deck") allows insertion and deletion at both ends — front and rear — in O(1). It generalizes both the stack and the queue.

Backed by a doubly linked list or a circular dynamic array (like C++ std::deque), giving O(1) at the ends and O(1) indexed access in the STL version.

Core operations

pushFront(x) / pushBack(x)
popFront() / popBack()
front() / back()
// all O(1)

Why Deques? A deque is a stack and a queue at once. It powers the sliding-window-maximum pattern, undo/redo with bounded history, palindrome checks, and work-stealing schedulers.

Deque as stack & queue

📚

As a Stack

Use only pushBack/popBack (or only the front) → pure LIFO.

Use: when you may later need the other end too.

🎟️

As a Queue

Push at back, pop at front → pure FIFO.

Use: BFS, buffering.

📈

Monotonic Deque

Maintain increasing/decreasing order by popping from the back before pushing.

Use: sliding window max/min in O(n).

Terminology

Front / Head

The left end. pushFront/popFront/front operate here.

Back / Rear / Tail

The right end. pushBack/popBack/back operate here.

Double-ended

Both ends support O(1) insert and remove.

Monotonic

A deque kept sorted so the extreme element is always at one end.

Circular buffer

Array-backed deque wrapping both indices with modulo.

Random access

std::deque supports O(1) d[i], unlike list-backed deques.

Complexity Summary

Push front/back

O(1)

Insert at either end.

Pop front/back

O(1)

Remove at either end.

Peek front/back

O(1)

Read either end.

Index access

O(1)†

std::deque only; list-backed is O(n).

O(n)

Linear scan.

Space

O(n)

n elements.

Advantages & Disadvantages

Advantages

O(1) insert/remove at both ends.
Serves as both a stack and a queue.
std::deque adds O(1) random access.
Backbone of the sliding-window-maximum pattern.

Disadvantages

More overhead than a plain queue/stack.
std::deque memory is chunked, not fully contiguous.
Middle insertion/deletion is still O(n).
Iterator invalidation rules are subtle.

C++ STL Implementation

deque_stl.cpp · std::deque

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> dq = {20, 30};
    dq.push_front(10);   // [10,20,30]
    dq.push_back(40);    // [10,20,30,40]
    dq.pop_front();      // [20,30,40]
    dq.pop_back();       // [20,30]
    cout << dq.front() << " " << dq.back() << " " << dq[0];
    return 0;  // 20 30 20 — all O(1)
}

sliding_window_max.cpp · Monotonic deque

// Sliding Window Maximum — O(n)
vector<int> maxSlidingWindow(vector<int>& a, int k) {
    deque<int> dq;   // stores indices, values decreasing
    vector<int> res;
    for (int i = 0; i < a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // stale
        while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();  // smaller
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]); // front = max
    }
    return res;
}

Interactive Deque Visualization

Element Front Back Added Removed

Idle

Current operation details

Operation

—

Front

—

Back

—

Steps

taken

Adds

inserts

Removes

deletes

Size

elements

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — build your own operation

Deque (front→back): Value:

✓ Done

Speed

Step-by-step operation log

Step	Front	Back	Action	Deque State
Run a scenario to populate the log.

Key Patterns

Sliding window maximum. Keep indices in a deque with values in decreasing order. Pop the back while it's smaller than the incoming value, pop the front when it slides out of the window. The front is always the window max — O(n) total.

Palindrome check. Compare front() and back(), pop both inward. If they ever differ, it's not a palindrome. O(n)/O(1).

Cheat Sheet

Operation	Time	Space	Notes
Push front/back	O(1)	O(1)	Either end
Pop front/back	O(1)	O(1)	Either end
Peek front/back	O(1)	O(1)	Read ends
Index access (STL)	O(1)	O(1)	std::deque d[i]
Sliding window max	O(n)	O(k)	Monotonic deque
Palindrome check	O(n)	O(1)	Compare both ends inward

Learning Roadmap

Deque Basics

pushFront/Back, popFront/Back, using a deque as a stack and as a queue.

~2 hours

std::deque API

Random access, iterators, chunked memory model, when to prefer over vector/list.

~2 hours

Monotonic Deque

Sliding window maximum/minimum, first negative in window, constrained subarray sums.

~4 hours

Advanced

0-1 BFS with a deque, work-stealing schedulers, bounded undo/redo history.

~3 hours

Interview Preparation

Sliding Window Maximum

Monotonic decreasing deque of indices; front is the max. Pop stale front, pop smaller back. O(n).

Monotonic

Design Circular Deque

Fixed array with head/tail indices wrapping via modulo. O(1) both ends.

Ring Buffer

First Negative in Every Window

Deque of indices of negative numbers; front is the first negative still in window.

Deque

0-1 BFS

Push zero-weight edges to the front, one-weight to the back. Shortest path on 0/1 graphs in O(V+E).

Graph

Practice Problems

MediumDesign Circular DequeRing Buffer

MediumFirst Negative in WindowDeque

MediumNumber of Sub-arrays with Bounded MaxWindow

HardSliding Window MaximumMonotonic

HardShortest Subarray with Sum ≥ KMonotonic

HardConstrained Subsequence SumDP + Deque

Key Takeaways

↔️Both ends, O(1): a deque is stack + queue combined — push/pop/peek at front and back all constant time.

📈Monotonic deque: the signature use — sliding window max/min in O(n) by keeping values ordered.

🎯std::deque: the STL version adds O(1) random access via chunked storage, unlike list-backed deques.

🧭0-1 BFS: push front for 0-weight, back for 1-weight edges — Dijkstra-quality paths without a heap.