Stack, Queue, and Deque

Stack, queue, and deque are the same family with different rules about which end you may touch. That restriction is the entire reason they are useful: when an algorithm needs only one end, the container serves it in $O(1)$ and makes the wrong operations impossible—which is why these structures keep appearing in bracket matching, BFS, sliding-window maxima, and 0-1 BFS.

Difficulty: Beginner | Prerequisites: Arrays and Strings | CF Rating Range: 800–2100

Intuition

The core trade is simple: give up arbitrary access, gain guaranteed constant-time access to the one element you actually need. All three containers enforce this trade—stack, queue, and deque just differ in which end they expose. Once you accept the restriction, the structure handles the ordering for free.

Consider the classic demonstration. You have an array [3, 1, 4, 1, 5, 9] and a window size $k=3$. For every contiguous window of $k$ elements, report the maximum.

First instinct: slide the window one position at a time, scan all $k$ elements.

Array: [3, 1, 4, 1, 5, 9]    k = 3

Window [3, 1, 4] -> scan 3 elements -> max = 4
Window [1, 4, 1] -> scan 3 elements -> max = 4
Window [4, 1, 5] -> scan 3 elements -> max = 5
Window [1, 5, 9] -> scan 3 elements -> max = 9

Total comparisons: 4 windows x 3 scans = 12

With $n=6$ and $k=3$ the waste is mild. But picture $n={10}^6$ and $k={10}^5$: roughly $9\times {10}^5$ windows, each scanning ${10}^5$ elements—about $9\times {10}^{10}$ comparisons. Way beyond any time limit.

The waste is obvious: consecutive windows overlap by $k-1$ elements, yet we throw away everything we learned and rescan from scratch. When the window slides from [3, 1, 4] to [1, 4, 1], we already knew 4 was the biggest—and 4 is still in the new window. Why scan it again?

The Monotonic Deque Idea

Keep only the elements that can still affect the answer—stored in decreasing order inside a deque—and the front is always the maximum. Each element enters and leaves at most once, turning the whole pass into $O(n)$ work.

Think of a hallway with a bouncer at the back door. A new person arrives and the bouncer kicks out everyone shorter—they can never be the tallest while the newcomer is still around. Meanwhile, the person at the front ages out when the window slides past them. The tallest is always at the front of the line.

The same principle—restricting access points to preserve a useful ordering—appears in simpler forms too:

• Stack (LIFO): The last bracket you opened is the first one you need to close. Pushing openers onto a stack means the correct match is always on top—no searching required.
• Queue (FIFO): In BFS, the first node discovered at distance $d$ must be processed before any node at distance $d+1$. A queue enforces that ordering automatically.
• Deque: Combines both ends. The monotonic deque variant described above is its most powerful competitive programming application.

Visual Walkthrough

Trace the same array, a = [3, 1, 4, 1, 5, 9], with window size $k=3$.

The deque stores indices, not values. Notation: dq = [i:v, ...] means index i holding value v, front on the left.

Step 0: i=0, a[0]=3
  action: deque empty, push index 0
  dq = [0:3]
  window incomplete (need 3 elements)

Step 1: i=1, a[1]=1
  action: 1 < 3 (back of deque), just push index 1
  dq = [0:3, 1:1]
  window incomplete

Step 2: i=2, a[2]=4
  action: 4 > 1 -> pop back (index 1)
          4 > 3 -> pop back (index 0)
          deque empty, push index 2
  dq = [2:4]
  window [0..2]
  *** answer = a[dq.front()] = a[2] = 4 ***

Step 3: i=3, a[3]=1
  action: 1 < 4 (back), push index 3
          front index 2 still in window
  dq = [2:4, 3:1]
  window [1..3]
  *** answer = a[2] = 4 ***

Step 4: i=4, a[4]=5
  action: 5 > 1 -> pop back (index 3)
          5 > 4 -> pop back (index 2)
          deque empty, push index 4
  dq = [4:5]
  window [2..4]
  *** answer = a[4] = 5 ***

Step 5: i=5, a[5]=9
  action: 9 > 5 -> pop back (index 4)
          deque empty, push index 5
  dq = [5:9]
  window [3..5]
  *** answer = a[5] = 9 ***

