Stacks y Queues: cuando el orden de acceso es el algoritmo

Arrays y linked lists guardan datos. Stacks y queues imponen una restricción sobre cómo accedés a esos datos. Esa restricción no es una limitación — es la herramienta.

Cuando elegís un stack o una queue, estás diciéndole al código (y a la persona que lo lee después) algo específico sobre el orden en que los elementos se van a procesar. El tipo de dato comunica la intención.

Stack: último en entrar, primero en salir

Un stack es una colección donde solo podés interactuar con el elemento más reciente. El último que agregaste es el primero que podés sacar. Se llama LIFO — Last In, First Out.

Las operaciones son tres:

• push(x) — agregar un elemento al tope
• pop() — sacar y devolver el elemento del tope
• peek() — ver el elemento del tope sin sacarlo

Todas son O(1). El stack no necesita saber dónde está ningún otro elemento — solo el tope.

Implementación

La implementación más directa usa un array. push y pop al final del array son O(1), así que no hay costo adicional.

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
  }
}

En la mayoría de los lenguajes ya tenés esto sin necesidad de implementarlo: en JavaScript podés usar un array directamente con .push() y .pop(). La clase de arriba existe para hacer explícita la intención — si declarás un Stack, el código dice que solo vas a usar el tope.

El call stack: un stack que ya conocés

El call stack de JavaScript es literalmente un stack. Cada vez que llamás una función, se apila un frame. Cuando la función retorna, ese frame se desapila.

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

function b() {
  c()
}

function a() {
  b()
}

a()

// El stack en cada momento:
// → a()
// → a() → b()
// → a() → b() → c()
// → a() → b()   (c retornó)
// → a()          (b retornó)
// → vacío        (a retornó)

Cuando tirás un error y ves el stack trace, estás viendo exactamente ese stack en el momento del error — las funciones apiladas desde la raíz hasta donde se rompió todo. Los errores de "Maximum call stack size exceeded" son stacks que crecieron demasiado por recursión sin caso base.

Problema clásico: paréntesis balanceados

Un problema que se vuelve trivial con un stack: dado un string con paréntesis, corchetes y llaves, verificar si están correctamente balanceados.

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

  for (const char of str) {
    if (!cierres.has(char)) {
      stack.push(char)           // es un abridor, lo apilamos
    } else {
      if (stack.pop() !== pares[char]) return false  // el tope debe ser el par correcto
    }
  }

  return stack.length === 0    // si quedaron abridores sin cerrar, false
}

estaBalanceado('({[]})')  // true
estaBalanceado('({[}])')  // false — el ] cierra el [ pero había un { sin cerrar antes
estaBalanceado('((())')   // false — falta un cierre

Sin el stack, este problema requiere lógica contorsionada. Con el stack, el código sigue exactamente el razonamiento natural: "cuando encuentro un cierre, el último abridor que vi tiene que ser su par".

Otros usos reales

Deshacer y rehacer (Ctrl+Z / Ctrl+Y). Cada acción se apila. Deshacer hace pop. Rehacer es un segundo stack donde van a parar las acciones deshechas.

Historial del navegador. Las páginas visitadas son un stack. El botón Atrás hace pop. Navegar a una nueva página limpia el stack de "adelante".

Recorrido en profundidad (DFS). Los grafos y árboles se recorren en profundidad usando un stack — explora todo un camino antes de volver atrás. Los veremos en el capítulo de grafos.

Evaluación de expresiones. Compiladores e intérpretes usan stacks para evaluar 3 + 4 * 2 respetando precedencia de operadores, y para convertir expresiones infijas a notación postfija.

Queue: primero en entrar, primero en salir

Una queue es una colección donde el primer elemento que agregaste es el primero que podés sacar. FIFO — First In, First Out.

Las operaciones:

• enqueue(x) — agregar un elemento al final
• dequeue() — sacar y devolver el elemento del frente
• peek() — ver el elemento del frente sin sacarlo

Todas deben ser O(1). Y ahí está la trampa de implementación.

Por qué el array naïve no funciona

Si usás un array y hacés push al final y shift al frente, el enqueue es O(1) pero el dequeue es O(n) — shift desplaza todos los elementos una posición hacia adelante.

const queue = []
queue.push('a')     // O(1) ✓
queue.push('b')
queue.shift()       // O(n) ✗ — mueve todos los elementos

Para queues grandes, ese O(n) en cada dequeue es un problema real.

Implementación correcta: linked list

Una queue con linked list mantiene punteros al frente y al final. Enqueue agrega al final (O(1)), dequeue saca del frente (O(1)). Sin desplazamiento de elementos.

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
  }
}

La alternativa de alta performance es un circular buffer — un array fijo donde los índices de frente y final avanzan circularmente sin mover datos. Es la implementación que usan las queues en C++ y Java internamente cuando el tamaño es conocido.

La queue del event loop

La Task Queue y la Microtask Queue del event loop de JavaScript son literalmente queues. Los callbacks que llegaron primero se ejecutan primero. setTimeout(() => ..., 0) encola el callback al final de la queue de macrotasks. El event loop hace dequeue uno por uno cuando el call stack está vacío.

La elección de FIFO no es arbitraria: garantiza que los eventos se procesen en el orden en que ocurrieron. Si fuera un stack, el callback más reciente se ejecutaría primero y los anteriores podrían quedar esperando indefinidamente.

Problema clásico: recorrido por niveles de un árbol

El recorrido en amplitud (BFS) de un árbol procesa todos los nodos de un nivel antes de pasar al siguiente. Una queue hace esto de forma natural.

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
}

// Para el árbol:
//       1
//      / \
//     2   3
//    / \
//   4   5
//
// Resultado: [1, 2, 3, 4, 5]

Cada nodo entra a la queue en orden de nivel. Como FIFO garantiza que el primero en entrar es el primero en procesarse, los nodos de un nivel se procesan completos antes de que empiecen los del siguiente.

Con un stack en lugar de una queue, esto haría DFS en lugar de BFS — procesaría todo el subárbol izquierdo antes de tocar el derecho. La estructura determina el algoritmo.

Otros usos reales

Colas de tareas en servidores. Un servidor web recibe requests y los encola. Los workers los procesan en orden de llegada. RabbitMQ, SQS, y Kafka son sistemas enteros construidos sobre este concepto.

Rate limiting. Para limitar a 100 requests por segundo, encolás los requests con timestamp y descartás los que llegan si la queue tiene 100 ítems del último segundo.

Impresoras y sistemas de spooling. Los trabajos de impresión van a una queue. El que llegó primero, se imprime primero.

Simulaciones y sistemas de eventos discretos. Sistemas que modelan el tiempo (simulaciones de tráfico, colas bancarias) usan priority queues para procesar eventos en orden de tiempo de ocurrencia.

Variantes que vale la pena conocer

Deque (Double-Ended Queue)

Un deque permite agregar y sacar elementos por ambos extremos. Es la generalización de stack y queue — podés usarlo como cualquiera de los dos, o como los dos a la vez.

// Con el Deque de JavaScript (simulado con array)
const deque = []
deque.push('a')      // agregar al final
deque.unshift('z')   // agregar al frente
deque.pop()          // sacar del final
deque.shift()        // sacar del frente

Casos de uso: ventanas deslizantes (sliding window), palíndromos, el historial de navegación completo (adelante y atrás).

Priority Queue

Una priority queue no es FIFO — cada elemento tiene una prioridad, y el que se saca primero es el de mayor prioridad, independientemente del orden de llegada.

Internamente se implementa con un heap (árbol binario parcialmente ordenado), que garantiza acceso al elemento de máxima prioridad en O(1) y extracción en O(log n).

enqueue(valor, prioridad)  → O(log n)
dequeue()                  → O(log n) — saca el de mayor prioridad
peek()                     → O(1)

Casos de uso: algoritmos de caminos mínimos (Dijkstra), sistemas de scheduling de tareas por urgencia, motores de búsqueda que priorizan resultados por relevancia. La cubrimos en el capítulo de grafos.

Monotonic Stack

Un stack con una invariante adicional: los elementos siempre están en orden (creciente o decreciente). Cuando querés agregar un elemento que viola el orden, hacés pop hasta que la invariante se cumpla.

// Stack monótono creciente: encuentra el "siguiente mayor" para cada elemento
function siguienteMayor(arr) {
  const resultado = new Array(arr.length).fill(-1)
  const stack = [] // guarda índices

  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]
// El siguiente mayor de 2 es 5, de 1 es 5, de 5 es 6, de 3 es 6, de 6 no hay

Este patrón resuelve en O(n) problemas que parecen requerir O(n²) — "para cada elemento, encontrá el primer elemento mayor a la derecha". Es uno de los patrones más frecuentes en entrevistas técnicas y en problemas de procesamiento de señales.

La tabla de operaciones

Cuándo usar cada uno

La pregunta no es "¿cuál es más rápido?" — las dos tienen O(1) en todas sus operaciones. La pregunta es "¿en qué orden necesito procesar los elementos?".

Usá un Stack cuando:

• Necesitás procesar en orden inverso al que llegaron
• El procesamiento de un elemento puede generar más trabajo que tiene que procesarse antes de continuar (DFS iterativo: recursión reescrita con un stack explícito)
• Necesitás "deshacer" — volver al estado anterior
• Estás parseando estructuras anidadas (HTML, JSON, expresiones)

Usá una Queue cuando:

• El orden de llegada determina el orden de procesamiento
• Estás distribuyendo trabajo entre múltiples consumidores
• Necesitás explorar nivel por nivel (BFS)
• El productor y el consumidor trabajan a velocidades distintas y necesitás un buffer

La regla de oro: si el problema implica "volvé hacia atrás" o "procesá lo más reciente primero", es un stack. Si implica "procesá en orden de llegada" o "explorá en amplitud", es una queue.