Stacks and Queues

1Stack: last in, first out

A stack is a LIFO structure: push and pop both act at one end, the top. Each of those operations is O(1). Stacks model nested work — recursion call frames, undo history, and the unmatched openers in an expression — because the most recently opened obligation is the one that must close first.

Figure. Stack after push 1, then 2, then 3. Only the top cell is reachable for the next pop.

How push and pop work

1. PushPlace a new element on the top. The previous top becomes the second element.
2. PopRemove and return the current top. The element under it is exposed.
3. PeekRead the top without removing it — still constant time.

2Queue: first in, first out

A queue is FIFO: enqueue at the back, dequeue at the front, each O(1) with a proper implementation. Queues order work by arrival — BFS level expansion, print jobs, request handlers — because the oldest waiting item is the next one served.

Figure. Queue after enqueue 1, then 2, then 3. Dequeue pulls from the left; enqueue appends on the right.

How enqueue and dequeue work

1. EnqueueAttach the new element at the back. It waits behind everything already in line.
2. DequeueRemove the front element — the one that has waited longest.
3. Empty checkFront and back meet (or the structure reports empty) when nothing remains to serve.

3Valid parentheses with a stack

Checking that brackets are balanced and correctly nested is the textbook stack problem. Scan left to right: push every opener; on a closer, pop and demand an exact match. Fail if the stack is empty on a closer, if a pop mismatches, or if anything remains when the string ends. Time and worst-case stack space are both O(n).

Figure. Scan left to right: push openers, pop on a matching closer; empty stack at end means valid nesting.

One left-to-right pass

1. OpenerPush '(', '[', or '{' onto the stack.
2. CloserPop; the opener must be the matching mate. Empty stack or wrong mate ⇒ invalid.
3. End of stringValid only if the stack is empty — every opener found its closer.

Valid parentheses

def is_valid(s):
    mate = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif not stack or stack.pop() != mate[ch]:
            return False
    return not stack

Coding lab. Check ([]) nested brackets runs in the app, with checks on your output.

4Monotonic stack: next greater element

A monotonic stack stays strictly decreasing (or increasing) by value. For next-greater-element, store indices of values still waiting for a larger neighbour to their right. Scan left to right; while the current value beats the value at the stack top, pop and record the answer. Each index is pushed and popped at most once, so the whole pass is O(n) instead of a nested O(n^2) scan.

Figure. Array from the worked example. Annotations above each cell are that cell's next greater to the right.

Decreasing stack of indices

1. Hold waitersStack stores indices whose next greater is still unknown, in decreasing value order.
2. ResolveWhen nums[i] is greater than nums[stack.top], pop and set answer[popped] = nums[i].
3. Push ii itself may still need a greater element further right.
4. LeftoversIndices still on the stack at the end have no greater element — answer -1.

Next greater element

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            ans[stack.pop()] = value
        stack.append(i)
    return ans

5Queue from two stacks

When the only primitive is a stack, a queue is two stacks: in for enqueue, out for dequeue. Enqueue always pushes onto in. Dequeue pops from out; if out is empty, pour every element from in into out first (reversing order), then pop. Each element moves at most twice, so enqueue and dequeue are amortized O(1).

Figure. Enqueue on the in-stack; when the out-stack is empty, flush in→out so dequeue reads FIFO order.

Amortized handoff

1. EnqueuePush onto in.
2. Dequeue, out readyIf out is non-empty, pop out — that is the front.
3. Dequeue, out emptyWhile in is non-empty, pop in and push onto out. Then pop out.

6Deque and sliding-window maximum

A deque supports insert and remove at both ends in O(1). For sliding-window maximum, keep a deque of indices whose values are decreasing: the front is always the max in the current window. Drop indices that left the window from the front; drop smaller candidates from the back before pushing the new index. One pass is O(n) time and O(k) deque space — better than a heap's O(n \log k).

Figure. First window of length 3 over [1, 3, −1, −3, 5]; its maximum is 3 at the second cell.

Monotonic deque

1. Expire the frontWhile the front index is outside [i−k+1, i], pop left.
2. Dominated backsWhile the back's value ≤ nums[i], pop right — it can never be max while i is in the window.
3. Push and readPush i. Once the window is full, nums[front] is the answer for this i.

7Stacks for expression parsing

Beyond matching brackets, stacks evaluate and convert expressions. Postfix (RPN) evaluation pushes numbers and, on an operator, pops operands, applies the operator, and pushes the result. Infix-to-postfix conversion uses an operator stack with precedence rules. Prefix walks right-to-left with the same idea. The shared habit: delayed operators wait on a stack until their operands are ready.

Figure. Postfix mid-state: numbers wait on the stack until an operator arrives. Seeing × pops 4 and 5, pushes 20.

Postfix evaluation

1. NumberPush it on the value stack.
2. OperatorPop right operand, pop left operand, apply, push the result.
3. DoneOne value remains on the stack — the expression's value.

8When to reach for which

Pick the structure from the access pattern the problem needs. Nesting, undo, matching openers, next-greater, and expression operators want a stack. Arrival order, BFS, and fair scheduling want a queue. Both-ends work and sliding-window extrema want a deque. Implementing one from the other (queue from two stacks, stack from two queues) is an interview constraint trick, not a default design.

Figure. Stack for LIFO nesting and undo; queue for BFS layers; monotonic stack for next-greater patterns.

Decision cues

1. Nesting or "most recent"Stack — parentheses, path undo, monotonic waiters.
2. Oldest first or level orderQueue — BFS, task queues, printers.
3. Both ends or window extremaDeque — sliding-window maximum, steque-style APIs.