Tally: 6 pushes + 5 pops = 11 deque operations for the full array. Every element was pushed exactly once and popped at most once—the amortized $O(n)$ guarantee.

Brute force used 12 comparisons on this tiny array, roughly the same. But with $n={10}^6$ and $k={10}^5$, the deque still does at most $2n=2\times {10}^6$ operations while brute force does $\sim 9\times {10}^{10}$—a $\mathrm{45,000}\times$ speedup.

The Invariant

+------------------------------------------------------------------+
| INVARIANT: The deque contains indices in increasing order from    |
| front to back, and their corresponding array values are in        |
| strictly DECREASING order. Every index in the deque lies within   |
| the current window [i - k + 1 .. i]. Therefore a[dq.front()]      |
| is always the maximum of the current window.                      |
+------------------------------------------------------------------+

Why it holds:

• Decreasing values: Before pushing index $i$, we pop every back element whose value $\le a[i]$. No element remaining in the deque is smaller than the newest entry. In Step 2 above, indices 0 and 1 both got popped because their values (3 and 1) were $\le 4$.

• Window bounds: Before reading the answer, we pop any front element whose index is $<i-k+1$ (it has left the window). In this example, no front-pops were needed because the aggressive back-pops already cleared stale indices—but with a decreasing array, front-pops fire every step.

• Front = max: Combining the two properties, the front element holds the largest value among all indices currently in the window.

The simpler structures have equally clean invariants:

STACK INVARIANT (bracket matching): The top is always the most recent
unmatched opening bracket.

QUEUE INVARIANT (BFS): All nodes at distance d appear before all nodes
at distance d + 1, so the front always has the smallest distance among
unprocessed nodes.

LIFO vs FIFO—Correctness, Not Just Speed

What the Code Won't Teach You

Deque is the base; stack and queue are restrictions. std::stack and std::queue are literally thin wrappers around std::deque. A deque supports push/pop at both ends plus random access; a stack narrows that to one end, and a queue narrows it to opposite ends. The hierarchy matters because the restriction is the feature, not the limitation. Once you understand the deque, stack and queue stop being separate ideas.

Stack's true power: forgetting what is no longer relevant. A stack does more than reverse order—it keeps the most recent unresolved items and drops the ones already decided. In a monotonic stack, when a larger element arrives, every smaller element on top is immediately answered and popped. The stack discards them because they are provably irrelevant, and that selective memory is what keeps the algorithm clean and $O(n)$.

LIFO vs FIFO determines correctness, not just speed. Using a stack for BFS or a queue for DFS does not merely slow things down—it gives wrong answers. Processing order controls which nodes are explored first, and that directly controls the result:

Graph:     1 --- 2 --- 4
           |           |
           3 --- 5 --- 6

        STACK (DFS)                      QUEUE (BFS)
  Visit order: 1,3,5,6,2,4         Visit order: 1,2,3,4,5,6
  Goes DEEP first                   Goes WIDE first

  Step-by-step:                    Step-by-step:
  push(1)                          enqueue(1)
  pop->1, push 2,3                 dequeue->1, enqueue 2,3
  pop->3, push 5                   dequeue->2, enqueue 4
  pop->5, push 6                   dequeue->3, enqueue 5
  pop->6                           dequeue->4, enqueue 6
  pop->2, push 4                   dequeue->5
  pop->4                           dequeue->6

  Same graph, same neighbours,      Shortest-path distances from 1:
  completely different order.        node:  1  2  3  4  5  6
                                     dist:  0  1  1  2  2  3
                                     (only BFS guarantees this)

The same seven operations on a stack versus a queue produce completely different output:

Operations: push(A), push(B), push(C), pop, pop, push(D), pop

STACK (LIFO):                     QUEUE (FIFO):
push(A): [A]                      push(A): [A]
push(B): [A,B]                    push(B): [A,B]
push(C): [A,B,C]                  push(C): [A,B,C]
pop -> C: [A,B]                   pop -> A: [B,C]
pop -> B: [A]                     pop -> B: [C]
push(D): [A,D]                    push(D): [C,D]
pop -> D: [A]                     pop -> C: [D]

