Stacks and Queues

Two Ways to Wait
The Stack: Last In, First Out
Where You Meet Stacks at Work
Undo and Redo
Classic Problem: Balanced Brackets
More Stack Problems: Postfix and Warmer Days
The Queue: First In, First Out
Where You Meet Queues at Work
Building a Queue Well
Circular Buffers
A Queue From Two Stacks
Recipe: stack.ts and queue.ts for algolab
Try It Yourself

1. Two Ways to Wait

Picture a stack of plates in a cafeteria. You add a clean plate on the top, and you take a plate from the top. The plate that went on last is the first one to come off. Now picture a line at a ticket counter. New people join at the back, and the person at the front is served first. The one who arrived first leaves first.

Those two pictures are the two structures of this chapter:

A stack is last in, first out (LIFO).
A queue is first in, first out (FIFO).

Both are just a list with a rule that restricts where you may add and remove. That restriction is the point. A stack only touches one end. A queue adds at one end and removes at the other. Because they are so limited, they can be made very fast, and their rules match many real problems exactly. When you read code and see "stack" or "queue", you immediately know the order things come out.

In this chapter you build both, solve the classic "balanced brackets" problem, and see how the call stack and background job queues work. Stacks and queues also reappear later as the engines behind depth-first and breadth-first search.

2. The Stack: Last In, First Out

A stack has three core operations:

Operation	What it does
`push(x)`	put `x` on top
`pop()`	remove and return the top item
`peek()`	look at the top item without removing it

Plus size and isEmpty(). Every operation is O(1).

push(1)   push(2)   push(3)   pop() -> 3   pop() -> 2
                     [3]                    
           [2]       [2]       [2]
 [1]       [1]       [1]       [1]          [1]

In JavaScript, an array already does this with push and pop, both O(1) at the end (you saw that in the arrays chapter). So a stack is a thin wrapper that hides everything else an array could do:

class Stack<T> {
  private items: T[] = [];

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  push(value: T): void {
    this.items.push(value);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }
}

Why wrap an array at all? Because a Stack type promises how the data is used. Nobody can accidentally call shift() or read items[0]. A reader sees Stack<Page> and knows only the top matters.

Using it:

const s = new Stack<string>();
s.push("a");
s.push("b");
s.push("c");

console.log(s.peek(), s.pop(), s.size); // c c 2

peek() shows c, pop() removes and returns c, and two items remain.

3. Where You Meet Stacks at Work

The call stack. Every time a function calls another function, the engine pushes a "frame" holding its variables and where to return to. When the function finishes, the frame is popped. This is why the last function called is the first to finish. It is also why infinite recursion ends with "Maximum call stack size exceeded", which you will see in the recursion chapter. When you read a stack trace in an error, you are reading this stack from top to bottom.
Undo and redo. Every editor keeps a stack of past states.
Browser back button. Pages you visited are pushed. Back pops.
Parsing. Compilers, linters, and your editor's bracket matching use a stack to track what is still open.
Depth-first search. Exploring a maze or a file tree, always following the newest path first, is a stack (explicit, or the call stack).
Expression evaluation. Calculators and spreadsheets turn (3 + 4) * 2 into steps with a stack.

4. Undo and Redo

Let's build the undo history of a text editor with two stacks. One holds the past (for undo). One holds the undone states (for redo).

state:  "Hi there"        undo stack: ["", "Hi"]     redo stack: []
undo -> "Hi"              undo stack: [""]           redo stack: ["Hi there"]
undo -> ""                undo stack: []             redo stack: ["Hi there", "Hi"]
redo -> "Hi"              undo stack: [""]           redo stack: ["Hi there"]

Rules:

A new edit pushes the current state onto the undo stack and clears the redo stack. Once you type something new, the old future no longer exists. (Try it in any editor.)
undo moves the current state to the redo stack and pops the undo stack into the current state.
redo does the reverse.

class History<T> {
  private undoStack = new Stack<T>();
  private redoStack = new Stack<T>();

  constructor(private current: T) {}

  get value(): T {
    return this.current;
  }

