Core Concepts

Stack: Last In, First Out (LIFO)

Think of a stack of plates — you add and remove from the TOP only.

# Python: use a list as a stack
stack = []
stack.append(1)    # Push — O(1) amortized
stack.append(2)
stack.append(3)
top = stack.pop()  # Pop — O(1) — returns 3
peek = stack[-1]   # Peek — O(1) — returns 2 (without removing)

C# equivalent: Stack<T> with .Push(), .Pop(), .Peek()

TS equivalent: Use an array with .push(), .pop()

Queue: First In, First Out (FIFO)

Think of a line at a restaurant — first to arrive is first to be served.

from collections import deque

# ⚠️ NEVER use list for a queue! list.pop(0) is O(n).
# deque.popleft() is O(1) — this is WHY deque exists.
queue = deque()
queue.append(1)       # Enqueue — O(1)
queue.append(2)
front = queue.popleft()  # Dequeue — O(1) — returns 1

C# equivalent: Queue<T> with .Enqueue(), .Dequeue()

TS equivalent: No efficient built-in — use a library or implement manually

Common mistake: Using list.pop(0) as a queue in Python. This is O(n) because it shifts all remaining elements. Always use collections.deque for queue operations.

When to Use Which

Use a Stack Use a Queue

Matching brackets/parentheses

BFS traversal (graphs, trees)

Undo operations

Scheduling/processing in order

DFS (explicit stack)

Sliding window problems

Expression evaluation

Level-order traversal

Monotonic stack problems

Rate limiting

The Monotonic Stack Pattern

A monotonic stack maintains elements in strictly increasing or decreasing order. Used for "next greater element" and similar problems.

# Example: Find the next greater element for each position
# Input:  [2, 1, 5, 6, 2, 3]
# Output: [5, 5, 6, -1, 3, -1]

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []  # Stores INDICES of elements waiting for their answer

    for i, num in enumerate(nums):
        # While stack is not empty AND current element is greater than
        # the element at the top of the stack → we found the answer!
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

Exercises