Stacks, queues, and deques

Three ways to say who goes next. Same box of data - but the rule you use to add and remove decides everything from browser undo to how a search explores.

An array lets you touch any slot by index. A stack, queue, and deque give that up on purpose - they restrict where you may add and remove, and in exchange every operation is a cheap $O(1)$. The restriction is the feature: it turns out "always take from the top" and "always take from the front" are exactly the disciplines that undo, scheduling, and graph traversal need.

Two disciplines: LIFO and FIFO

Each structure exposes a tiny, fixed vocabulary. A stack has push (add on top), pop (remove the top), and peek (look at the top without removing). A queue has enqueue (add at the rear), dequeue (remove from the front), and front (peek at who's next). A deque simply offers both ends. None of them let you reach into the middle - that's the whole point.

Under the hood you can build any of them two ways. A linked list gives $O(1)$ ends for free - splice a node on or off. An array is faster and cache-friendly for a stack (grow and shrink the tail), but a naïve array queue is a trap: removing the front by shifting everything left is $O(n)$. The fix - a circular buffer - is below.

See the disciplines move

Push and pop the stack and watch values enter and leave the same top end. Enqueue and dequeue the queue and watch values enter at the rear but leave from the opposite front end. Then try the balanced-parentheses checker: type brackets and step through as a stack pushes each opener and pops it when its partner closer arrives - the classic proof that a stack is the right tool for matching.

In code

A stack is just a list you only touch at the tail. The bracket checker from the demo is eight lines. And in practice you rarely hand-roll a queue - a deque gives $O(1)$ at both ends, so it is a stack, a queue, or a deque depending on which methods you call.

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':                       # opener -> push it
            stack.append(ch)
        elif ch in ')]}':                     # closer -> must match the top
            if not stack or stack.pop() != pairs[ch]:
                return False                    # nothing to match, or wrong pair
    return not stack                          # balanced iff nothing left unclosed

from collections import deque            # O(1) at BOTH ends
q = deque()
q.append(x)          # enqueue at rear
q.popleft()          # dequeue from front   -> FIFO (a queue)
q.append(x); q.pop() # push then pop at rear -> LIFO (a stack)

Check yourself