Overview#

Stacks and queues are both restricted linear structures. They do not emphasize “access at arbitrary positions”; instead, they emphasize “the order in which elements enter and leave.”

• Stack: last in, first out, like a stack of plates;
• Queue: first in, first out, like waiting in line.

These two structures may seem simple, but they are the foundation of recursion, expression parsing, BFS, task scheduling, monotonic stacks, and monotonic queues.

Prerequisites

• LIFO / FIFO: stacks are last in, first out; queues are first in, first out
• Array implementation: pay attention to the cost of push/pop and shift/unshift
• Monotonic structures: use a stack or queue to maintain an ordered candidate set

Problem Definition#

Stacks and queues solve the problem of “order control.”

If a problem cares about “the most recently added element,” you usually think of a stack; if a problem cares about “the earliest waiting element,” you usually think of a queue.

Core Principles: Step-by-Step Illustration#

1
push 1 -> [1]
2
push 2 -> [1, 2]
3
pop    -> [1], returns 2

1
enqueue 1 -> [1]
2
enqueue 2 -> [1, 2]
3
dequeue   -> [2], returns 1

1
Keep from largest to smallest:
2
Enqueue 3: [3]
3
Enqueue 1: [3, 1]
4
Enqueue 2: [3, 2]  // 1 is removed

Basic Operations and Complexity#

“Amortized O(1)” means: a single operation may pop multiple elements, but each element is popped only once over its entire lifetime.

TypeScript Implementation#

1
class Stack<T> {
2
  private readonly items: T[] = [];
3

4
  push(value: T): void {
5
    this.items.push(value);
6
  }
7

8
  pop(): T | undefined {
9
    return this.items.pop();
10
  }
11

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

16
  get size(): number {
17
    return this.items.length;
18
  }
19
}

1
class Queue<T> {
2
  private readonly items: T[] = [];
3
  private head = 0;
4

5
  enqueue(value: T): void {
6
    this.items.push(value);
7
  }
8

9
  dequeue(): T | undefined {
10
    if (this.head >= this.items.length) return undefined;
11

12
    const value = this.items[this.head];
13
    this.head++;
14

15
    if (this.head > 32 && this.head * 2 > this.items.length) {
16
      this.items.splice(0, this.head);
17
      this.head = 0;
18
    }
19

20
    return value;
21
  }
22

23
  get size(): number {
24
    return this.items.length - this.head;
25
  }
26
}

1
function nextGreater(nums: number[]): number[] {
2
  const result = Array(nums.length).fill(-1);
3
  const stack: number[] = [];
4

5
  for (let i = 0; i < nums.length; i++) {
6
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
7
      const index = stack.pop()!;
8
      result[index] = nums[i];
9
    }
10

11
    stack.push(i);
12
  }
13

14
  return result;
15
}

Engineering Optimization: Avoid Misusing Array APIs#

In JavaScript, operations at the end of an array are fast:

1
arr.push(value);
2
arr.pop();

But operations at the head will shift elements:

1
arr.shift();
2
arr.unshift(value);

If the queue size is small, using shift directly is acceptable; if the queue is on a hot path, you should use a head pointer, a circular array, or a deque implementation.

Applications and Limitations#

Summary#

• A stack is last in, first out; a queue is first in, first out.
• Their value lies in controlling processing order, not random access.
• Queue implementations should avoid O(n) shifting caused by frequent deletion at the head.
• Monotonic stacks and monotonic queues optimize problems to linear time by deleting invalid candidates.