Stacks, queues, trees and graphs in JavaScript

JavaScript has no built-in stack, queue, tree or graph type. It has arrays, objects, Map and Set, and a few lines of code are usually enough to turn those into the structure you need. What these structures are, and what operations cost, is in the fundamentals lessons on stacks, queues and linked lists and on trees and graphs. This lesson is about writing them the JavaScript way, using the classes, private fields, generators and collections from this module.

Arrays as stacks

A stack adds and removes at one end, last in, first out. An array already does that with push and pop, and at(-1) looks at the top without removing it.

const stack = [];
stack.push("a");
stack.push("b");
stack.push("c");

console.log(stack.at(-1), stack.length);
console.log(stack.pop(), stack.pop(), stack);

c 3
c b [ 'a' ]

function reverse(text) {
  const letters = [...text];
  let result = "";
  while (letters.length > 0) {
    result += letters.pop();
  }
  return result;
}
console.log(reverse("stack"));

kcats

reverse shows the idea in use: pushing letters and popping them gives them back in the opposite order. Here the array is consumed with pop in a while loop. ([...text].reverse().join("") is shorter in practice. The point is the stack.) For a stack, a plain array is the right structure, and wrapping it in a class only helps when you want to hide the array.

Queues

A queue adds at the back and removes from the front, first in, first out. It is tempting to use push and shift on an array, and for short queues that is fine. The catch is that shift removes the first item, and the engine may have to move every other item down one place. V8 hides that cost for small arrays. In tests on Node 22 and 26, emptying an array of 10,000 numbers with shift took about a millisecond, while 100,000 numbers took seconds, ten times the items for well over a thousand times the work. The exact numbers depend on the machine and the engine version, but that jump does not. A queue that tracks where its front is avoids the problem.

class Queue {
  #items = new Map();
  #head = 0;

  enqueue(value) {
    this.#items.set(this.#head + this.#items.size, value);
  }

  dequeue() {
    const value = this.#items.get(this.#head);
    if (this.#items.delete(this.#head)) {
      this.#head += 1;
    }
    return value;
  }

  get size() {
    return this.#items.size;
  }
}

Enqueue two items and take them out again, including one dequeue from an empty queue:

const queue = new Queue();
queue.enqueue("first");
queue.enqueue("second");
console.log(queue.dequeue(), queue.size);
console.log(queue.dequeue(), queue.dequeue(), queue.size);

first 1
second undefined 0

The queue stores items in a Map under increasing numeric keys and remembers the key of the front item in #head. enqueue adds under the next free key, which is #head plus the number of items. dequeue reads the front item and removes it, and only then moves #head on. Dequeuing from an empty queue finds nothing, deletes nothing, and returns undefined. Nothing is shifted, and the private fields keep callers from touching the keys.

Linked lists

A linked list is a chain of nodes where each node holds a value and a reference to the next node. Adding at the front is quick, because only a new node and one reference change. Reaching the n-th item means following n references, which is the cost of not having an array’s numbered slots.

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

The list keeps its head and size in private fields, and is iterable through a generator method:

class LinkedList {
  #head = null;
  #size = 0;

  prepend(value) {
    this.#head = new ListNode(value, this.#head);
    this.#size += 1;
    return this;
  }

  get size() {
    return this.#size;
  }

  *[Symbol.iterator]() {
    for (let node = this.#head; node !== null; node = node.next) {
      yield node.value;
    }
  }
}

Build a list and use it with spread and Math.max:

const list = new LinkedList().prepend(3).prepend(2).prepend(1);
console.log([...list], list.size);
console.log(Math.max(...list));

[ 1, 2, 3 ] 3
3

prepend makes a node that points at the old head and makes it the new head, so the items come out in the reverse order they were added. The generator method *[Symbol.iterator] from lesson 9 walks the chain with a for loop whose step is node = node.next. Because the list is iterable, spread, Math.max(...list), for...of and the iterator helpers all work on it without any more code.

Binary search trees

A tree is nodes with children, and a binary search tree keeps smaller values in the left child and larger ones in the right. Each step of a search discards one side. Each node is a plain object, and the operations are short recursive functions, as in the recursion lesson.

function insert(node, value) {
  if (node === null) {
    return { value, left: null, right: null };
  }
  if (value < node.value) {
    node.left = insert(node.left, value);
  } else {
    node.right = insert(node.right, value);
  }
  return node;
}

