Stacks and queues are the same idea — “a sequence you only touch at the ends” — with one rule flipped. That single rule flip is the difference between undo history and a print queue.

What you’ll learn

• Stack (LIFO) built from a plain listlist: appendappend/poppop.
• Queue (FIFO) built from collections.dequecollections.deque: appendappend/popleftpopleft.
• Why list.pop(0)list.pop(0) is $O(n)$ and deque.popleft()deque.popleft() is $O(1)$.
• The monotonic stack pattern — Next Greater Element, runnable.
• Using dequedeque as both a stack and a queue.
• LeetCode-style problems to drill the pattern.

Stack: last in, first out

A stack only cares about one end. Python’s listlist is already perfect for this — appendappend and poppop (no argument) both operate on the end, both $O(1)$ amortized.

stack = []
 
stack.append(1)
stack.append(2)
stack.append(3)
print("after pushes:", stack)
 
top = stack.pop()
print("popped:", top)
print("stack now:", stack)
 
print("peek (no pop):", stack[-1])
print("is empty?", len(stack) == 0)

stack = []
 
stack.append(1)
stack.append(2)
stack.append(3)
print("after pushes:", stack)
 
top = stack.pop()
print("popped:", top)
print("stack now:", stack)
 
print("peek (no pop):", stack[-1])
print("is empty?", len(stack) == 0)

Undo/redo, “match the brackets”, and depth-first traversal (both recursion and its explicit-stack equivalent) all lean on exactly this shape.

Queue: first in, first out

A queue needs cheap operations at both ends: push at the back, pop from the front. A plain listlist is the wrong tool here — pop(0)pop(0) has to shift every remaining element down by one, which is $O(n)$.

# DON'T use a list as a queue if you pop from the front repeatedly.
queue_as_list = [1, 2, 3, 4, 5]
 
# Each pop(0) shifts every remaining element left by one slot -> O(n)
front = queue_as_list.pop(0)
print("popped from front:", front)
print("remaining:", queue_as_list, "  <- everything shifted, that cost O(n)")

# DON'T use a list as a queue if you pop from the front repeatedly.
queue_as_list = [1, 2, 3, 4, 5]
 
# Each pop(0) shifts every remaining element left by one slot -> O(n)
front = queue_as_list.pop(0)
print("popped from front:", front)
print("remaining:", queue_as_list, "  <- everything shifted, that cost O(n)")

collections.dequecollections.deque is implemented as a doubly linked sequence of fixed-size blocks, so both ends are cheap — no shifting, ever.

from collections import deque
 
queue = deque()
queue.append(1)   # enqueue: add at the back, O(1)
queue.append(2)
queue.append(3)
print("queue:", queue)
 
front = queue.popleft()   # dequeue: remove from the front, O(1)
print("dequeued:", front)
print("queue now:", queue)

from collections import deque
 
queue = deque()
queue.append(1)   # enqueue: add at the back, O(1)
queue.append(2)
queue.append(3)
print("queue:", queue)
 
front = queue.popleft()   # dequeue: remove from the front, O(1)
print("dequeued:", front)
print("queue now:", queue)

Monotonic stack: Next Greater Element

A monotonic stack keeps its elements in strictly increasing (or decreasing) order by popping anything that violates the order before pushing the new element. It’s the standard trick for “find the next bigger/smaller thing to the right” problems, and it does the whole array in one $O(n)$ pass — each element is pushed and popped at most once.

def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []   # holds INDICES, kept so nums[stack] is decreasing
 
    for i, x in enumerate(nums):
        # pop every index whose value is smaller than the current one --
        # x IS their next greater element
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            result[j] = x
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))
# 2 -> 4, 1 -> 2, 2 -> 4, 4 -> -1 (none), 3 -> -1 (none)

def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []   # holds INDICES, kept so nums[stack] is decreasing
 
    for i, x in enumerate(nums):
        # pop every index whose value is smaller than the current one --
        # x IS their next greater element
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            result[j] = x
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))
# 2 -> 4, 1 -> 2, 2 -> 4, 4 -> -1 (none), 3 -> -1 (none)

Watch the stack grow and shrink as it scans the array — every pop happens because the current bar is taller than the one on top of the stack:

dequedeque as both a stack and a queue

collections.dequecollections.deque is $O(1)$ at both ends, so it works perfectly as either a stack or a queue — one structure, two disciplines.

from collections import deque
 
# used as a STACK: push/pop the same end
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("stack pop:", stack.pop())        # LIFO: 3
 
# used as a QUEUE: push at the back, pop from the front
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("queue popleft:", queue.popleft())   # FIFO: 1

from collections import deque
 
# used as a STACK: push/pop the same end
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("stack pop:", stack.pop())        # LIFO: 3
 
# used as a QUEUE: push at the back, pop from the front
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("queue popleft:", queue.popleft())   # FIFO: 1

Complexity summary

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 20 — Valid Parentheses · Easy

Problem. Given a string of ()[]{}()[]{}, decide whether the brackets are correctly closed in the correct order and matched by type.

Constraints. 1 <= len(s) <= 10^41 <= len(s) <= 10^4.

Examples. "()""()" gives TrueTrue · "()[]{}""()[]{}" gives TrueTrue · "(]""(]" gives FalseFalse · "([)]""([)]" gives FalseFalse

LC 1047 — Remove All Adjacent Duplicates In String · Easy

Problem. Repeatedly remove two adjacent equal letters until no such pair remains. Return the final string; the answer is unique.

Constraints. 1 <= len(s) <= 10^51 <= len(s) <= 10^5, lowercase letters.

Examples. "abbaca""abbaca" gives "ca""ca" · "azxxzy""azxxzy" gives "ay""ay"

LC 682 — Baseball Game · Easy

Problem. Given a list of operations, compute the total score. Each entry is an integer (record it), "+""+" (record the sum of the previous two), "D""D" (record double the previous), or "C""C" (invalidate the previous record and remove it).

Constraints. 1 <= len(operations) <= 10001 <= len(operations) <= 1000, and every operation is valid when it appears.

Examples. ["5","2","C","D","+"]["5","2","C","D","+"] gives 3030 · ["5","-2","4","C","D","9","+","+"]["5","-2","4","C","D","9","+","+"] gives 2727

Recap

• Stack = LIFO, built from a plain listlist (appendappend/poppop), both $O(1)$ amortized.
• Queue = FIFO. Never use list.pop(0)list.pop(0) ($O(n)$) — use collections.dequecollections.deque (appendappend/popleftpopleft, both $O(1)$).
• A monotonic stack answers “next greater/smaller” queries for an entire array in one $O(n)$ pass.
• dequedeque is flexible enough to serve as either a stack or a queue.

Next: Hash Tables — how dictdict and setset get $O(1)$ average lookup, and the collision handling underneath.