Stacks and queues: when access order is the algorithm

Arrays and linked lists store data. Stacks and queues impose a constraint on how you access that data. The constraint is not a limitation — it is the tool.

When you pick a stack or a queue, you are telling the code (and whoever reads it later) something specific about the order in which elements will be processed. The data type communicates the intent.

Stack: last in, first out

A stack is a collection where you can only interact with the most recent element. The last one you added is the first one you can take out. It is called LIFO — Last In, First Out.

There are three operations:

• push(x) — add an element to the top
• pop() — remove and return the top element
• peek() — look at the top element without removing it

All of them are O(1). The stack never needs to know where any other element is — only the top.

Implementation

The most direct implementation uses an array. push and pop at the end of an array are O(1), so there is no extra cost.

class Stack {
  #items = []

  push(value) {
    this.#items.push(value)
  }

  pop() {
    if (this.isEmpty()) throw new Error('Stack vacío')
    return this.#items.pop()
  }

  peek() {
    if (this.isEmpty()) throw new Error('Stack vacío')
    return this.#items[this.#items.length - 1]
  }

  isEmpty() {
    return this.#items.length === 0
  }

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

Most languages give you this without any implementation work: in JavaScript you can use an array directly with .push() and .pop(). The class above exists to make the intent explicit — if you declare a Stack, the code says you are only going to touch the top.

The call stack: a stack you already know

JavaScript's call stack is literally a stack. Every time you call a function, a frame is pushed. When the function returns, that frame is popped.

function c() {
  console.log('c ejecutando')
}

function b() {
  c()
}

function a() {
  b()
}

a()

// The stack at each moment:
// → a()
// → a() → b()
// → a() → b() → c()
// → a() → b()   (c returned)
// → a()          (b returned)
// → empty        (a returned)

When you throw an error and see the stack trace, you are looking at exactly that stack at the moment of the error — the functions piled up from the root down to where everything broke. "Maximum call stack size exceeded" errors are stacks that grew too far from recursion without a base case.

Classic problem: balanced parentheses

A problem that becomes trivial with a stack: given a string of parentheses, brackets, and braces, check whether they are correctly balanced.

function estaBalanceado(str) {
  const stack = []
  const pares = { ')': '(', ']': '[', '}': '{' }
  const cierres = new Set([')', ']', '}'])

  for (const char of str) {
    if (!cierres.has(char)) {
      stack.push(char)           // it's an opener, push it
    } else {
      if (stack.pop() !== pares[char]) return false  // the top must be the matching pair
    }
  }

  return stack.length === 0    // if openers were left unclosed, false
}

estaBalanceado('({[]})')  // true
estaBalanceado('({[}])')  // false — the ] closes the [ but there was an unclosed { before it
estaBalanceado('((())')   // false — a closer is missing

Without a stack, this problem needs contorted logic. With one, the code follows the natural reasoning exactly: "when I hit a closer, the last opener I saw has to be its match".

Other real-world uses

Undo and redo (Ctrl+Z / Ctrl+Y). Every action gets pushed. Undo pops. Redo is a second stack where undone actions end up.

Browser history. The pages you visited are a stack. The Back button pops. Navigating to a new page clears the "forward" stack.

Depth-first traversal (DFS). Graphs and trees are traversed depth-first using a stack — it explores an entire path before backtracking. We'll get to them in the graphs chapter.

Expression evaluation. Compilers and interpreters use stacks to evaluate 3 + 4 * 2 respecting operator precedence, and to convert infix expressions to postfix notation.

Queue: first in, first out

A queue is a collection where the first element you added is the first one you can take out. FIFO — First In, First Out.

The operations:

• enqueue(x) — add an element at the back
• dequeue() — remove and return the front element
• peek() — look at the front element without removing it

All of them must be O(1). And that's where the implementation trap is.

Why the naive array doesn't work

If you use an array and push at the end and shift at the front, the enqueue is O(1) but the dequeue is O(n) — shift moves every element one position forward.

const queue = []
queue.push('a')     // O(1) ✓
queue.push('b')
queue.shift()       // O(n) ✗ — moves every element

For large queues, that O(n) on every dequeue is a real problem.

The correct implementation: linked list

A queue backed by a linked list keeps pointers to the front and the back. Enqueue adds at the back (O(1)), dequeue takes from the front (O(1)). No shifting of elements.

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

class Queue {
  #head = null
  #tail = null
  #size = 0

  enqueue(value) {
    const node = new Node(value)
    if (this.#tail) {
      this.#tail.next = node
    }
    this.#tail = node
    if (!this.#head) {
      this.#head = node
    }
    this.#size++
  }

  dequeue() {
    if (this.isEmpty()) throw new Error('Queue vacía')
    const value = this.#head.value
    this.#head = this.#head.next
    if (!this.#head) this.#tail = null
    this.#size--
    return value
  }

  peek() {
    if (this.isEmpty()) throw new Error('Queue vacía')
    return this.#head.value
  }

  isEmpty() {
    return this.#size === 0
  }

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

The high-performance alternative is a circular buffer — a fixed array where the front and back indices advance in a circle without moving any data. It is the implementation queues in C++ and Java use internally when the size is known.

The event loop queue

The Task Queue and the Microtask Queue in JavaScript's event loop are literally queues. The callbacks that arrived first run first. setTimeout(() => ..., 0) enqueues the callback at the back of the macrotask queue. The event loop dequeues one at a time whenever the call stack is empty.

The choice of FIFO is not arbitrary: it guarantees events are processed in the order they happened. If it were a stack, the most recent callback would run first and the earlier ones could wait forever.

Classic problem: level-order traversal of a tree

Breadth-first traversal (BFS) of a tree processes every node on one level before moving to the next. A queue does this naturally.

function bfs(root) {
  if (!root) return []

  const queue = new Queue()
  const resultado = []

  queue.enqueue(root)

  while (!queue.isEmpty()) {
    const nodo = queue.dequeue()
    resultado.push(nodo.value)

    if (nodo.left)  queue.enqueue(nodo.left)
    if (nodo.right) queue.enqueue(nodo.right)
  }

  return resultado
}

// For the tree:
//       1
//      / \
//     2   3
//    / \
//   4   5
//
// Result: [1, 2, 3, 4, 5]

Each node enters the queue in level order. Because FIFO guarantees the first in is the first processed, one level finishes completely before the next one starts.

With a stack instead of a queue, this would do DFS instead of BFS — it would process the entire left subtree before touching the right one. The structure determines the algorithm.

Other real-world uses

Task queues in servers. A web server receives requests and enqueues them. Workers process them in arrival order. RabbitMQ, SQS, and Kafka are entire systems built on this concept.

Rate limiting. To cap at 100 requests per second, you enqueue requests with a timestamp and drop the incoming ones when the queue already holds 100 items from the last second.

Printers and spooling systems. Print jobs go into a queue. Whoever got there first prints first.

Simulations and discrete event systems. Systems that model time (traffic simulations, bank lines) use priority queues to process events in order of occurrence time.

Variants worth knowing

Deque (double-ended queue)

A deque lets you add and remove elements at both ends. It is the generalization of stack and queue — you can use it as either one, or as both at once.

// Using a deque in JavaScript (simulated with an array)
const deque = []
deque.push('a')      // add at the back
deque.unshift('z')   // add at the front
deque.pop()          // remove from the back
deque.shift()        // remove from the front

Use cases: sliding windows, palindromes, full browser history (forward and back).

Priority queue

A priority queue is not FIFO — every element carries a priority, and the one that comes out first is the highest-priority one, regardless of arrival order.

Internally it is implemented with a heap (a partially ordered binary tree), which guarantees access to the highest-priority element in O(1) and extraction in O(log n).

enqueue(valor, prioridad)  → O(log n)
dequeue()                  → O(log n) — takes the highest priority
peek()                     → O(1)

Use cases: shortest-path algorithms (Dijkstra), task scheduling systems ordered by urgency, search engines ranking results by relevance. We cover it in the graphs chapter.

Monotonic stack

A stack with one extra invariant: the elements are always in order (increasing or decreasing). When you want to add an element that violates the order, you pop until the invariant holds again.

// Monotonic increasing stack: finds the "next greater" for each element
function siguienteMayor(arr) {
  const resultado = new Array(arr.length).fill(-1)
  const stack = [] // stores indices

  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
      resultado[stack.pop()] = arr[i]
    }
    stack.push(i)
  }

  return resultado
}

siguienteMayor([2, 1, 5, 3, 6])
// → [5, 5, 6, 6, -1]
// The next greater of 2 is 5, of 1 is 5, of 5 is 6, of 3 is 6, and 6 has none

This pattern solves in O(n) problems that look like they need O(n²) — "for each element, find the first greater element to its right". It is one of the most frequent patterns in technical interviews and in signal processing problems.

The operations table

When to use which

The question is not "which one is faster?" — both are O(1) on every operation. The question is "in what order do I need to process the elements?".

Use a stack when:

• You need to process in the reverse of arrival order
• Processing one element can generate more work that has to be handled before continuing (iterative DFS: recursion rewritten with an explicit stack)
• You need to "undo" — go back to the previous state
• You are parsing nested structures (HTML, JSON, expressions)

Use a queue when:

• Arrival order determines processing order
• You are distributing work across multiple consumers
• You need to explore level by level (BFS)
• The producer and the consumer run at different speeds and you need a buffer

The rule of thumb: if the problem involves "go back" or "handle the most recent first", it's a stack. If it involves "process in arrival order" or "explore breadth-first", it's a queue.