Stack pops: C, B, D               Queue pops: A, B, C
(reverse insertion order)         (insertion order)

After the same sequence of operations, the stack contains [A] and the queue contains [D]—completely different states. This is why swapping one for the other changes correctness, not just performance.

The unifying principle: the algorithm's required ordering dictates the data structure. Dijkstra uses a priority queue (nearest cost first), BFS uses a queue (shallowest first), DFS uses a stack (deepest first), 0-1 BFS uses a deque (weight-0 edges to front, weight-1 to back). Each structure enforces the invariant its algorithm depends on.

Two Stacks Make a Queue

Push onto an "inbox" stack. When you need to dequeue, dump the inbox into an "outbox" stack—this reversal restores FIFO order—then pop from the outbox. Each element moves at most twice, so amortized cost is $O(1)$ per operation.

enqueue(1), enqueue(2), enqueue(3):

  inbox:  |3|        outbox: | |
          |2|                | |
          |1|                | |
          ---                ---

dequeue() -- outbox empty, so dump inbox -> outbox (three pops+pushes):

  inbox:  | |        outbox: |1|
          | |                |2|
          | |                |3|
          ---                ---

  pop outbox -> returns 1  (FIFO order!)

enqueue(4), enqueue(5):

  inbox:  |5|        outbox: |2|
          |4|                |3|
          | |                | |
          ---                ---

dequeue() -- outbox NOT empty, just pop:

  pop outbox -> returns 2  (correct)

  Each element: pushed to inbox once, moved to outbox once,
  popped from outbox once.  3 operations total per element.
  Amortized cost per enqueue/dequeue: O(1).

Each element is pushed to inbox once, moved to outbox once, and popped from outbox once—three touches total, amortized $O(1)$.

Recognition Triggers

Stack:

• "matching brackets / parentheses" → stack
• "next greater element" or "next smaller element" → monotonic stack
• "undo the last operation" or "backtrack" → stack
• "largest rectangle in histogram" → monotonic stack

Queue:

• "shortest path in unweighted graph" → BFS queue
• "process in order of arrival" or "FIFO simulation" → queue
• "level-order traversal" → queue

Deque:

• "sliding window minimum / maximum" → monotonic deque
• "0-1 BFS" (edge weights are 0 and 1 only) → deque
• "optimise DP transitions over a sliding range" → monotonic deque

std::deque<T> (#include <deque>): push_front, push_back, pop_front, pop_back, front, back, operator[]—all $O(1)$. Insert/erase in the middle is $O(n)$.

Common misidentifications:

• "Find the $k$-th largest element overall"—looks like a stack or deque trick, but you need a heap (priority queue) or quickselect. The access pattern is not LIFO or FIFO; you need the global $k$-th element, not a local extreme. See: Priority Queue and Heaps.
• "Sliding window median"—unlike min/max, the median cannot be maintained with a single monotonic structure. You need two heaps (a max-heap for the lower half and a min-heap for the upper half) or a policy-based tree.
• "Range minimum query with arbitrary (non-sliding) ranges"—a monotonic deque only works when the window slides in one direction. For arbitrary query ranges, use a Sparse Table or Segment Tree.
• "Need random access into the middle"—stack and queue hide internal elements. Use a vector or deque with indexing.
• "Need elements in sorted order"—none of these structures maintain sorted order. Use a set/multiset or priority queue.

C++ STL Reference

std::stack<T>—#include <stack>

Method	What it does	Time
push(x)	Push element onto top	$O(1)$ amortized
emplace(args...)	Construct element in-place on top	$O(1)$ amortized
pop()	Remove top element (returns void)	$O(1)$
top()	Reference to top element	$O(1)$
size()	Number of elements	$O(1)$
empty()	Whether stack is empty	$O(1)$
swap(other)	Swap contents with another stack	$O(1)$

std::queue<T>—#include <queue>

Method	What it does	Time
push(x)	Enqueue element at back	$O(1)$ amortized
emplace(args...)	Construct element in-place at back	$O(1)$ amortized
pop()	Remove front element (returns void)	$O(1)$
front()	Reference to front element	$O(1)$
back()	Reference to back element	$O(1)$
size()	Number of elements	$O(1)$
empty()	Whether queue is empty	$O(1)$
swap(other)	Swap contents with another queue	$O(1)$

std::deque<T>—#include <deque>

Method	What it does	Time
push_back(x)	Insert at back	$O(1)$ amortized
push_front(x)	Insert at front	$O(1)$ amortized
emplace_back(args...)	Construct in-place at back	$O(1)$ amortized
emplace_front(args...)	Construct in-place at front	$O(1)$ amortized
pop_back()	Remove last element	$O(1)$
pop_front()	Remove first element	$O(1)$
front()	Reference to first element	$O(1)$
back()	Reference to last element	$O(1)$
operator[](i)	Random access by index	$O(1)$
at(i)	Bounds-checked random access	$O(1)$
size()	Number of elements	$O(1)$
empty()	Whether deque is empty	$O(1)$
clear()	Remove all elements	$O(n)$
insert(pos, x)	Insert at iterator position	$O(n)$
erase(pos)	Erase at iterator position	$O(n)$
begin() / end()	Iterators	$O(1)$
swap(other)	Swap contents	$O(1)$

Note: std::stack and std::queue are container adaptors. By default they wrap std::deque, but you can specify a different underlying container—e.g., std::stack<int, std::vector<int>>.

---

Implementation (Contest-Ready)

Bracket Matching—Minimal

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) { ok = false; break; }
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) { ok = false; break; }
        }
    }
    cout << (ok && st.empty() ? "YES" : "NO") << "\n";
}