  set(next: T): void {
    this.undoStack.push(this.current);
    this.current = next;
    this.redoStack = new Stack<T>(); // a new edit clears redo
  }

  undo(): T {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.current);
      this.current = this.undoStack.pop()!;
    }
    return this.current;
  }

  redo(): T {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.current);
      this.current = this.redoStack.pop()!;
    }
    return this.current;
  }
}

undo and redo mirror each other, and both do nothing when there is nothing to move. Use it like this:

const h = new History("");
h.set("Hi");
h.set("Hi there");

console.log(h.undo(), h.undo(), h.redo()); // Hi (empty) Hi

The middle value is an empty string, so the output line reads Hi Hi with two spaces. A real editor stores a diff or a command instead of a full copy of the text for every step, but the two-stack idea is the same.

5. Classic Problem: Balanced Brackets

Problem: given a string containing (), [], and {}, decide whether every bracket is closed in the right order.

"{[()]}" is balanced.
"([)]" is not: the ) arrives while [ is the most recent open bracket.
"((" is not: two brackets never get closed.

The most recent unclosed opening bracket must be the next one to close. "Most recent first" is exactly a stack. The algorithm:

Go through the characters.
On an opening bracket, push it.
On a closing bracket, pop the stack. The popped item must be the matching opener, otherwise it is not balanced.
At the end the stack must be empty, otherwise some brackets are still open.

const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

function isBalanced(text: string): boolean {
  const stack = new Stack<string>();
  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.isEmpty();
}

Trace "([)]":

Char	Action	Stack
`(`	push	`(`
`[`	push	`( [`
`)`	pop gives `[`, but we need `(`	mismatch, return false

Edge cases the code already handles: a closer with nothing to pop (")" pops undefined, which never equals a bracket, so it returns false), leftover openers ("((" ends with a non-empty stack), and other characters like letters (they are ignored, so "a(b[c]d)e" is balanced).

Time is O(n) because each character is pushed and popped at most once. Space is O(n) in the worst case, such as a string of only openers.

This one problem is a common interview opener, and a real feature of tools like JSON validators and code formatters.

6. More Stack Problems: Postfix and Warmer Days

Postfix (reverse Polish) evaluation

In postfix notation the operator comes after its operands: 3 4 + means 3 + 4, and 3 4 + 2 * means (3 + 4) * 2. It needs no parentheses, and a stack evaluates it in one pass: push numbers, and on an operator pop two numbers, apply it, and push the result.

function evalRpn(tokens: string[]): number {
  const stack = new Stack<number>();
  for (const token of tokens) {
    if (["+", "-", "*", "/"].includes(token)) {
      const b = stack.pop()!; // the right operand comes off first
      const a = stack.pop()!;
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}

console.log(evalRpn(["3", "4", "+", "2", "*"])); // 14

Pay attention to the order: the first pop is the right operand b. For subtraction and division the order matters: 7 2 - must be 7 - 2, not 2 - 7.

The monotonic stack: days until a warmer temperature

Problem: for each day, how many days until a warmer one? For [73, 74, 75, 71, 69, 72, 76, 73] the answer is [1, 1, 4, 2, 1, 1, 0, 0] (0 means it never gets warmer).

The slow way checks every later day for every day: O(n squared). A stack does it in O(n). Keep a stack of indexes of days still waiting for a warmer day. When today is warmer than the day on top, that day's wait is over, so pop it and record the gap. Then push today.

function daysUntilWarmer(temps: number[]): number[] {
  const result = new Array<number>(temps.length).fill(0);
  const waiting = new Stack<number>(); // indexes, temps decreasing
  for (let i = 0; i < temps.length; i++) {
    while (!waiting.isEmpty() && temps[waiting.peek()!] < temps[i]) {
      const j = waiting.pop()!;
      result[j] = i - j;
    }
    waiting.push(i);
  }
  return result;
}

The temperatures of the days in the stack are always decreasing from bottom to top, which is why this is called a monotonic stack. There is a while inside a for, but each index is pushed once and popped once, so the total work is still O(n). That is a nice reminder: nested loops do not always mean O(n squared). Count how many times each item is touched.

7. The Queue: First In, First Out

A queue has these operations:

Operation	What it does
`enqueue(x)`	add `x` at the back
`dequeue()`	remove and return the front item
`peek()`	look at the front without removing it

Plus size and isEmpty(). All should be O(1).

enqueue(a)  enqueue(b)  enqueue(c)  dequeue() -> a
front [a]   [a b]       [a b c]     [b c] front

Can we use an array with push and shift? It works, and for small queues it is fine. But from the arrays chapter you know shift() has to move the remaining items, which is O(n) in principle. A queue of a million waiting jobs should not pay that price on every dequeue.

8. Where You Meet Queues at Work

Job queues. Sending email, resizing images, and processing payments are put in a queue and handled by workers in order. Tools like RabbitMQ, SQS, and Redis-based queues are queues at scale.
Event loop. JavaScript itself uses a queue: callbacks and resolved promises wait in line for the call stack to be free.
Print jobs, support tickets, ride requests. First come, first served.
Breadth-first search. Exploring level by level (trees and graphs chapters) uses a queue.
Buffers and streaming. Data arriving faster than it is processed waits in a queue (network packets, video frames, log lines).
Rate limiting and throttling. Sliding windows of recent requests are often kept in a queue.

9. Building a Queue Well

You already have the perfect tool. A linked list with a tail pointer adds at the end in O(1) and removes from the front in O(1), and those are exactly the two operations a queue needs:

import { LinkedList } from "./linked-list.ts";

class Queue<T> {
  private list = new LinkedList<T>();

  get size(): number {
    return this.list.size;
  }

  isEmpty(): boolean {
    return this.list.size === 0;
  }

  enqueue(value: T): void {
    this.list.append(value);
  }

  dequeue(): T | undefined {
    return this.list.removeFirst();
  }

  peek(): T | undefined {
    return this.list.head?.value;
  }
}

Using it:

const q = new Queue<string>();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");

console.log(q.dequeue(), q.peek(), q.size); // a b 2

That is why we built LinkedList with a tail in the last chapter. Note the contrast: a stack is happiest on an array (one end, no pointers), while a queue is happiest on a linked list (two ends, no shifting).

Structure	Backed by	Add	Remove	Peek
Stack	array	O(1)	O(1)	O(1)
Queue	linked list	O(1)	O(1)	O(1)
Queue	array with `shift()`	O(1)	O(n)	O(1)

10. Circular Buffers

Sometimes you want a queue with a fixed size: keep the last 100 log lines, the last 60 seconds of metrics, or the most recent 10 searches. When it is full, the oldest item is thrown away to make room. A linked list works, but a fixed array is more compact and allocates nothing after the start.

The trick is a circular buffer (or ring buffer). It uses a plain array of fixed size and treats the end as connected to the start, like the carousels you built with modular arithmetic. In Modular Arithmetic you saw that (i + 1) % length wraps an index back to 0. Here that same % operator drives the whole structure.

We keep two numbers: start (index of the oldest item) and count (how many items are stored). The next free slot is (start + count) % capacity.

capacity 3, after pushing 1, 2, 3, then 4 and 5:

push 1,2,3:  [1, 2, 3]   start=0 count=3
push 4:      [4, 2, 3]   start=1 count=3   (overwrote 1)
push 5:      [4, 5, 3]   start=2 count=3   (overwrote 2)

Reading in order from start: 3, 4, 5

class CircularBuffer<T> {
  private items: (T | undefined)[];
  private start = 0;
  private count = 0;

  constructor(readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.items = new Array(capacity);
  }

  push(value: T): T | undefined {
    const end = (this.start + this.count) % this.capacity;
    if (this.count < this.capacity) {
      this.items[end] = value;
      this.count++;
      return undefined;
    }
    const dropped = this.items[this.start]; // full: replace the oldest
    this.items[this.start] = value;
    this.start = (this.start + 1) % this.capacity;
    return dropped;
  }

  shift(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.items[this.start];
    this.items[this.start] = undefined;
    this.start = (this.start + 1) % this.capacity;
    this.count--;
    return value;
  }
}

push returns the item it threw away (or undefined if there was room), so callers can log or react to the loss. Both operations are O(1) and never move other items.

const b = new CircularBuffer<number>(3);
for (let i = 1; i <= 5; i++) b.push(i);

console.log(b.toArray().join(",")); // 3,4,5

(toArray() is in the recipe below.) The oldest items, 1 and 2, were overwritten, and what remains is the 3 most recent values, in order.

11. A Queue From Two Stacks

A famous interview question: implement a queue using only stacks. Stacks reverse order and queues keep it, so the idea is to reverse twice:

inbox receives every enqueue (push).
outbox serves every dequeue (pop).
When outbox is empty and a dequeue is requested, pour the whole inbox into the outbox, one item at a time. The pop order flips, so the oldest item ends up on top.

enqueue 1, 2, 3 -> inbox (bottom to top): 1 2 3
dequeue: outbox is empty, so pour:
  pop 3 -> push to outbox, pop 2 -> push, pop 1 -> push
  outbox (bottom to top): 3 2 1   -> pop gives 1. Correct.

class TwoStackQueue<T> {
  private inbox = new Stack<T>();
  private outbox = new Stack<T>();

  enqueue(value: T): void {
    this.inbox.push(value);
  }

  dequeue(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox.pop();
  }
}

A single dequeue can cost O(n) when it pours. But every item is poured at most once in its life, so over many operations the cost averages to O(1) per operation. This is called amortized O(1), the same word used for Array.push in the arrays chapter. Never pour while the outbox still has items, or the order breaks.

12. Recipe: stack.ts and queue.ts for algolab

Create src/stack.ts. It holds the Stack, the problems from this chapter that use it, a MinStack (see exercise 3), and the full History:

export class Stack<T> {
  private items: T[] = [];

  get size(): number {
    return this.items.length;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  // O(1) amortized
  push(value: T): void {
    this.items.push(value);
  }

  // O(1)
  pop(): T | undefined {
    return this.items.pop();
  }

  // O(1)
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  toArray(): T[] {
    return [...this.items];
  }
}

const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

export function isBalanced(text: string): boolean {
  const stack = new Stack<string>();
  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.isEmpty();
}

// Reverse Polish notation: "3 4 + 2 *" -> 14
export function evalRpn(tokens: string[]): number {
  const stack = new Stack<number>();
  for (const token of tokens) {
    if (["+", "-", "*", "/"].includes(token)) {
      const b = stack.pop()!;
      const a = stack.pop()!;
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}

// Monotonic stack: days until a warmer temperature
export function daysUntilWarmer(temps: number[]): number[] {
  const result = new Array<number>(temps.length).fill(0);
  const waiting = new Stack<number>(); // indexes, temps decreasing
  for (let i = 0; i < temps.length; i++) {
    while (!waiting.isEmpty() && temps[waiting.peek()!] < temps[i]) {
      const j = waiting.pop()!;
      result[j] = i - j;
    }
    waiting.push(i);
  }
  return result;
}

// Stack that also reports its minimum in O(1)
export class MinStack {
  private items: { value: number; min: number }[] = [];

  push(value: number): void {
    const min = this.items.length
      ? Math.min(value, this.items[this.items.length - 1].min)
      : value;
    this.items.push({ value, min });
  }

  pop(): number | undefined {
    return this.items.pop()?.value;
  }

  min(): number | undefined {
    return this.items[this.items.length - 1]?.min;
  }
}

// Undo / redo history
export class History<T> {
  private undoStack = new Stack<T>();
  private redoStack = new Stack<T>();

  constructor(private current: T) {}

  get value(): T {
    return this.current;
  }

  set(next: T): void {
    this.undoStack.push(this.current);
    this.current = next;
    this.redoStack = new Stack<T>(); // a new edit clears redo
  }

  undo(): T {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.current);
      this.current = this.undoStack.pop()!;
    }
    return this.current;
  }

  redo(): T {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.current);
      this.current = this.redoStack.pop()!;
    }
    return this.current;
  }
}

Now src/queue.ts, building on your LinkedList:

import { LinkedList } from "./linked-list.ts";
import { Stack } from "./stack.ts";

// Queue on top of the linked list: both ends are O(1).
export class Queue<T> {
  private list = new LinkedList<T>();

  get size(): number {
    return this.list.size;
  }

  isEmpty(): boolean {
    return this.list.size === 0;
  }

  enqueue(value: T): void {
    this.list.append(value);
  }

  dequeue(): T | undefined {
    return this.list.removeFirst();
  }

  peek(): T | undefined {
    return this.list.head?.value;
  }

  toArray(): T[] {
    return this.list.toArray();
  }
}

// Fixed-size ring: when full, the oldest item is overwritten.
export class CircularBuffer<T> {
  private items: (T | undefined)[];
  private start = 0;
  private count = 0;

  constructor(readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.items = new Array(capacity);
  }

  get size(): number {
    return this.count;
  }

  isFull(): boolean {
    return this.count === this.capacity;
  }

  // O(1). Returns the overwritten item, if any.
  push(value: T): T | undefined {
    const end = (this.start + this.count) % this.capacity;
    if (this.count < this.capacity) {
      this.items[end] = value;
      this.count++;
      return undefined;
    }
    const dropped = this.items[this.start];
    this.items[this.start] = value;
    this.start = (this.start + 1) % this.capacity;
    return dropped;
  }

  // O(1)
  shift(): T | undefined {
    if (this.count === 0) return undefined;
    const value = this.items[this.start];
    this.items[this.start] = undefined;
    this.start = (this.start + 1) % this.capacity;
    this.count--;
    return value;
  }

  toArray(): T[] {
    const out: T[] = [];
    for (let i = 0; i < this.count; i++) {
      out.push(this.items[(this.start + i) % this.capacity] as T);
    }
    return out;
  }
}

// Interview classic: a queue built from two stacks.
export class TwoStackQueue<T> {
  private inbox = new Stack<T>();
  private outbox = new Stack<T>();

  enqueue(value: T): void {
    this.inbox.push(value);
  }

  dequeue(): T | undefined {
    if (this.outbox.isEmpty()) {
      while (!this.inbox.isEmpty()) this.outbox.push(this.inbox.pop()!);
    }
    return this.outbox.pop();
  }

  get size(): number {
    return this.inbox.size + this.outbox.size;
  }
}

Tests for the stack, in src/stack.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { Stack, isBalanced, evalRpn, daysUntilWarmer, MinStack, History } from "./stack.ts";

test("Stack is last in, first out", () => {
  const s = new Stack<number>();
  s.push(1);
  s.push(2);
  assert.equal(s.peek(), 2);
  assert.equal(s.pop(), 2);
  assert.equal(s.pop(), 1);
  assert.equal(s.pop(), undefined);
  assert.equal(s.isEmpty(), true);
});

test("isBalanced", () => {
  assert.equal(isBalanced("{[()]}"), true);
  assert.equal(isBalanced("a(b[c]d)e"), true);
  assert.equal(isBalanced("([)]"), false);
  assert.equal(isBalanced("(("), false);
  assert.equal(isBalanced(")"), false);
  assert.equal(isBalanced(""), true);
});

test("evalRpn", () => {
  assert.equal(evalRpn(["3", "4", "+", "2", "*"]), 14);
  assert.equal(evalRpn(["10", "2", "8", "*", "+", "3", "-"]), 23);
  assert.equal(evalRpn(["7", "2", "/"]), 3);
});

test("daysUntilWarmer", () => {
  assert.deepEqual(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]);
});

test("MinStack", () => {
  const s = new MinStack();
  s.push(5);
  s.push(2);
  s.push(7);
  assert.equal(s.min(), 2);
  s.pop();
  s.pop();
  assert.equal(s.min(), 5);
});

test("History undo and redo", () => {
  const h = new History("a");
  h.set("ab");
  h.set("abc");
  assert.equal(h.undo(), "ab");
  assert.equal(h.undo(), "a");
  assert.equal(h.undo(), "a");
  assert.equal(h.redo(), "ab");
  h.set("abx");
  assert.equal(h.redo(), "abx");
});

And for the queue, in src/queue.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { Queue, CircularBuffer, TwoStackQueue } from "./queue.ts";

test("Queue is first in, first out", () => {
  const q = new Queue<string>();
  q.enqueue("a");
  q.enqueue("b");
  assert.equal(q.peek(), "a");
  assert.equal(q.dequeue(), "a");
  assert.equal(q.dequeue(), "b");
  assert.equal(q.dequeue(), undefined);
  assert.equal(q.isEmpty(), true);
});

test("CircularBuffer overwrites the oldest", () => {
  const b = new CircularBuffer<number>(3);
  [1, 2, 3].forEach((n) => b.push(n));
  assert.equal(b.push(4), 1);
  assert.equal(b.push(5), 2);
  assert.deepEqual(b.toArray(), [3, 4, 5]);
  assert.equal(b.shift(), 3);
  assert.deepEqual(b.toArray(), [4, 5]);
  b.push(6);
  b.push(7);
  assert.deepEqual(b.toArray(), [5, 6, 7]);
});

test("TwoStackQueue keeps FIFO order", () => {
  const q = new TwoStackQueue<number>();
  q.enqueue(1);
  q.enqueue(2);
  assert.equal(q.dequeue(), 1);
  q.enqueue(3);
  assert.equal(q.dequeue(), 2);
  assert.equal(q.dequeue(), 3);
  assert.equal(q.dequeue(), undefined);
});

Run everything:

npx tsx --test

All tests from this chapter and the earlier ones should pass.

A small demo.ts to see it work:

import { Stack, isBalanced, evalRpn, daysUntilWarmer, History } from "./src/stack";
import { Queue, CircularBuffer } from "./src/queue";

const s = new Stack<string>();
s.push("a");
s.push("b");
s.push("c");
console.log(s.peek(), s.pop(), s.size);
console.log(isBalanced("{[()]}"), isBalanced("([)]"), isBalanced("(("));
console.log(evalRpn(["3", "4", "+", "2", "*"]));
console.log(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]).join(" "));

