sdlc.dev

Data structures and algorithms path · Sequences · Topic 4 of 13

Stacks and queues

Not started

A stack and a queue are both containers you add to and take from, and the only difference is which item comes out next. A stack hands back the most recently added item (last in, first out), like a pile of plates. A queue hands back the item that has waited longest (first in, first out), like a checkout line. Choosing between them is choosing an order of work, and that choice is behind undo history, parsers, depth-first versus breadth-first search and job processing.

Why it matters: Undo, parsing, the call stack, depth-first search, job queues, breadth-first search and every message broker are one of these two.

  1. 1A stack is LIFO

    push adds to the top and pop removes from the top, so the most recent item comes out first. Both are O(1) on the end of an array.

  2. 2A queue is FIFO

    Items leave in the order they arrived. Adding at one end and removing at the other needs care to stay O(1).

  3. 3shift() is not a queue

    Removing from the front of an array moves every remaining element. Use a ring buffer, a deque or two indexes.

  4. 4Bound your queues

    An unbounded queue between a fast producer and a slow consumer is a memory leak with a delay.

1

Watch it run

Play it or step through. Every step says what just happened.

const pairs = { ")": "(", "]": "[", "}": "{" };function balanced(s) {  const stack = [];  for (const ch of s) {    if ("([{".includes(ch)) stack.push(ch);    else if (stack.pop() !== pairs[ch]) return false;  }  return stack.length === 0;}console.log(balanced("([]{})"));console.log(balanced("(]"));

Characters still to read

The rest of the string, front first

empty

Stack

Open brackets waiting to be closed; top is the newest

empty

Matched

Pairs that closed correctly

empty

Console0 lines

    Step 0 of 12

    Nothing has run yet. The function walks the string once and keeps unmatched open brackets on a stack.

    The same shape, a stack of things still open, is how parsers match tags and how your language's call stack tracks which function to return to.

    2

    Try it yourself

    Change the code, predict the order, then run it for real in your browser.

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    3

    Check yourself

    3 questions. Get them all right to finish this topic.

    1. 1.You push 1, 2, 3 onto a stack and enqueue 1, 2, 3 into a queue. What do pop and dequeue return?
    2. 2.Why does checking balanced brackets use a stack?
    3. 3.In a ring buffer of capacity 4 with head at index 3 and 2 items, where does the next enqueue go?

    0 of 3 right so far. Get all three to finish this topic.

    Stacks

    A stack needs two operations, push and pop, both at the same end. The end of a dynamic array is perfect: arr.push(x) and arr.pop() in JavaScript, list.append and list.pop() in Python, ArrayDeque.push and pop in Java (its docs say it is likely to be faster than the old Stack class). Your program's call stack is one: each call pushes a frame and each return pops it, which is why recursion and explicit stacks are interchangeable. Depth-first search, undo and redo, and evaluating expressions all use one.

    Queues

    A queue adds at the back and removes from the front. On a plain array, removing from the front is shift(), which moves every remaining element, so a busy queue becomes O(n) per operation. Two standard fixes:

    • A ring buffer: a fixed array plus a head index and a count. Enqueue writes at (head + size) % capacity, dequeue reads at head and advances it, and both wrap around the end. Grow it like a dynamic array when it fills. This is how ArrayDeque works; Python's collections.deque uses linked blocks of elements for the same O(1) at both ends.
    • Two indexes into a growing array, compacting occasionally.
    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    After two dequeues, "e" and "f" land in slots 0 and 1, the space freed at the front, and the order still comes out right.

    Queues are also how systems absorb bursts: work arrives faster than it can be handled for a while, and the queue holds the difference. If the burst never ends, an unbounded queue just grows until memory runs out. A bounded queue that makes producers wait or rejects new work is the honest version, and it is the idea behind backpressure.

    Go deeper