Bracket Matching—Explained

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;

    for (char c : s) {
        // Opening brackets get pushed; we'll match them later.
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            // Closing bracket with nothing to match -> invalid.
            if (st.empty()) { ok = false; break; }

            char t = st.top(); st.pop();
            // Each closer must pair with its specific opener.
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) {
                ok = false;
                break;
            }
        }
    }

    // Valid only if every opener was matched (stack is empty).
    cout << (ok && st.empty() ? "YES" : "NO") << "\n";
}

BFS Shortest Path—Minimal

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // dist[v] = -1 means unvisited; doubles as visited array.
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front(); q.pop();  // FIFO: discovery order.
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << dist[i] << " \n"[i == n];
}

BFS Shortest Path—Explained

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // dist[v] = -1 means unvisited; doubles as a visited array.
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front(); q.pop();  // FIFO: process in discovery order.
        for (int v : adj[u]) {
            if (dist[v] == -1) {     // Only visit each node once.
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << dist[i] << " \n"[i == n];
}

Sliding Window Maximum—Minimal

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    deque<int> dq; // stores indices
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " \n"[i == n - 1];
    }
}

Sliding Window Maximum—Explained

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    // dq stores *indices* (not values) in decreasing order of a[index].
    // Front of dq is always the index of the current window maximum.
    deque<int> dq;

    for (int i = 0; i < n; i++) {
        // Remove indices that fell out of window [i-k+1, i].
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // Maintain decreasing order: a[i] dominates any smaller
        // element still at the back, and will outlive them.
        while (!dq.empty() && a[dq.back()] <= a[i])
            dq.pop_back();

        dq.push_back(i);

        // First full window starts at i = k-1.
        if (i >= k - 1)
            cout << a[dq.front()] << " \n"[i == n - 1];
    }
}

---

Operations Reference

Stack

Operation	Time	Space
push	$O(1)$ amortized	$O(1)$
pop	$O(1)$	$O(1)$
top	$O(1)$	$O(1)$
Build from $n$ elements	$O(n)$	$O(n)$

Queue

Operation	Time	Space
push	$O(1)$ amortized	$O(1)$
pop	$O(1)$	$O(1)$
front / back	$O(1)$	$O(1)$
Build from $n$ elements	$O(n)$	$O(n)$

Deque

Operation	Time	Space
push_front / push_back	$O(1)$ amortized	$O(1)$
pop_front / pop_back	$O(1)$	$O(1)$
front / back	$O(1)$	$O(1)$
operator[]	$O(1)$	$O(1)$
insert / erase (middle)	$O(n)$	$O(1)$
Build from $n$ elements	$O(n)$	$O(n)$

---

Problem Patterns & Tricks

Bracket / Parenthesis Matching