Searching and measuring follow the same recursive shape:

function contains(node, value) {
  if (node === null) {
    return false;
  }
  if (value === node.value) {
    return true;
  }
  return contains(value < node.value ? node.left : node.right, value);
}

function height(node) {
  if (node === null) {
    return 0;
  }
  return 1 + Math.max(height(node.left), height(node.right));
}

Build a tree from six values and query it:

let root = null;
for (const n of [5, 2, 8, 1, 9, 3]) {
  root = insert(root, n);
}
console.log(contains(root, 3), contains(root, 7), height(root));
console.log(root.left.value, root.right.value);

true false 3
2 8

insert returns the node it was given, or a new node if the spot was empty, and the caller stores the result. That makes the first insert and the later ones the same code. contains goes left or right according to the comparison. height counts the levels. For the values 5, 2, 8, 1, 9, 3 the tree has three levels, and the root has 2 on its left and 8 on its right.

How well a search tree performs depends on its shape. Inserting already sorted values makes every node go right, and the tree turns into a list. Self-balancing trees fix that, and in real programs you would usually use a Map or a sorted array instead of writing a tree. Walking the tree in order, with yield* recursion as in the generators lesson, gives the values sorted.

Graphs

A graph is nodes connected by edges. The usual representation is an adjacency list: for each node, the nodes next to it. In JavaScript a Map from node name to a Set of neighbours is clear, because a set ignores a repeated edge and tests for one in a single call.

const graph = new Map();

function addEdge(a, b) {
  for (const [from, to] of [[a, b], [b, a]]) {
    if (!graph.has(from)) {
      graph.set(from, new Set());
    }
    graph.get(from).add(to);
  }
}

addEdge("home", "shop");
addEdge("home", "park");
addEdge("shop", "mall");
addEdge("park", "mall");
addEdge("mall", "cinema");
console.log(graph.get("home"), graph.size);

Set(2) { 'shop', 'park' } 5

addEdge adds the edge in both directions, which makes the graph undirected, creating a node’s set the first time it appears. The five edges produce a graph of five places, and home has two neighbours.

Breadth-first search (BFS) visits nodes in order of distance from the start: first the start, then everything one step away, then two steps, and so on. It uses a queue, and a record of what has been seen so nothing is queued twice.

function distances(start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  for (let i = 0; i < queue.length; i++) {
    const place = queue[i];
    for (const next of graph.get(place)) {
      if (!dist.has(next)) {
        dist.set(next, dist.get(place) + 1);
        queue.push(next);
      }
    }
  }
  return dist;
}

console.log(distances("home"));

Map(5) {
  'home' => 0,
  'shop' => 1,
  'park' => 1,
  'mall' => 2,
  'cinema' => 3
}

The code keeps the queue as an array and walks it with an index, instead of using shift, so it is still efficient for big graphs. dist is both the record of the distance and the “seen” check: a node that is in it has been queued already. Every node’s first visit is by a shortest route, since BFS reaches closer nodes first, which is why BFS finds shortest paths when every edge counts the same. Replace “queue” with “stack” and the same loop becomes depth-first search.

Random numbers and shuffling

Math.random() returns a number from 0 up to, but not including, 1. Scale it and round down to get a whole number in a range, and use the same idea to pick an item or shuffle an array. The Fisher-Yates shuffle walks from the end, swaps each item with a random item at or before it, and gives every order the same chance.

function randomInt(min, max, random = Math.random) {
  return Math.floor(random() * (max - min + 1)) + min;
}

