Stacks & Queues

Less is more

A stack and a queue are restricted collections: they deliberately forbid random access and offer just two or three operations. The restriction is the feature — it makes behavior predictable, implementations trivially fast, and intent obvious in code.

Stacks

# Python — a list IS a stack (append/pop at the end are O(1))
stack = []
stack.append(10)     # push
stack.append(20)
top = stack[-1]      # peek → 20
x = stack.pop()      # pop  → 20

// Java — use ArrayDeque, not the legacy Stack class
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
int top = stack.peek();
int x = stack.pop();

// C++
std::stack<int> st;
st.push(10);
int top = st.top();
st.pop();                 // note: pop() returns void in C++

Where stacks already run your life

• The call stack — you met it in Functions: every call pushes a frame, every return pops one. Recursion (Level 3) is a stack, which is why any recursive algorithm can be rewritten with an explicit one.
• Undo / redo — every action pushes onto the undo stack; Ctrl-Z pops it (and pushes onto redo).
• Browser back button — pages visited, most recent first.
• Parsing — matching brackets, evaluating expressions, your compiler.

The interview classic: matched brackets

"Is {[()]} valid?" — opens push, closes must match the top:

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False
    return not stack          # leftovers = unclosed opens

Why a stack? Because the most recently opened bracket must close first — the problem statement contains the letters L-I-F-O if you squint. Training yourself to hear "most recent first" → stack is the actual lesson.

One level up sits the monotonic stack — keep the stack sorted by popping everything your new element beats. It turns "next greater element" and "daily temperatures" style problems from O(n²) scans into one O(n) pass. Meet it properly in the problem bank.

Watch a stack work

Run a push/pop sequence — note who leaves first. Then edit the operations and try to predict the final state before pressing play.

Queues

# Python — NOT a list! Use deque (list.pop(0) shifts everything: O(n))
from collections import deque
q = deque()
q.append(10)         # enqueue at the back
q.append(20)
front = q[0]         # peek → 10
x = q.popleft()      # dequeue from the front → 10, in O(1)

// Java
Queue<Integer> q = new ArrayDeque<>();
q.offer(10);
int x = q.poll();

// C++
std::queue<int> q;
q.push(10);
int x = q.front(); q.pop();

Where queues run the world

• BFS — breadth-first search: explore a graph level by level; the queue holds the frontier. This is the algorithmic reason queues exist, and it's how shortest paths in unweighted graphs are found.
• Task/message queues: printers, web servers under load, and the industrial-strength version — Kafka/SQS pipelines (messaging & queues) — are all "absorb requests at the back, process from the front." The humble deque here and Level 6's distributed queue are the same idea at different scales.
• Rate limiting & buffering: smooth a bursty producer feeding a steady consumer (rate limiting).

The deque — both ends at once

A deque (double-ended queue, "deck") allows O(1) push/pop at both ends — it's the general tool that plays stack and queue. Its star solo is the sliding-window maximum problem, where it powers an O(n) solution (sliding window).

Watch a queue work

Same operations, opposite exit door — the oldest element leaves first.

Build one from the other (interview favorite)

Queue from two stacks: push into inbox; to dequeue, if outbox is empty, pour inbox into it (reversing order), then pop outbox:

class QueueFromStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())   # reverse the order
        return self.outbox.pop()

Each element is moved at most twice ever → amortized O(1) per operation (the arrays page accounting again). The mirror problem — stack from queues — exists too; one of the pair shows up constantly in first rounds.

Production perspective

• Stacks and queues are usually built on arrays or linked lists — they're disciplines, not layouts. Array-backed (with the resize-doubling trick) is the practical default.
• The names persist up the stack: "stack trace," "task queue," "event queue" (the heart of Node.js — Level 7), "undo stack." When you read infrastructure docs, these aren't metaphors — there is literally a queue in there.
• Choosing LIFO vs FIFO is a product decision sometimes: a job scheduler that LIFOs feels snappy for new requests but starves old ones — fairness vs recency, in one letter.

Common mistakes

• list.pop(0) as dequeue in Python — shifts every element, O(n); a loop of them is O(n²). deque.popleft() exists for exactly this.
• Peeking/popping an empty stack — crash (exceptions). The not stack guard in is_valid above is half the solution's correctness.
• Using Java's Stack class — legacy, synchronized, slow; ArrayDeque is the documented replacement.
• Forgetting the leftover check — bracket-matching that returns True with "(((" unprocessed. The final return not stack matters.
• Hearing "queue" and reaching for sorting — FIFO already is the order; if you need priority order instead, that's a heap, two pages from now.

Interview perspective

Practice

1. Beginner: simulate a browser's back button: visit pages, go back, verify order. Then add "forward" — what second structure appeared?
2. The canon: valid parentheses (above, from memory); implement a MinStack that returns the minimum element in O(1) (hint: a second stack riding along); queue-from-two-stacks.
3. Monotonic teaser: for [73,74,75,71,69,72,76,73] (temperatures), compute for each day how many days until a warmer one — first O(n²) the obvious way, then with a stack in O(n). Compare runs on 10⁵ elements.
4. Design: your API server gets bursts of 1,000 requests/sec but can process 200/sec. Walk through what a queue in front buys you, what happens if the burst never stops, and what policy you'd add (connects to rate limiting).

Next: Hash Tables — the O(1) lookup machine that powers half of all interview solutions.

Practice — climb the ladder

If the problem whispers "most recent first" it is a stack; "first come, first served" is a queue; "next greater/smaller" is a monotonic stack.