Push openers, pop on closers, and verify the match. Handles nested structures of arbitrary depth. Extends to computing scores (e.g., (()(())) scoring problems) by keeping a running value on the stack.

Problems: CF 1097B -- Petr and a Combination Lock (light warm-up), CF 52C -- Circular RMQ

Next Greater / Smaller Element (Monotonic Stack)

Maintain a stack of indices with values in decreasing (or increasing) order. When a new element violates the order, pop and record the answer for popped elements. Each element is pushed and popped at most once, so the total work is $O(n)$.

// nge[i] = smallest j > i with a[j] > a[i], or -1 if none.
vector<int> nge(n, -1);
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] < a[i]) {
        nge[st.top()] = i;
        st.pop();
    }
    st.push(i);
}

Problems: CF 1313C2 -- Skyscrapers (hard), CF 1795D -- Triangle Coloring

BFS on Unweighted Graphs

Standard BFS uses a queue to explore vertices layer by layer, giving shortest distances in unweighted graphs. Also used for multi-source BFS (push all sources initially) and grid BFS (4/8-directional).

Problems: CF 1037D -- Valid BFS?, CF 1063B -- Labyrinth

0-1 BFS (Deque)

When edge weights are only 0 or 1, replace Dijkstra with a deque: push weight-0 neighbors to the front, weight-1 neighbors to the back. Runs in $O(V+E)$ instead of $O((V+E)\log V)$.

vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[src] = 0;
dq.push_front(src);
while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (w == 0) dq.push_front(v);
            else        dq.push_back(v);
        }
    }
}

Problems: CF 1063B -- Labyrinth, CF 877D -- Olya and Energy Drinks

Sliding Window Min/Max (Monotonic Deque)

Keep a deque of indices with values in decreasing order (for max) or increasing order (for min). Pop from the front when the index exits the window. Answers all window queries in $O(n)$ total—essential for DP optimizations.

Problems: CF 1195E -- OpenStreetMap, CF 372C -- Watching Fireworks is Fun

See Also: For in-depth monotonic stack treatment (next-greater-element variants, contribution counting, histogram tricks), see Monotonic Stack. For sliding window deque optimization and DP applications, see Monotonic Queue.

Largest Rectangle in Histogram

For each bar, find the nearest shorter bar on each side using a monotonic stack. Area for bar $i$ = $h_i\times (righ{t}_i-lef{t}_i-1)$. Classic $O(n)$ stack problem that appears as a subproblem in maximal rectangle in a binary matrix.

Problems: CF 1156E -- Special Segments of Permutation

Simulation / Greedy with a Stack

Many greedy problems require building an answer character by character, occasionally removing earlier choices. A stack lets you undo the last choice efficiently—e.g., lexicographically smallest subsequence, removing $k$ digits to minimize a number.

Problems: CF 1092D1 -- Great Vova Wall (Version 1), CF 1579D -- Productive Meeting

Multi-Source BFS

Push all source nodes into the queue at distance 0 before the BFS loop. Computes the shortest distance from any source to every other node—used in "distance to nearest special cell on a grid" and similar problems.

Problems: CF 1293D -- Aroma's Search, CF 1805D -- A Wide, Wide Wagon

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  STACK / QUEUE / DEQUE  --  Quick Reference                      |
+------------------------------------------------------------------+
|  WHEN TO USE:                                                    |
|    Stack  -> matching, undo, DFS, next-greater/smaller element   |
|    Queue  -> BFS, level-order, FIFO simulation                   |
|    Deque  -> sliding window min/max, 0-1 BFS, need both ends    |
|                                                                  |
|  KEY STL:                                                        |
|    stack<int> s; s.push(x); s.top(); s.pop();                    |
|    queue<int> q; q.push(x); q.front(); q.pop();                 |
|    deque<int> d; d.push_back(x); d.push_front(x);               |
|                    d.pop_back();   d.pop_front();                |
|                    d.front();      d.back();  d[i];              |
|                                                                  |
|  MONOTONIC STACK (next greater element):                         |
|    while (!s.empty() && a[s.top()] < a[i]) {                    |
|        nge[s.top()] = i; s.pop(); }                              |
|    s.push(i);                                                    |
|                                                                  |
|  MONOTONIC DEQUE (sliding window max, size k):                   |
|    while (!d.empty() && d.front() <= i-k) d.pop_front();        |
|    while (!d.empty() && a[d.back()] <= a[i]) d.pop_back();      |
|    d.push_back(i);  // answer = a[d.front()]                     |
|                                                                  |
|  COMPLEXITY:  push/pop/front/back = O(1)                         |
|               deque random access   = O(1)                       |
|  SPACE:       O(n)                                               |
+------------------------------------------------------------------+

