JS-201 · Lesson 4 of 12 · 25 min

Stacks and queues

▶ Video coming soon A video version of this lesson is on the way.

Two requests reached Brightwater over the summer. Rosa Delgado, who runs the community kitchen and the lunch counter, asked for an Undo button on the counter page, because trainees sometimes tap the wrong dish and have to start an order again. And Lucy asked whether the grocery waitlist could put urgent cases ahead of everyone else without anyone reordering the list by hand. At the fourth session, on Thursday, September 16, Gareth shows that both requests are about the same question: in what order should things come back out?

A stack gives things back in the reverse of the order they went in. A queue gives them back in the same order. A priority queue gives back whichever has the highest priority. These three are abstract data types: each is defined by what its operations do, not by how it is built, and each can be built in more than one way.

Stacks: last in, first out

A stack works like a pile of trays at the counter: you add to the top and take from the top. The operations are push, which adds a value, pop, which removes and returns the most recently added value, and peek, which looks at the top without removing it. This order is called LIFO, last in, first out. A JavaScript array is already a good stack: push and pop work at the end, and both are O(1).

Left: a vertical stack of four boxes labeled Soup, Drink, Egg sandwich and Cookie from bottom to top, with push and pop arrows both at the top. Right: a horizontal queue of four boxes labeled Okafor, Nguyen, Haddad and Silva, with an enqueue arrow entering at the back on the right and a dequeue arrow leaving at the front on the left.
A stack adds and removes at the same end; a queue adds at the back and removes from the front.

Stacks appear wherever work has to be undone or resumed in reverse order. The JavaScript engine's call stack, from JavaScript Programming II, is one: each function call pushes a frame, each return pops it, and the function that finishes first is the one called last. Undo is another. Every change pushes a record of what was done, and Undo pops the most recent one and reverses it.

JavaScript Example · Undo and redo with two stacks
const order = [];
const undoStack = [];
const redoStack = [];

function add(item) { order.push(item); undoStack.push(item); redoStack.length = 0; }
function undo() {
  if (undoStack.length === 0) return;
  const item = undoStack.pop();
  order.splice(order.lastIndexOf(item), 1);
  redoStack.push(item);
}
function redo() {
  if (redoStack.length === 0) return;
  const item = redoStack.pop();
  order.push(item);
  undoStack.push(item);
}

add('SOUP'); add('EGG'); add('DRINK');
undo();                       // the trainee tapped DRINK by mistake
console.log(order);
redo();                       // no, the customer did want a drink
console.log(order);
undo(); undo();
add('COOKIE');                // a new change clears the redo stack
console.log(order, 'redo available:', redoStack.length);
Output
[ "SOUP", "EGG" ]
[ "SOUP", "EGG", "DRINK" ]
[ "SOUP", "COOKIE" ] redo available: 0

What this code does

Each add records the item on the undo stack, and undo pops the most recent record, removes that item and pushes it onto the redo stack. redo moves it back the other way. A new add empties the redo stack, which matches how Undo and Redo behave in most programs.

The counter page's real version records whole actions, such as "added one soup" or "changed the tip to 10 in 100", rather than just dish codes, but the stacks work the same way. Recording actions instead of copies of the whole order keeps each step O(1) in memory.

Checking brackets with a stack

A stack is also the natural tool for checking that brackets are balanced, which editors and parsers do constantly. Read the text from left to right. Push every opening bracket. For every closing bracket, pop the stack and check that the popped bracket is the matching opener. At the end the stack must be empty. Nested brackets have to close in the reverse order they opened, which is exactly what LIFO means.

JavaScript Example · Balanced brackets
function balanced(text) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of text) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

console.log(balanced('{ "shifts": [ { "id": 1 }, { "id": 2 } ] }'));
console.log(balanced('totals(sum([1, 2), 3])'));
console.log(balanced('((('));
console.log(balanced(''));
Output
true
false
false
true

What this code does

balanced pushes each opening bracket and, for each closing bracket, pops the most recent opener and checks that it matches. The second string fails because a round bracket closes while a square one is still open. The third fails because openers are left on the stack, and the empty string counts as balanced.

Queues: first in, first out

A queue works like the line at the counter. New arrivals join at the back with enqueue, and the person at the front is served next with dequeue. This order is FIFO, first in, first out. Queues appear wherever work must be handled fairly in arrival order: print jobs, messages waiting to be sent, families waiting for a grocery slot and, in Lesson 10, the places still to visit in a breadth-first search.

