Stacks and Queues

1. What It Is and Why It Exists

A stack is a LIFO (last-in, first-out) collection: you can only add (push) and remove (pop) at one end, the top. A queue is FIFO (first-in, first-out): you add at the back (enqueue) and remove from the front (dequeue). Both restrict where you can touch the data, and that restriction is exactly the point — it makes the structure model a specific control flow in O(1) per operation. A stack mirrors nested/recursive structure (matching brackets, function call frames, "undo", depth-first search or DFS). A queue mirrors order-preserving processing (breadth-first search or BFS, scheduling, buffering). DFS follows a branch before returning to others; BFS visits nodes in successive distance layers.

The "why it works" intuition: a stack is the call stack — anything naturally recursive can be made iterative with an explicit stack, which is how you avoid recursion-depth limits in an interview. A queue guarantees you process items in arrival order, which is precisely why BFS finds shortest paths in an unweighted graph: nodes come off the queue in non-decreasing distance order. Without these structures you'd reimplement the same ordering bookkeeping by hand every time.

2. Operations and Complexity

Space is O(n). The important distinction is cost: a Python list can implement a queue, but removing from its front is slow. list.pop(0) is O(n), so draining n items this way costs O(n^2). The expected answer is collections.deque for queues (and stacks too). Interviewers also probe whether you can implement a queue with two stacks (amortized O(1)).

3. Implementation

The stack wrapper below exposes last-in, first-out operations. The queue uses two stacks: moving all items from _in to _out reverses their order, putting the oldest item on top. Each item moves only once, so a sequence of queue operations costs amortized O(1) per operation even though one transfer can cost O(n).

class Stack:                              # LIFO; one end only
    def __init__(self):
        self._data = []
    def push(self, x):  self._data.append(x)        # O(1) amortized
    def pop(self):      return self._data.pop()     # O(1)
    def peek(self):     return self._data[-1]       # O(1)
    def empty(self):    return not self._data

class Queue:                              # FIFO via two stacks: amortized O(1)
    def __init__(self):
        self._in = []                     # push here
        self._out = []                    # pop from here
    def enqueue(self, x):
        self._in.append(x)                # O(1)
    def dequeue(self):
        if not self._out:                 # move only when out is empty:
            while self._in:               # each element moves at most once
                self._out.append(self._in.pop())  # -> amortized O(1)
        return self._out.pop()

In a real interview:

• Stack → use a Python list (append / pop / a[-1]).
• Queue → use collections.deque (append / popleft), never list.pop(0).
• Need both ends or a sliding-window queue → collections.deque (it is the canonical monotonic-queue backbone).

from collections import deque
stack = []                 # push: stack.append(x); pop: stack.pop()
queue = deque()            # enqueue: queue.append(x); dequeue: queue.popleft()

4. When to Reach for It

• Stack: matching/nesting (parentheses, valid-expression), "most recent unmatched", undo/backtracking, converting recursion (DFS, tree traversal) to iteration, and the entire monotonic-stack pattern (next greater element).
• Queue: BFS / level-order traversal, shortest path in an unweighted graph, scheduling and rate-limiting, and the monotonic-deque sliding-window-maximum pattern.
• Deque: any time you need O(1) operations at both ends, or a fixed-size sliding window.

5. Common Pitfalls

• Using list.pop(0) as a queue dequeue: O(n) each → O(n^2) total. Always collections.deque.popleft().
• Popping/peeking an empty stack or queue: raises IndexError. Guard with an emptiness check before every pop/peek.
• LIFO vs FIFO mix-up: using a stack where order must be preserved (or a queue for nesting) gives subtly wrong output that passes tiny tests and fails larger ones.
• deque random indexing: dq[i] for a middle index is O(n) — deque is fast only at the ends; use a list if you need indexing.
• Two-stack queue: transferring every call. Only refill out when it is empty; transferring while out still holds items puts newer items above older ones and breaks FIFO order.

6. Interview Cheat Sheet

• "Stack is LIFO, queue is FIFO. A deque has O(1) end operations; the list stack and two-stack queue here have amortized O(1) operations."
• "In Python a list is my stack; a deque is my queue — list.pop(0) is O(n), so I never use a list as a queue."
• "A stack converts any recursion to iteration and avoids recursion-depth limits; a queue gives BFS its shortest-path-in-unweighted-graph property."
• "I can build a queue from two stacks at amortized O(1) by only refilling the output stack when it's empty."

Follow-ups:

• "Implement a queue using stacks." — Two stacks; push to in, pop from out, refill out from in only when out is empty → amortized O(1).
• "Implement a stack using queues." — One queue, on push rotate the queue so the new element is at the front → O(n) push, O(1) pop (or the reverse).
• "Min-stack / get-min in O(1)?" — Keep a second stack of running minimums (or store (value, min_so_far) pairs); every operation stays O(1).