Part 1 — Stacks: Last In, First Out

A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle: the last element pushed is the first one popped. Think of a stack of plates — you add to and remove from the top, and the bottom plate is buried. Because the only accessible element is the top, a stack is the natural model for anything that must be undone or unwound in reverse order.

Core Operations

• Push(item) — add to the top — O(1)
• Pop() — remove and return the top — O(1)
• Peek() — return the top without removing it — O(1)
• isEmpty() — check emptiness — O(1)

Every operation touches only the top of the stack, which is why every reasonable implementation offers O(1) at the access point.

Array vs Linked List: The Decision Table

In practice the array-backed stack wins most workloads: contiguous memory keeps the top on a hot cache line. The linked-list stack matters when depth is unbounded or unpredictable and reallocation is unacceptable.

Overflow and Underflow

• Stack overflow — pushing onto a full fixed-size stack. Growable arrays hide this by resizing, but in languages like C it writes past the buffer; in recursion it’s the call stack running out — usually runaway recursion or a missing base case.
• Stack underflow — popping an empty stack. Libraries return a sentinel or throw; a silent wrong value is the classic bug.

These two failure modes are why isEmpty() is checked before every pop(), and why the balanced-parentheses problem ends with “the stack must be empty” as the success condition.

Applications: Where LIFO Shows Up

• Expression evaluation — infix-to-postfix conversion (Shunting-yard) and direct evaluation both use stacks.
• Undo/redo — each action is pushed onto the undo stack; undo pops it and pushes the inverse onto the redo stack.
• Browser back button — visited pages are pushed; back pops; forward is a second stack.
• Call stack — every function call pushes a frame (locals, return address); return pops it. Recursion depth equals stack depth.
• Balanced parentheses — push openers, pop on closers; empty at the end means balanced.
• Depth-first search — DFS is recursion wearing a stack disguise; the iterative version uses an explicit stack.
• Backtracking — maze solving and N-queens unwind choices by popping a stack.

Worked Example: Two-Stack Dijkstra Evaluation

Dijkstra’s two-stack algorithm evaluates a fully parenthesized expression in a single pass:

1. Push operands (numbers) onto the value stack.
2. Push operators and open parentheses onto the operator stack.
3. On a closing parenthesis ): pop one operator and two operands, evaluate, push the result.

Walk through ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) — stacks shown bottom-first:

The final value stack holds [ 101 ] — the answer. Each token is processed once and each stack operation is O(1), so the whole evaluation is O(n). The same pattern — push, defer, resolve on a closing marker — underlies Shunting-yard, HTML/XML validation, and any reversible left-to-right reduction.

Part 2 — Queues: First In, First Out

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle: the first element enqueued is the first one dequeued. Think of a ticket line — the first person in line is served first, and newcomers join the back. FIFO is the fairness guarantee behind everything from CPU scheduling to message brokers: whoever arrived first goes first.

Core Operations

• Enqueue(item) — add to the back — O(1)
• Dequeue() — remove and return the front — O(1)
• Front() — return the front without removing it — O(1)
• isEmpty() — check emptiness — O(1)

The front (dequeue side) and back (enqueue side) are the only two access points, so a correct queue tracks both ends.

Array (Ring Buffer) vs Linked List

A ring buffer is an array whose head and tail indices wrap with modular arithmetic; when the size counter hits capacity the buffer is full. That fixed, contiguous layout is exactly why it backs logs, network buffers, and audio FIFOs. A linked-list queue (with a tail pointer) wins when the depth is unbounded and there is no natural cap.

Why Enqueue and Dequeue Are O(1)

Both implementations achieve O(1) at both ends, but for different reasons:

• Array: head = (head + 1) % capacity — nothing shifts, elements never move.
• Linked list: only the head or tail node is touched; no traversal from one end to the other.

The failure mode to avoid is the naive array queue that shifts every element left on dequeue — that’s O(n) per dequeue and turns a queue into a quadratic mess. If you see a dequeue that moves elements, it’s wrong.

BFS: The Queue’s Home Turf

Breadth-first search explores a graph level by level using a queue. Dequeue a node, enqueue every unvisited neighbor; because the queue is FIFO, nodes are discovered in order of distance from the source — which guarantees the shortest path in unweighted graphs:

BFS(start):
  queue ← [start]; mark start visited
  while queue is not empty:
    v ← dequeue(queue)
    process v
    for each neighbor u of v:
      if u is not visited:
        mark u visited
        enqueue(queue, u)

The first time a node is popped, it is at minimal distance from the start. Swap the queue for a stack and BFS becomes DFS — the two algorithms differ only in the container.

Priority Queues vs Deques

• Priority queue — dequeue returns the highest- (or lowest-) priority element, not the oldest. Backed by a binary heap, insert and extract are O(log n). This is what Dijkstra’s algorithm and task schedulers use when arrival order is irrelevant and priority is everything.
• Deque (double-ended queue) — insert and remove at both ends in O(1). The workhorse of sliding-window problems, palindrome checks, and bounded buffers where you add to one side and evict from the other.

A deque is a generalized queue; a priority queue is a different contract entirely — ordering by priority, not by arrival.

Applications

• BFS / shortest path in unweighted graphs — the level-by-level discovery guarantee.
• Task scheduling — round-robin CPU scheduling hands the ready queue FIFO turns.
• Message queues — producers enqueue, consumers dequeue; Kafka partitions are append-only FIFO logs.
• LRU cache — a deque (or doubly-linked list) plus a hash map gives O(1) promotion and O(1) eviction of the least-recently-used item.
• Resource pools — thread pools and DB connection pools hand out connections FIFO for fairness.
• Buffering — I/O buffers, print spooling, and streaming back-pressure.

Worked Example: Ring Buffer by Hand

A ring buffer of capacity 4, tracking a size counter. Start empty: head = 0, tail = 0, size = 0.

enqueue a, b, c, d     → [ a b c d ]  size = 4   (full)
dequeue()              → a            head = 1, size = 3
enqueue e              → writes slot 0           tail = (0+1) % 4 = 1, size = 4
                         [ e b c d ]

After the wrap, the logical order is b c d e — the ring rotated without moving a single element. Every operation is an array read/write plus an index increment: no shifting, no allocation, no O(n) anywhere. That is the entire point of the ring buffer.

Practice Trajectory

1. Implement a stack twice — array-backed and linked-list-backed — and note the first’s resize behavior.
2. Solve balanced parentheses for three bracket types with a single stack.
3. Implement a MinStack (push, pop, min all O(1)) using an auxiliary stack.
4. Evaluate the postfix expression 3 4 + 5 * with one stack.
5. Convert a recursive DFS into an explicit-stack iterative version and compare space usage.
6. Implement a queue with a ring buffer and verify wraparound when the buffer fills.
7. Implement a deque with a doubly-linked list; confirm O(1) at both ends.
8. Run BFS on a small grid and print the distance from the source to every cell.
9. Implement an LRU cache using a deque (or doubly-linked list) plus a hash map.
10. Compare a priority queue against a deque for the sliding-window maximum problem and explain the difference.

When to Use Which