The obvious JavaScript queue is an array with push to enqueue and shift to dequeue. It is correct, but as Lesson 2 showed, shift moves every remaining element, so each dequeue is O(n) and a long run of them is O(n²). The simulation below counts the moves for a busy day of 5,000 waitlist changes.

JavaScript Example · The hidden cost of shift
function moves(n) {
  // Dequeueing n items one at a time with shift moves (n-1) + (n-2) + ... + 0 elements.
  let total = 0;
  for (let left = n; left > 0; left--) total += left - 1;
  return total;
}
for (const n of [40, 500, 5000]) console.log('dequeue', n, 'items with shift:', moves(n), 'element moves');
Output
dequeue 40 items with shift: 780 element moves
dequeue 500 items with shift: 124750 element moves
dequeue 5000 items with shift: 12497500 element moves

What this code does

Each shift has to move all the elements still behind it, so emptying a queue of n items moves n times (n minus 1) divided by 2 elements in total. For 40 families that is trivial, but for 5,000 items it is over 12 million moves. The cost grows quadratically, like the nested loops in Lesson 1.

In practice, engines have tricks that make shift on small arrays faster than this simple count suggests, but the growth is still there for large arrays. A queue that is fast for any size needs a different design.

A fast queue

The simplest fast queue keeps the array and a head index pointing to the front item. Dequeue reads the item at head and adds one to head; nothing moves. The slots before head are wasted, so now and then, when more than half of the array is used-up slots, the queue copies the live part into a fresh array. That copy is O(n), but it happens so rarely that dequeue is amortized O(1), for the same reason push is.

JavaScript Example · A queue with a head index
class Queue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(x) { this.items.push(x); }                 // O(1) amortized
  dequeue() {                                        // O(1) amortized
    if (this.head === this.items.length) return undefined;
    const x = this.items[this.head];
    this.items[this.head] = undefined;               // let the value be collected
    this.head++;
    if (this.head > 1000 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head);      // compact now and then
      this.head = 0;
    }
    return x;
  }
  peek() { return this.items[this.head]; }
  get size() { return this.items.length - this.head; }
}

const waitlist = new Queue();
for (const f of ['Okafor', 'Nguyen', 'Haddad', 'Silva']) waitlist.enqueue(f);
console.log('next:', waitlist.dequeue(), '| then:', waitlist.dequeue());
waitlist.enqueue('Moreau');
console.log('front:', waitlist.peek(), '| size:', waitlist.size);

// A long run: 100,000 families join and leave.
const big = new Queue();
let served = 0;
for (let i = 0; i < 100000; i++) { big.enqueue(i); if (i % 3 !== 0) { big.dequeue(); served++; } }
console.log('served', served, 'still waiting', big.size, 'array length', big.items.length);
Output
next: Okafor | then: Nguyen
front: Haddad | size: 3
served 66666 still waiting 33334 array length 35810

What this code does

The Queue keeps an array and a head index, so dequeue only reads one slot and moves head forward. When the used-up slots at the front outnumber the live ones, it slices off the dead part, which keeps memory in check while leaving each operation O(1) amortized. The long run shows the array staying well under twice the number of families still waiting, instead of growing to 100,000 slots.

A linked list with head and tail references, from Lesson 3, is the other classic way to build a queue: enqueue appends at the tail and dequeue removes the head, both O(1) every time. The array version is usually faster in JavaScript because of memory locality, and it is the one riverside-data uses. A deque, a double-ended queue, allows adding and removing at both ends; it can be built from a doubly linked list or a ring buffer.

Ring buffers

Sometimes a queue only needs to remember the most recent items. The counter page shows the last five orders on a side panel, and the dashboard keeps the last 60 minutes of order counts for a small chart. A ring buffer, also called a circular buffer, does this in a fixed-size array. It keeps the index of the oldest item and a count. A new item is written into the slot after the newest one, wrapping round to slot 0 at the end of the array, and when the buffer is full the new item overwrites the oldest.

Five array slots arranged in a circle, numbered 0 to 4. Slots hold orders 46, 47, 43, 44 and 45. An arrow labeled oldest points at slot 2 holding 43, and an arrow labeled newest points at slot 1 holding 47. A curved arrow shows the next write going into slot 2, replacing the oldest order.
A ring buffer of five slots after seven writes: positions wrap round, and the next write replaces the oldest entry.

The wrapping is done with the remainder after division: slot (start + i) modulo capacity. Every operation is O(1), the memory never grows, and nothing is ever moved. That makes ring buffers popular for logs, audio and network data, and anything else that streams.

