Stack and Queue Interview Patterns: Valid Parentheses, LRU Cache, and Design Problems (2025)

Stack: LIFO and Its Applications

A stack (Last In, First Out) is the go-to structure when you need to process or undo in reverse order: function call stack, expression evaluation, DFS, matching brackets, and “undo” operations. Key insight: whenever you see “the most recent unmatched X” or “process in reverse,” think stack. Python: use a list (append/pop). Java: Deque as stack (ArrayDeque). Do NOT use java.util.Stack — it is synchronized and slow.

Valid Parentheses (LC 20)

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in mapping:
            top = stack.pop() if stack else '#'
            if mapping[c] != top:
                return False
        else:
            stack.append(c)
    return not stack

Evaluate Reverse Polish Notation (LC 150)

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)  # truncate toward zero
    }
    for t in tokens:
        if t in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

Min Stack (LC 155) — O(1) getMin

class MinStack:
    def __init__(self):
        self.stack = []      # (value, current_min) pairs
    def push(self, val: int) -> None:
        current_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, current_min))
    def pop(self) -> None:
        self.stack.pop()
    def top(self) -> int:
        return self.stack[-1][0]
    def getMin(self) -> int:
        return self.stack[-1][1]

LRU Cache (LC 146) — O(1) get and put

Use a doubly linked list (for O(1) insert and remove) combined with a hashmap (for O(1) lookup). Most-recently-used at the tail; least-recently-used at the head. On get: move to tail. On put: insert at tail; if over capacity, remove head.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()  # maintains insertion order

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # remove LRU (first item)

Queue: BFS and Design

# Implement Queue using Two Stacks (LC 232)
class MyQueue:
    def __init__(self):
        self.inbox = []   # for push
        self.outbox = []  # for pop/peek

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self) -> int:
        self._transfer()
        return self.outbox.pop()

    def peek(self) -> int:
        self._transfer()
        return self.outbox[-1]

    def empty(self) -> bool:
        return not self.inbox and not self.outbox

Amortized O(1) per operation: each element is pushed to inbox once, transferred to outbox once, and popped from outbox once — 3 operations total. The transfer only happens when outbox is empty.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the O(1) trick for Min Stack and why does a separate min stack work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The naive approach tracks the current min by scanning the entire stack on getMin() — O(n). The O(1) trick: store a (value, current_min) pair with every element pushed. The current_min at each level is min(new_value, previous_min). When you pop, the min at the level below is automatically restored because it was stored in that level's pair. A cleaner alternative: maintain a parallel min_stack. On push: if new value <= min_stack top (or min_stack is empty), push to min_stack too. On pop: if popped value == min_stack top, pop from min_stack too. getMin() returns min_stack top. Both approaches are O(1) amortized with O(n) extra space.”}},{“@type”:”Question”,”name”:”How does LRU Cache achieve O(1) for both get and put operations?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LRU requires two operations: (1) Find a key instantly (O(1) lookup). (2) Move it to "most recently used" position and evict the least recently used in O(1). A hashmap alone gives O(1) lookup but O(n) for ordering. A doubly linked list gives O(1) insert/remove but O(n) lookup. Combined: hashmap maps keys to list nodes (O(1) lookup), doubly linked list maintains recency order (O(1) move-to-end and remove-from-front). On get: hashmap lookup finds the node, move it to the tail. On put: hashmap lookup checks if key exists (update or insert at tail), evict head if over capacity. Python's OrderedDict implements this pattern natively with move_to_end() and popitem(last=False).”}},{“@type”:”Question”,”name”:”Why does implementing a queue with two stacks give amortized O(1) per operation?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Each element is pushed to the inbox stack once (O(1)), transferred to the outbox stack once (O(1) amortized across all transfers), and popped from outbox once (O(1)). Total: 3 operations per element regardless of how many enqueue/dequeue operations are interleaved. The transfer (moving all elements from inbox to outbox) happens at most once per element — an element transferred to outbox stays there until popped, never going back to inbox. Worst case for a single dequeue: O(n) if transfer is triggered. But amortized over n operations: O(1) per operation. This is the standard amortized analysis — expensive operations are amortized over the cheap operations that precede them.”}},{“@type”:”Question”,”name”:”What is the difference between a stack and a deque, and when do you use each?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Stack: LIFO — add and remove only from one end (top). Deque (double-ended queue): add and remove from both ends in O(1). A deque is strictly more powerful than a stack. Use a deque when: sliding window maximum (add to right, remove from both ends based on value and window boundary), BFS with priority at both ends, or palindrome checking (read from both ends). Use a pure stack when the LIFO structure captures the problem naturally (bracket matching, DFS, undo). In Python: collections.deque supports appendleft(), popleft(), append(), pop() all in O(1). Java: ArrayDeque is the preferred implementation for both stack and deque use cases (LinkedList has higher memory overhead).”}},{“@type”:”Question”,”name”:”How do you evaluate a mathematical expression with operator precedence using a stack?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Shunting-yard algorithm (Dijkstra): converts infix expression (3 + 4 * 2) to postfix (3 4 2 * +), then evaluate postfix with a stack. Two stacks: output queue and operator stack. For each token: if number: push to output. If operator: pop operators from operator stack to output while they have higher or equal precedence. Push current operator to operator stack. If left paren: push to operator stack. If right paren: pop operators to output until left paren (discard both parens). At end: pop remaining operators to output. Evaluate postfix: for each token: if number, push. If operator, pop two numbers, apply operator, push result. Handles all standard mathematical precedence correctly in O(n).”}}]}