
A stack is a last-in-first-out (LIFO) collection: the last item you push in is the first one you get back, like a pile of plates. A queue is first-in-first-out (FIFO): items leave in the order they arrived, like a line at a coffee shop. Both are abstract interfaces, not specific data structures - JavaScript arrays can implement either.

<ExamplePair>
<ExampleProse>

A stack on top of an array uses `push` to add to the top and `pop` to remove from the top. Both are O(1): they touch only the last element, so the array never has to shift anything around. A classic use case is an undo history: each action goes on the stack; pressing undo pops the most recent one off.

</ExampleProse>
<ExampleCode>

```js
const undoStack = [];

function doAction(action) {
  undoStack.push(action);
  console.log("Did:", action);
}

function undo() {
  const last = undoStack.pop();
  if (last) {
    console.log("Undid:", last);
  } else {
    console.log("Nothing to undo");
  }
}

doAction("type 'hello'");  // Did: type 'hello'
doAction("bold selection"); // Did: bold selection
undo();                     // Undid: bold selection
undo();                     // Undid: type 'hello'
undo();                     // Nothing to undo
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

A queue on top of an array uses `push` to add to the back and `shift` to remove from the front. The `shift` operation is O(n) because the browser has to move every remaining element one index earlier. For small queues that's fine; for a hot queue (many items, high throughput) the cost adds up.

</ExampleProse>
<ExampleCode>

```js
const printQueue = [];

function enqueue(job) {
  printQueue.push(job);
}

function dequeue() {
  return printQueue.shift(); // O(n) - the whole array slides left
}

enqueue("page-1.pdf");
enqueue("page-2.pdf");
enqueue("page-3.pdf");

console.log(dequeue()); // "page-1.pdf"
console.log(dequeue()); // "page-2.pdf"
console.log(dequeue()); // "page-3.pdf"

// Checking length and front without removing
const taskQueue = ["alpha", "beta", "gamma"];
console.log(taskQueue.length);  // 3
console.log(taskQueue[0]);      // "alpha" (peek at front without shift)
```

</ExampleCode>
</ExamplePair>

<InProduction>
Arrays make great stacks (`push` and `pop` are O(1)) but lousy queues: `shift` has to slide every element one position forward, so it's O(n). The regression is easy to miss in a benchmark that uses 100 items - it only shows up around 100,000. For a hot queue, reach for a linked-list-backed queue or a circular buffer where both enqueue and dequeue are O(1). Most job-queue and event-loop implementations inside Node.js internals use a circular buffer exactly for this reason.
</InProduction>


Stack (LIFO: push/pop) and queue (FIFO: push/shift). Arrays are great stacks but poor queues because shift is O(n); use a linked-list queue when throughput matters.

Stacks and Queues


A linked list is a chain of nodes; each node holds a value and a reference (pointer) to the next node. There is no underlying contiguous block of memory, which means inserting or removing a node at a known position is O(1) - you just rewire two pointers. The trade-off is that there is no index: to get item number 50 you have to follow the chain 50 times.

<ExamplePair>
<ExampleProse>

A minimal singly-linked list needs a `Node` class and a `LinkedList` class. `prepend` adds to the front in O(1). `append` walks to the last node and attaches there - O(n). An iteration helper (or a standard `[Symbol.iterator]`) lets you loop over the values with a `for...of` loop.

</ExampleProse>
<ExampleCode>

```js
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next; // walk to the last node
      }
      current.next = node;
    }
    this.size++;
  }

  [Symbol.iterator]() {
    let current = this.head;
    return {
      next() {
        if (!current) return { done: true, value: undefined };
        const value = current.value;
        current = current.next;
        return { done: false, value };
      },
    };
  }
}

const list = new LinkedList();
list.append("a");
list.append("b");
list.append("c");

for (const val of list) {
  console.log(val); // "a", "b", "c"
}

console.log(list.size); // 3
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

The key limitation of a linked list is the absence of random access. Getting the item at index `i` requires starting at the head and following `i` pointers. With an array the same operation returns instantly because the runtime can compute the memory address directly from the index.

</ExampleProse>
<ExampleCode>