JavaScript Example · A ring buffer for the last five orders
class RingBuffer {
  constructor(capacity) { this.buf = new Array(capacity); this.start = 0; this.count = 0; }
  push(x) {
    const cap = this.buf.length;
    this.buf[(this.start + this.count) % cap] = x;
    if (this.count < cap) this.count++;
    else this.start = (this.start + 1) % cap;    // full: the oldest is overwritten
  }
  toArray() {
    const out = [];
    for (let i = 0; i < this.count; i++) out.push(this.buf[(this.start + i) % this.buf.length]);
    return out;
  }
}

const recent = new RingBuffer(5);
for (let order = 41; order <= 47; order++) recent.push(order);
console.log('last five orders, oldest first:', recent.toArray());
console.log('slots as stored:', recent.buf, 'start', recent.start);
Output
last five orders, oldest first: [ 43, 44, 45, 46, 47 ]
slots as stored: [ 46, 47, 43, 44, 45 ] start 2

What this code does

push writes each order into the slot after the newest one, using the remainder to wrap round to the start of the array. Once all five slots are full, each new order overwrites the oldest and moves start forward. toArray reads the slots from start, so it always lists the five most recent orders in order.

Priority queues and heaps

Lucy's urgent cases need a different rule: not first come, first served, but most urgent first, and among equally urgent families, whoever has waited longest. A priority queue has two main operations: insert a value with a priority, and remove the value with the highest priority. Keeping an array sorted would make removal O(1) but insertion O(n). Searching an unsorted array would make insertion O(1) but removal O(n). A binary heap makes both O(log n).

A binary heap is a tree stored in an array. The item at index i has children at 2i + 1 and 2i + 2, and its parent at the whole-number part of (i − 1) ÷ 2. In a min-heap, every parent is smaller than or equal to its children, so the smallest item is always at index 0. To insert, put the new item at the end and swap it upwards while it is smaller than its parent. To remove the smallest, move the last item to the top and swap it downwards with its smaller child until the order is restored. The tree is always as short as possible, about log₂ n levels, so each operation makes at most about log₂ n swaps.