const h = new History("");
h.set("Hi");
h.set("Hi there");
console.log(h.undo(), h.undo(), h.redo());

const q = new Queue<string>();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.dequeue(), q.peek(), q.size);

const ring = new CircularBuffer<number>(3);
for (let i = 1; i <= 5; i++) ring.push(i);
console.log(ring.toArray().join(","));

npx tsx demo.ts

c c 2
true false false
14
1 1 4 2 1 1 0 0
Hi  Hi
a b 2
3,4,5

13. Try It Yourself

Reverse a string. Use a Stack<string> to reverse "stack". Why does it work? Then explain why [...text].reverse().join("") is shorter, and when a stack-based approach is still the better choice (hint: think about streaming characters one by one).
Find the mistake (interview). Extend isBalanced to also return the index of the first mistake, or -1 when the text is fine. For "(a]", which index do you report?
Min stack (interview). Read the MinStack in the recipe. Why does each entry store the minimum at the time it was pushed? Push 5, 2, 7, pop twice, and trace what min() returns at every step. Then try to write a stack that also returns the maximum in O(1).
Next greater element. Given [4, 5, 2, 10, 8], produce, for each item, the next item to its right that is larger (or -1). Use the monotonic stack idea from daysUntilWarmer. The answer here is [5, 10, 10, -1, -1].
Hot potato. Players stand in a circle. Starting with the first, count k players and remove that one, then continue counting from the next. Simulate it with a Queue: dequeue and enqueue k - 1 players to rotate, then dequeue (eliminate) the next. Who is left with players ["A", "B", "C", "D", "E"] and k = 3?
Moving average (interview). Design a class MovingAverage(windowSize) with a method next(value) that returns the average of the last windowSize values. Use your CircularBuffer plus a running sum, so each call is O(1). Compare it with the sliding window technique from the arrays chapter.

Stacks and queues are tiny, but they show up inside bigger algorithms all the time. Soon you will use a stack to explore every branch of a problem, and the call stack makes that possible. In the next chapter, Recursion, a function calls itself, the call stack grows, and you learn to control it before it overflows.