function shuffle(items, random = Math.random) {
  const result = [...items];
  for (let i = result.length - 1; i > 0; i--) {
    const j = randomInt(0, i, random);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

Both functions take the random source as a parameter that defaults to Math.random. Random output cannot be printed in a lesson, so the checks below look at properties that always hold, and pass a fixed source (() => 0) to get a repeatable shuffle:

const seen = new Set();
for (let i = 0; i < 1000; i++) seen.add(randomInt(1, 6));
console.log([...seen].sort());

const deck = shuffle([1, 2, 3, 4, 5]);
console.log(deck.length, [...deck].sort());
console.log(shuffle([1, 2, 3], () => 0));

[ 1, 2, 3, 4, 5, 6 ]
5 [ 1, 2, 3, 4, 5 ]
[ 2, 3, 1 ]

A thousand throws of a six-sided die reach every face from 1 to 6, and the shuffled deck holds the same five numbers. Passing the random source in is also how you test code that uses chance. Two warnings. items.sort(() => Math.random() - 0.5) looks like a shuffle but is not fair, because sort expects a consistent comparison. And Math.random is not safe for secrets such as tokens or passwords: use crypto.randomUUID(), crypto.getRandomValues() or randomInt from node:crypto, which draw on the operating system’s secure source.

Common pitfalls

• Using shift for a large queue. It can become very slow, because the remaining items may be moved on every call. Use a head index or a structure like the one above.
• Forgetting the “seen” set in a graph walk. A cycle makes the loop run forever.
• Modifying a node’s next before saving it. In list code, keep const next = current.next before you relink, or the rest of the list is lost.
• Comparing nodes by their contents. Nodes are objects, compared by identity. Compare the value.
• Inserting sorted data into a plain binary search tree. It turns into a list. Shuffle the input or use a balanced structure.
• Popping from an empty stack and trusting the result. pop() gives undefined, which looks like a stored value. Check length when it matters.
• Recursing very deeply on a long chain. A recursive walk over a list of a hundred thousand nodes can overflow the call stack. Use a loop for long chains.

Exercises

function balanced(text) {
  const pairs = new Map([[")", "("], ["]", "["], ["}", "{"]]);
  const stack = [];
  for (const ch of text) {
    if ("([{".includes(ch)) {
      stack.push(ch);
    } else if (pairs.has(ch)) {
      if (stack.pop() !== pairs.get(ch)) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

for (const text of ["(a[b]{c})", "(]", "((", "", "a)"]) {
  console.log(JSON.stringify(text), balanced(text));
}

"(a[b]{c})" true
"(]" false
"((" false
"" true
"a)" false

function findStart(grid) {
  for (const [y, row] of grid.entries()) {
    const x = row.indexOf("S");
    if (x !== -1) {
      return [x, y];
    }
  }
}

const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];

function shortestPath(grid) {
  const start = findStart(grid);
  const seen = new Set([start.join(",")]);
  const queue = [[...start, 0]];
  for (const [x, y, steps] of queue) {
    if (grid[y][x] === "E") {
      return steps;
    }
    for (const [dx, dy] of moves) {
      const [nx, ny] = [x + dx, y + dy];
      const cell = grid[ny]?.[nx];
      if (cell === undefined || cell === "#" || seen.has(`${nx},${ny}`)) {
        continue;
      }
      seen.add(`${nx},${ny}`);
      queue.push([nx, ny, steps + 1]);
    }
  }
  return -1;
}

console.log(shortestPath(["S.#", "..#", "#.E"]));
console.log(shortestPath(["S#E"]));
console.log(shortestPath(["SE"]));

4
-1
1

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function fromArray(values) {
  let head = null;
  for (const value of [...values].reverse()) head = new ListNode(value, head);
  return head;
}

function toArray(head) {
  const values = [];
  for (let node = head; node !== null; node = node.next) {
    values.push(node.value);
  }
  return values;
}

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function fromArray(values) {
  let head = null;
  for (const value of [...values].reverse()) head = new ListNode(value, head);
  return head;
}

function toArray(head) {
  const values = [];
  for (let node = head; node !== null; node = node.next) {
    values.push(node.value);
  }
  return values;
}

function reverse(head) {
  let previous = null;
  let current = head;
  while (current !== null) {
    const next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }
  return previous;
}

console.log(toArray(reverse(fromArray([1, 2, 3, 4]))));
console.log(toArray(reverse(fromArray([7]))), reverse(null));

[ 4, 3, 2, 1 ]
[ 7 ] null

Summary

• An array is a stack with push, pop and at(-1).
• shift can make a very slow queue for large data. Keep a head index, as the Queue class does with a Map and a private #head.
• A linked list is nodes holding a value and a next. Add *[Symbol.iterator] to make it work with spread, for...of and the iterator helpers.
• A binary search tree is nodes with left and right, handled with short recursive functions. An unbalanced tree degrades into a list.
• A graph is a Map from node to a Set of neighbours. Breadth-first search uses a queue and a seen record, and finds shortest paths when all edges are equal.

That completes the first two intermediate modules. The classes, symbols and iterators here are what the rest of the level builds on.