---

Common Mistakes & Debugging

Empty container access

Calling .top(), .front(), or .back() on an empty container is undefined behavior. Always guard with .empty():

if (!st.empty()) {
    int x = st.top();
    st.pop();
}

Under contest stress, this is the #1 source of runtime errors with these structures.

pop() returns void

A classic C++ trap: st.pop() does not return the removed element. Always read first, then pop:

int x = st.top();  // read
st.pop();           // remove

Stack vs. Vector-as-stack

std::stack hides operator[], iterators, and clear(). If you need any of those, reach for std::vector with push_back() / pop_back() / back()—identical LIFO semantics with full flexibility. Many competitive programmers never use std::stack at all.

Queue vs. Deque

std::queue is a thin wrapper over std::deque that hides push_front, pop_back, and random access. If you might need those later in a problem, start with std::deque directly to avoid refactoring mid-contest.

Deque memory overhead

std::deque allocates memory in chunks and carries higher constant factors than std::vector. Up to $\sim {10}^7$ elements this is irrelevant, but keep it in mind when MLE is tight. A pair of vectors (one for each end) or a circular buffer can be lighter.

Monotonic Stack/Deque—Strict vs Non-Strict

For "next strictly greater," use < when popping. For "next greater or equal," use <=. Getting this wrong shifts answers by one or introduces duplicates—double-check the problem statement.

Forgetting to store indices

Monotonic stacks and deques almost always store indices, not raw values. Storing values loses positional information and makes it impossible to check whether an element has left the window.

// BUG: storing values instead of indices
deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.back() <= a[i]) dq.pop_back();
    dq.push_back(a[i]);  // Can't check if front has expired!
}
// FIX: store indices: dq.push_back(i) and compare with a[dq.back()]

Off-by-one in window expiry

The window [i - k + 1, i] means the front index expires when it equals i - k, not i - k + 1:

// BUG
if (dq.front() < i - k) dq.pop_front();
// FIX: use <= i-k (equivalently, < i-k+1)
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();

Using a queue for DFS (or a stack for BFS)

Swapping LIFO/FIFO does not merely change performance—it gives wrong answers:

// BUG: queue gives BFS order, not DFS
queue<int> q;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();  // FIFO = BFS, not DFS!
    for (int v : adj[u]) q.push(v);
}
// FIX: use stack (or recursion) for DFS

Mental Traps

Trap: "Deque is just a doubly-linked list." In most implementations (including std::deque), a deque is not a linked list. It is a chunked array—an array of pointers to fixed-size blocks—which gives $O(1)$ random access (compute block index, then offset within block). A linked list cannot provide that.

Actual std::deque layout (chunked array):

  map array (pointers to blocks):
     [ptr0]  [ptr1]  [ptr2]  [ptr3]
       |       |       |       |
       v       v       v       v
     [a,b,c] [d,e,f] [g,h,i] [j,k, ]
      blk 0   blk 1   blk 2   blk 3

  Access d[7]:
    block_size = 3
    block  = 7 / 3 = 2    ->  map[2] = ptr2
    offset = 7 % 3 = 1    ->  ptr2[1] = 'h'
    Result: O(1) random access!

  vs. what people imagine (doubly-linked list):

  [a] <-> [b] <-> [c] <-> [d] <-> [e] <-> ... <-> [k]

  Access node 7: walk 7 pointers from head -> O(n)

In practice: d[i] is $O(1)$, iteration is cache-friendly within a chunk (though less so than vector), and push_front/push_back only allocate a new block when the current end-block is full. The constant factor is noticeably heavier than vector, so for purely back-push workloads most competitive programmers reach for vector<int> as their stack.

Trap: "Stack problems are easy." The implementation is almost always short—10 to 20 lines. But recognizing that a problem is a stack problem is the hard part. "Largest rectangle in histogram" doesn't mention stacks. "Trapping rain water" doesn't mention stacks. The difficulty is in the reduction, not the data structure. When you're stuck, ask: "Is there an element that makes earlier elements irrelevant?" If yes, it's probably a stack problem.

Pattern Summary

• Bracket / parenthesis matching. Push openers, pop on closers, and verify the match. Extends to scoring problems (e.g. (()(()))) by carrying a running value on the stack.
• Next greater / smaller element. Monotonic stack. Each element is pushed and popped at most once—$O(n)$ total.
• BFS on unweighted graphs. Queue. Also powers multi-source BFS (push all sources at distance 0) and grid BFS.
• 0-1 BFS. Deque: weight-0 neighbors to the front, weight-1 to the back.
• Sliding window min/max. Monotonic deque. Essential for DP optimizations. See Monotonic Queue.
• Largest rectangle in histogram. Monotonic stack to find the nearest shorter bar on each side, then area for bar $i$ is $h_i\times (righ{t}_i-lef{t}_i-1)$. Appears as a subproblem in maximal rectangle in a binary matrix.
• Simulation / greedy with undo. Many greedy problems build an answer character by character, sometimes removing previous choices. A stack supports efficient undo—e.g., lexicographically smallest subsequence, "remove $k$ digits to minimize a number."

For an in-depth treatment of monotonic stack tricks (contribution counting, histogram patterns) see Monotonic Stack. For sliding-window DP optimization see Monotonic Queue.

---

When Not to Use These

• Sliding window median. A monotonic deque handles only min/max. For the median you need two heaps (max-heap for the lower half, min-heap for the upper half) or a policy-based tree.
• $k$-th largest overall. The access pattern is not LIFO or FIFO—you need a priority queue or quickselect.
• Range min on arbitrary (non-sliding) ranges. A monotonic deque only works when the window slides in one direction. For arbitrary query ranges, use a Sparse Table or Segment Tree.

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Balanced Bracket Sequence	CF 1556C	Easy (1200)	Stack bracket matching with greedy pairing
2	Valid BFS?	CF 1037D	Easy (1600)	Simulate BFS with a queue, verify order
3	Stock Spanner	LeetCode 901	Easy--Med	Monotonic stack, span counting
4	Skyscrapers (hard)	CF 1313C2	Medium (1900)	Next smaller element with monotonic stack, prefix sums
5	Watching Fireworks is Fun	CF 372C	Medium (1900)	Sliding window max via monotonic deque + DP
6	OpenStreetMap	CF 1195E	Medium (2000)	2D sliding window min using nested monotonic deques
7	Labyrinth	CF 1063B	Medium (2000)	0-1 BFS on grid with left/right move costs
8	Olya and Energy Drinks	CF 877D	Medium--Hard (2000)	BFS with bounded jumps optimised by deque
9	Special Segments of Permutation	CF 1156E	Hard (2100)	Monotonic stack to find nearest smaller on both sides
10	Imbalanced Array	CF 817D	Hard (2100)	Contribution technique with two monotonic stacks
11	Nearest Smaller Values	CSES	1300	Classic monotonic stack: find nearest smaller to the left
12	Towers	CSES	1400	Greedy with multiset or stack simulation

Further Reading

• cp-algorithms—Stack and Queue Modification—min-stack / min-queue technique; maintaining auxiliary min/max alongside standard operations.
• Codeforces: Monotonic Stack/Queue tutorial
• Monotonic Stack—in-depth next-greater-element patterns, contribution counting, histogram tricks.
• Monotonic Queue—advanced sliding-window DP optimizations.
• BFS—full BFS coverage including multi-source and 0-1 BFS.
• DFS and Tree DFS—DFS uses an implicit stack; explicit stacks appear in iterative DFS.
• Sliding Window—deques power $O(1)$ sliding-window min/max queries.
• Data Structure Selection Guide—choosing the right container under contest pressure.

---

Next Up: Linked List Basics—another fundamental structure where insertion order matters, but with $O(1)$ insert/delete at known positions.