Stacks & Queues

Some problems have a natural order: the last thing you did is the first thing you want to undo. Your browser's back button, an editor's undo stack, and a calculator's memory all share the same rule — last in, first out. That rule defines a stack.

Other problems demand fairness: the first task submitted should be the first task processed. A printer queue, a line at a coffee shop, and a background job scheduler all obey a different rule — first in, first out. That rule defines a queue.

Stacks and queues are not exotic data structures built from exotic parts. They are simply contracts about how items enter and leave a collection. You can build both on top of an array or a linked list; the magic is in the discipline of which end you use.

flowchart TD
  A["Push 1"] --> B["Push 2"]
  B --> C["Push 3"]
  C --> D["Pop → 3"]
  D --> E["Pop → 2"]
  style C fill:#e0900b,color:#fff
  style D fill:#e0900b,color:#fff

A stack is LIFO: the last item pushed is the first one popped.

The stack: push and pop

A stack has two main operations. Push adds an item to the top. Pop removes the item from the top. You may also peek at the top item without removing it. Because both operations happen at the same end, the most recently pushed item is always the next one popped — a pattern called LIFO, last in, first out.

A classic use is balancing brackets. You scan a string left to right, pushing every opening bracket onto the stack. When you meet a closing bracket, you pop the stack and check that the pair matches. If the stack is empty when you need a match, or if anything is left on the stack at the end, the expression is unbalanced. The stack is perfect here because the most recent opening bracket must be closed first.

When to reach for a stack

Stacks appear anywhere nested structure needs to be unwound in reverse order. Beyond bracket balancing, they power recursive function calls — the call stack is literally a stack — and depth-first tree traversal, where you push children and pop the next one to visit. Any time the last thing discovered must be the first thing processed, a stack is the natural fit.

A stack built on an array: push and pop at the same end. Press Run.

const stack = [];
stack.push("A");
stack.push("B");
stack.push("C");
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.length);

The queue: enqueue and dequeue

A queue also has two main operations, but they happen at opposite ends. Enqueue adds an item to the back. Dequeue removes an item from the front. The oldest item is always the next one out — a pattern called FIFO, first in, first out.

A naive implementation uses an array and calls push to enqueue and shift to dequeue. It works, but shift must slide every remaining element one slot to the left, making dequeue O(n). If you are processing thousands of tasks, that hidden cost adds up. A better approach is to track the front and back indices yourself, using a plain object or a linked list, so both operations run in O(1) time.

When to reach for a queue

Queues enforce fairness. In a breadth-first search, a queue ensures you explore all nodes at the current depth before moving deeper. In a multiplayer game server, a queue holds incoming commands so they execute in the order they arrived, preventing a fast client from jumping ahead of a slow one. If your system must process events in the exact order they occurred, a queue is the right abstraction.

flowchart LR
  A["Enqueue 1"] --> B["Enqueue 2"]
  B --> C["Enqueue 3"]
  C --> D["Dequeue → 1"]
  D --> E["Dequeue → 2"]
  style A fill:#3776ab,color:#fff
  style D fill:#3776ab,color:#fff

A queue is FIFO: the first item enqueued is the first one dequeued.

A naive queue with shift: dequeue works but is O(n).

const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);
console.log(queue.shift());
console.log(queue.shift());
console.log(queue.length);

A better queue with pointers

Instead of shifting the array, store items in an object and move a head pointer forward on dequeue. Keep a tail pointer for enqueue. Both operations become simple assignments that run in constant time. The items are not physically removed from the object — they are simply abandoned beyond the head pointer — but in JavaScript the garbage collector handles cleanup when the object is no longer referenced.

If you need to reuse the same object without growing it forever, you can wrap the indices around in a circle, creating a circular buffer. That pattern is common in embedded systems and streaming audio, where memory is fixed and predictable.

flowchart TD
  A["Array shift"] --> B["Slide every element left"]
  B --> C["O(n) dequeue"]
  D["Head pointer"] --> E["Move pointer forward"]
  E --> F["O(1) dequeue"]
  style C fill:#b91c1c,color:#fff
  style F fill:#1e7f3d,color:#fff

Pointer-based dequeue is O(1): move head forward instead of sliding elements.

An efficient queue using head and tail pointers on a plain object.

class FastQueue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(x) {
    this.items[this.tail++] = x;
  }
  dequeue() {
    if (this.head === this.tail) return undefined;
    const x = this.items[this.head];
    delete this.items[this.head++];
    return x;
  }
}
const q = new FastQueue();
q.enqueue(10);
q.enqueue(20);
console.log(q.dequeue());
console.log(q.dequeue());

Exercise

What does this print? Track the pushes and pops carefully.

const s = [];
s.push(1);
s.push(2);
console.log(s.pop());
s.push(3);
console.log(s.pop());

Your prediction — what does this print?

Exercise

Write isBalanced(str) that returns true if every opening bracket ( has a matching closing bracket ) in the correct order. Use a stack: push on (, pop on ). Return false if a ) appears when the stack is empty, or if any ( remain after the scan.

function isBalanced(str) {
  // use a stack to track brackets
}

function isBalanced(str) {
  const stack = [];
  for (const ch of str) {
    if (ch === '(') {
      stack.push(ch);
    } else if (ch === ')') {
      if (stack.length === 0) return false;
      stack.pop();
    }
  }
  return stack.length === 0;
}

Exercise

This queue implementation is meant to be efficient, but dequeue always returns undefined. Fix it so it returns items in FIFO order.

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(x) {
    this.items[this.tail] = x;
    this.tail++;
  }
  dequeue() {
    if (this.head === this.tail) return undefined;
    const x = this.items[this.tail];
    this.head++;
    return x;
  }
}

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(x) {
    this.items[this.tail] = x;
    this.tail++;
  }
  dequeue() {
    if (this.head === this.tail) return undefined;
    const x = this.items[this.head];
    this.head++;
    return x;
  }
}

Exercise

You are designing an undo feature for a text editor. Which abstract data structure is the natural choice?

Exercise

Write reverseString(str) that returns the reversed string using a stack. Push each character onto an array, then pop them all off to build the reversed result.

function reverseString(str) {
  // use a stack to reverse
}

function reverseString(str) {
  const stack = [];
  for (const ch of str) {
    stack.push(ch);
  }
  let result = '';
  while (stack.length > 0) {
    result += stack.pop();
  }
  return result;
}

Recap

A stack is LIFO: push and pop at the same end.
A queue is FIFO: enqueue at the back, dequeue at the front.
shift on an array is O(n); a pointer-based queue gives O(1) dequeue.
Stacks balance brackets and undo histories; queues schedule tasks fairly.
The abstract contract matters more than the underlying storage.

Next you will implement the classic searching and sorting algorithms, where the choice of data structure and the analysis of loops directly determine the Big-O of your solution.

The stack: push and pop

When to reach for a stack

The queue: enqueue and dequeue

When to reach for a queue

A better queue with pointers

Recap

Checkpoint quiz

Go deeper — technical resources