Stacks and Queues

Both a stack and a queue support the same two basic operations — add an item, remove an item — with $O(1)$ cost each. The only difference is which item comes back out. A stack is last-in-first-out (LIFO): the most recently added item is the first one removed, like a stack of plates where you only ever take from the top. A queue is first-in-first-out (FIFO): the item that's been waiting longest comes out first, like a line at a checkout counter. That one-word difference in retrieval order changes which real problems each structure solves cleanly.

The idea: same interface, opposite order

A stack supports push (add to the top) and pop (remove from the top) — both $O(1)$ because nothing else in the structure has to move. Python's list.append()/list.pop() already behaves like a stack.

A queue supports enqueue (add to the back) and dequeue (remove from the front). A plain Python list is a bad queue — list.pop(0) is $O(n)$ because every remaining element has to shift left. collections.deque gives $O(1)$ operations at both ends, which is what a real queue implementation needs.

Worked example 1: matching parentheses with a stack

Checking whether "(a(b)c)d)" has balanced parentheses: push every ( onto a stack; on every ), pop — if the stack is empty, there's an unmatched close.

• ( → push. Stack: [(]
• a → skip.
• ( → push. Stack: [(, (]
• b → skip.
• ) → pop. Stack: [(]
• c → skip.
• ) → pop. Stack: []
• d → skip.
• ) → stack is empty, pop fails → unbalanced, reject.

The stack naturally tracks "what still needs closing, most recent first" — exactly the LIFO structure of nested parentheses.

Worked example 2: order processing with a queue

An exchange gateway receives client order messages and must process them in the order received, regardless of processing speed. A queue enforces that: enqueue(order_1), enqueue(order_2), enqueue(order_3) — then dequeue() always returns order_1 first, order_2 second, order_3 third, no matter how fast or slow each one finishes. A stack would do the opposite — process order_3 first — which is exactly wrong for anything that needs first-come-first-served fairness, like price-time priority matching.

from collections import deque

stack = []                    # LIFO
stack.append(1); stack.append(2)
stack.pop()                   # -> 2

queue = deque()                # FIFO
queue.append(1); queue.append(2)
queue.popleft()                # -> 1

Where it shows up

Interviewers use stacks for balanced-parentheses variants, expression evaluation (shunting-yard), and "next greater element" (a monotonic stack); queues show up in breadth-first search and any "process level by level" problem. In trading systems, a FIFO queue is the literal mechanism behind price-time priority in a matching engine — orders at the same price execute in arrival order — while a stack-like undo history or a call stack tracks nested state, like recursive strategy logic or a parser walking a nested order specification.