```js
class LinkedList {
  // ... (same as above)
  get(index) {
    let current = this.head;
    let i = 0;
    while (current) {
      if (i === index) return current.value;
      current = current.next;
      i++;
    }
    return undefined; // index out of bounds
  }
}

// Linked list: O(n) - must walk from the head
const list = new LinkedList();
for (let i = 0; i < 1000; i++) list.append(i);
console.log(list.get(999)); // 999 - walked 1000 nodes

// Array: O(1) - computed from base address + offset
const arr = Array.from({ length: 1000 }, (_, i) => i);
console.log(arr[999]); // 999 - instant lookup
```

</ExampleCode>
</ExamplePair>

<InProduction>
Pointer chasing (following a chain of references scattered across the heap) destroys CPU cache locality: each node read is likely a cache miss, which is far slower than reading a contiguous array. In V8, arrays win for almost every application-code use case. The real production scenario where a linked list earns its keep is a doubly-linked list inside an LRU cache: you need O(1) insertion and O(1) removal at arbitrary positions, and you always have a direct reference to the node you want to move, so you never have to scan.
</InProduction>


Linked list: nodes chained via pointers. O(1) insert/remove at known positions, but no random access - walking n nodes to reach index i means arrays win for most application code.

Linked Lists


A regular expression is a small pattern language for matching text. JavaScript has it built in: you can write a pattern as a literal between slashes (`/foo/`) or construct one at runtime with `new RegExp("foo")`. Methods on strings and RegExp objects let you test, search, capture, and replace using those patterns.

<ExamplePair>
<ExampleProse>

`test` checks whether a pattern appears anywhere in a string and returns a boolean. `match` returns the matched text (and capture groups) or `null`. The `g` flag makes `match` return every occurrence instead of just the first.

</ExampleProse>
<ExampleCode>

```js
// test - returns true or false
console.log(/cat/.test("concatenate")); // true
console.log(/cat/.test("dog"));         // false

// match without g - first occurrence + index
const result = "hello world".match(/\w+/);
console.log(result[0]);     // "hello"
console.log(result.index);  // 0

// match with g - all occurrences as an array
const all = "hello world".match(/\w+/g);
console.log(all); // ["hello", "world"]
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

Capture groups, written as `(...)`, let you extract specific parts of a match. `exec` returns a single match with its groups as array slots. Named groups (`(?<name>...)`) make the captured values accessible by name instead of by index, which keeps regex code readable when there are several groups.

</ExampleProse>
<ExampleCode>

```js
// Numbered capture groups
const numbered = /(\w+)@(\w+)/.exec("user@example");
console.log(numbered[1]); // "user"
console.log(numbered[2]); // "example"

// Named capture groups - much easier to read
const named = /(?<user>\w+)@(?<host>\w+)/.exec("user@example");
console.log(named.groups.user); // "user"
console.log(named.groups.host); // "example"

// matchAll iterates all matches including their groups
const emails = "a@b.com c@d.com";
for (const match of emails.matchAll(/(?<user>\w+)@(?<host>[\w.]+)/g)) {
  console.log(match.groups.user, match.groups.host);
}
// "a" "b.com"
// "c" "d.com"
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

`replace` swaps matched text with a string or the return value of a function. Passing a function replacer is the most flexible form: it receives the full match plus any capture groups, so you can transform each match individually.

</ExampleProse>
<ExampleCode>

```js
// Simple string replacement (g flag replaces all)
const dashes = "2026-04-27".replace(/-/g, "/");
console.log(dashes); // "2026/04/27"

// Function replacer - called once per match
const words = "hello world";
const titled = words.replace(/\b\w/g, (char) => char.toUpperCase());
console.log(titled); // "Hello World"

// Function replacer with named groups
const date = "2026-04-27";
const reordered = date.replace(
  /(?<y>\d{4})-(?<m>\d{2})-(?<d>\d{2})/,
  (_, y, m, d) => `${d}/${m}/${y}`
);
console.log(reordered); // "27/04/2026"
```

</ExampleCode>
</ExamplePair>

<InProduction>
Catastrophic backtracking - where the regex engine exhausts every possible combination before giving up - can hang the event loop on user-supplied input. The classic trap is nested quantifiers like `(a+)+` applied to a string that nearly matches: the engine tries exponentially many paths. Anchor your patterns (`^` and `$`) where you can, keep quantifiers flat, and run any regex that touches untrusted strings through a static analyzer like `safe-regex` or the `eslint-plugin-security` rule `detect-unsafe-regex`.
</InProduction>


Regular expressions match and transform text using patterns built into JS - write them as /foo/ literals or new RegExp("foo"), with flags like g (global) and i (case-insensitive).