JavaScript Example · A priority queue built on a binary heap
class MinHeap {
  constructor(less = (a, b) => a < b) { this.a = []; this.less = less; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {                                          // O(log n)
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;                        // parent index
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {                                            // O(log n)
    const a = this.a;
    if (a.length === 0) return undefined;
    const top = a[0], last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

// Lower urgency number = more urgent; ties go to the earlier arrival.
const byUrgency = (a, b) => a.urgency < b.urgency || (a.urgency === b.urgency && a.arrived < b.arrived);
const waitlist = new MinHeap(byUrgency);
const families = [['Okafor', 3], ['Nguyen', 3], ['Larsen', 1], ['Haddad', 2], ['Silva', 1], ['Moreau', 3]];
families.forEach(([name, urgency], arrived) => waitlist.push({ name, urgency, arrived }));

const served = [];
while (waitlist.size > 0) { const f = waitlist.pop(); served.push(f.name + ' (' + f.urgency + ')'); }
console.log(served.join(', '));
Output
Larsen (1), Silva (1), Haddad (2), Okafor (3), Nguyen (3), Moreau (3)

What this code does

MinHeap keeps its items in an array arranged so that every parent comes before its children under the less function, so the first item is always the most urgent family. push adds a family at the end and swaps it upwards, and pop moves the last family to the top and swaps it downwards. The comparison uses arrival order to break ties, so equally urgent families are served in the order they joined.

A heap is not fully sorted, only sorted enough that the top is always right, which is why it is cheaper than a sorted array. JavaScript has no built-in heap, so riverside-data now includes this MinHeap class with a comparison function. Lesson 10 uses it to find the quickest delivery routes, and Lesson 12 uses it to find the busiest shifts without sorting them all.

Stacks, queues and their relatives.
StructureOrder outAddRemoveBuilt from
StackLast in, first outO(1)O(1)Array with push and pop
QueueFirst in, first outO(1) amortizedO(1) amortizedArray with a head index, or a linked list
Ring bufferOldest first, fixed sizeO(1)O(1)Fixed array with start and count
Priority queueHighest priority firstO(log n)O(log n)Binary heap in an array

Try it yourself

Brackets and quotes

Complete balanced(text) so that it returns true when every (, [ and { in text is closed by the matching bracket in the right order, and false otherwise. Use an array as a stack.

Characters that are not brackets are ignored.

function balanced(text) {
  let open = 0;
  for (const ch of text) {
    if ('([{'.includes(ch)) open++;
    if (')]}'.includes(ch)) open--;
  }
  return open === 0;
}

console.log(balanced('{ "a": [1, (2)] }'));
console.log(balanced('[(])'));
console.log(balanced('(()'));
console.log(balanced(')('));

Try it yourself

A queue that never shifts

Complete the dequeue method so that it returns the item at the front of the queue without calling shift. Use the head index and move it forward. Return undefined when the queue is empty.

The size getter is already written and depends on head.

class Queue {
  constructor() { this.items = []; this.head = 0; }
  enqueue(x) { this.items.push(x); }
  dequeue() {
    return undefined;
  }
  get size() { return this.items.length - this.head; }
}

const q = new Queue();
q.enqueue('Okafor'); q.enqueue('Nguyen'); q.enqueue('Haddad');
console.log(q.dequeue(), q.dequeue(), q.size);
q.enqueue('Silva');
console.log(q.dequeue(), q.dequeue(), q.dequeue(), q.size);
console.log(Queue.prototype.dequeue.toString().includes('shift') ? 'uses shift' : 'no shift');

Try it yourself

The last three readings

The walk-in fridge sends a temperature reading every minute, and the kitchen screen shows the last three. Complete push in the Last3 class so that it keeps only the three most recent readings in a fixed array of three slots, overwriting the oldest when full.

toArray is written for you and lists the readings oldest first.

class Last3 {
  constructor() { this.buf = [undefined, undefined, undefined]; this.start = 0; this.count = 0; }
  push(x) {
    this.buf[this.count] = x;
    this.count++;
  }
  toArray() {
    const out = [];
    for (let i = 0; i < this.count; i++) out.push(this.buf[(this.start + i) % 3]);
    return out;
  }
}

const fridge = new Last3();
for (const t of [3.1, 3.4, 3.2, 4.0, 4.6]) fridge.push(t);
console.log(fridge.toArray().join(' '));
console.log(fridge.buf.length);

Common mistakes

  • MistakeUsing shift to dequeue from a large array.

    Insteadshift is O(n). Use a head index, a linked list or a ring buffer.

  • MistakeChecking brackets by counting openers and closers.

    InsteadCounts miss wrong nesting such as [(]). A stack checks the order.

  • MistakeKeeping a priority queue as a sorted array.

    InsteadEach insertion is O(n). A binary heap makes insertion and removal O(log n).

  • MistakeExpecting a heap's array to be fully sorted.

    InsteadOnly the top is guaranteed to be the smallest; the rest is partly ordered.

  • MistakeForgetting to clear the redo stack after a new change.

    InsteadA new action makes the old redo history meaningless, so empty it.

Summary and key terms

  • A stack returns items last in, first out, and an array's push and pop make a stack with O(1) operations.
  • Stacks drive undo and redo, bracket checking and the engine's call stack.
  • A queue returns items first in, first out.
  • Using shift to dequeue is O(n) each time, so a fast queue keeps a head index into an array and compacts it occasionally, giving amortized O(1), or uses a linked list.
  • A ring buffer keeps the most recent items in a fixed array, wrapping its positions with the remainder after division, so every operation is O(1).
  • A priority queue returns the highest-priority item first.
  • A binary heap stores it as an array in which every parent comes before its children, so the top item is at index 0 and insertion and removal take O(log n) swaps.
  • JavaScript has no built-in queue or heap, so they are written as small classes.
stack
A collection that returns items in last in, first out order.
LIFO
Last in, first out: the most recently added item is removed first.
queue
A collection that returns items in first in, first out order.
FIFO
First in, first out: the earliest added item is removed first.
abstract data type
A collection defined by what its operations do, not by how it is built.
deque
A double-ended queue that allows adding and removing at both ends.
ring buffer
A fixed-size array used as a queue whose positions wrap round, overwriting the oldest item when full.
priority queue
A collection that always removes the item with the highest priority next.
binary heap
A tree kept in an array in which every parent comes before its children, giving O(log n) insertion and removal.
min-heap
A binary heap whose smallest item is always at the top.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Why is an array with push and pop a good stack?

    Show answer

    Both work at the end of the array and are O(1).

  2. What goes wrong with an array queue that uses shift?

    Show answer

    Each shift moves every remaining element, so n dequeues cost O(n²) in total.

  3. In a heap stored in an array, where are the children of index 3?

    Show answer

    At indexes 7 and 8.

  4. A ring buffer of capacity 4 has start 3 and count 2. Which slots hold its items?

    Show answer

    Slots 3 and 0, because the positions wrap round.

  5. What are the costs of insert and remove in a binary heap?

    Show answer

    O(log n) each, because the tree has about log₂ n levels.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz