Stack, queue, and deque

LIFO, FIFO, and double-ended queues — from bracket problems to sliding windows and BFS grids.

stack — last in, first out

std::stack (default: deque under the hood) supports push, pop, top, empty, size.

Classic CP uses:

Valid parentheses / bracket sequences.
Monotonic stack for “nearest greater to the left” (histogram, temperature-style problems).
DFS recursion simulation (explicit stack).

Note: pop() returns void — save top() first if you need the value.

Example — balanced parentheses:

bool ok(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

Example — monotonic stack: previous greater index:

vector<int> a = {3, 1, 4, 2};
vector<int> prevGreater(a.size(), -1);
stack<int> st;  // store indices, values decreasing
for (int i = 0; i < (int)a.size(); i++) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    if (!st.empty()) prevGreater[i] = st.top();
    st.push(i);
}

queue — breadth-first order

std::queue is FIFO: push at back, pop from front, front to read.

Standard pattern: BFS on graphs or grids — push start node, while queue non-empty, pop, relax neighbors, push unvisited.

0-1 BFS: use deque: push edge weight 0 to front, weight 1 to back.

Dijkstra is not a plain queue — you need priority_queue (or specialized queues).

Example — BFS on unweighted graph (g adjacency list):

vector<int> dist(n, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

Example — multi-source BFS (push all sources with dist 0):

queue<int> q;
for (int s : sources) {
    dist[s] = 0;
    q.push(s);
}
// same while loop as above

deque — both ends in O(1)

std::deque allows push_front, push_back, pop_front, pop_back, and indexed access (amortized O(1) at ends; index access O(1) but slightly heavier than vector).

Sliding window minimum/maximum: maintain monotone deque of indices — each element pushed once, popped once → O(n) total.

Tradeoff: For pure “stack only” or “queue only”, vector + index or queue/stack is clearer; deque shines when you need both ends.

Example — 0-1 BFS:

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

Example — sliding window minimum (indices in deque, values increasing):

vector<int> a = {5, 3, 6, 1, 2};
int k = 3;
deque<int> dq;  // indices, a[dq.front()] is min in window
for (int i = 0; i < (int)a.size(); 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()] << " ";
}

BFS sketch

Initialize visited, push source. While queue not empty: pop u; for each neighbor v: if not visited, mark, push v. Distance layers follow naturally with optional parallel size tracking per level.

1STACK S
2PUSH x
3while S not empty
4  y = TOP(S)
5  POP(S)
6
7QUEUE Q
8PUSH source
9while Q not empty
10  u = FRONT(Q); POP(Q)
11  for v in neighbors(u)
12    if not visited[v] then PUSH v

Complexity

stack/queue: each operation amortized O(1) with standard underlying containers.

deque: O(1) at ends; avoid treating it as “always like vector” in micro-optimizations — still excellent for contests.

Complexity Analysis

Time Complexity

O(1) amortized typical stack/queue/deque operations at ends

Space Complexity

O(n) for n stored elements

Monotone deque sliding window is O(n) total, not O(n) per window

Growth Rate Comparison