Pilas y colas como reglas de acceso

Una pila y una cola pueden guardar exactamente los mismos valores. Lo que cambia es quién sale primero. Esa única regla alcanza para producir algoritmos distintos, desde deshacer una acción hasta recorrer un grafo por niveles.

La pila: último en entrar, primero en salir

Una pila usa la política LIFO: último en entrar, primero en salir. Sus operaciones centrales son push, que agrega arriba; pop, que retira el elemento superior; y peek, que lo mira sin retirarlo.

Con un arreglo dinámico, agregar y quitar al final cuesta $O(1)$ amortizado. No hace falta exponer índices ni permitir inserciones arbitrarias: la interfaz limitada es justamente la que garantiza el orden.

Cuándo lo más reciente va primero

La pila aparece cuando lo más reciente debe resolverse primero. Un editor apila acciones para deshacerlas en orden inverso. Un parser apila delimitadores abiertos. Un recorrido DFS apila caminos pendientes. La propia ejecución de funciones usa una pila de llamadas.

La pregunta para reconocerla es: si llega una tarea nueva, ¿debe completarse antes que las anteriores? Si la respuesta es sí, el comportamiento es LIFO.

La cola: respetar el orden de llegada

Una cola usa FIFO: primero en entrar, primero en salir. enqueue agrega al final, dequeue retira desde el frente y front consulta el próximo elemento.

Es la política natural para trabajos que deben respetar orden de llegada: impresiones, mensajes, turnos y eventos pendientes. También es la base de BFS, que visita primero todos los nodos a distancia uno, después los de distancia dos y así sucesivamente.

Implementarla mal la vuelve cuadrática

Usar push para encolar y shift para desencolar parece cómodo, pero retirar el primer elemento de un arreglo suele desplazar todos los restantes y cuesta $O(n)$.

Una cola eficiente puede usar una lista enlazada con referencias a ambos extremos o un arreglo con índices de cabeza y cola. Así, encolar y desencolar cuestan $O(1)$. La estructura interna importa aunque la interfaz pública sea la misma.

La cola como frontera del recorrido

En BFS, la cola mantiene la frontera del recorrido. Sacamos un nodo, visitamos sus vecinos no vistos y los agregamos al final. Como los anteriores salen primero, la exploración respeta distancias crecientes en grafos sin pesos.

Cambiar esa cola por una pila produce DFS: en vez de expandir el nivel actual, profundiza por el camino agregado más recientemente. Una política de extracción distinta cambia el orden y también las propiedades que puede garantizar el algoritmo.

Una cola sin límite es un problema

En sistemas reales, una cola no debería crecer sin límite. Si los productores agregan más rápido de lo que los consumidores procesan, aumenta la memoria y también el tiempo de espera. Hace falta definir capacidad y una política: rechazar, bloquear, descartar o aplicar presión hacia atrás.

La estructura de datos resuelve el orden; no resuelve por sí sola la sobrecarga, la prioridad ni la persistencia ante una caída.

Las dos, escritas

Una pila sobre un arreglo dinámico es casi nada de código, porque el arreglo ya hace lo difícil: agregar y quitar al final cuesta $O(1)$ amortizado.

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

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

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

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

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

Lo importante de esa clase no es lo que tiene: es lo que no tiene. No hay acceso por índice, no hay inserción en el medio, no hay recorrido. Esa ausencia es la que garantiza que nadie pueda romper el orden LIFO desde afuera, y es la diferencia entre una pila y un arreglo al que le decimos pila.

La cola es donde aparece el problema. La versión obvia funciona y es lenta:

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

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

  dequeue(): T | undefined {
    return this.items.shift(); // O(n): desplaza todo lo que queda
  }
}

La cola con dos índices sobre un arreglo de tamaño fijo resuelve eso: en vez de mover los datos, se mueve la idea de dónde empieza.

class RingQueue<T> {
  private readonly items: Array<T | undefined>;
  private head = 0;
  private tail = 0;
  private count = 0;

  constructor(private readonly capacity: number) {
    this.items = new Array<T | undefined>(capacity);
  }

  enqueue(item: T): boolean {
    if (this.count === this.capacity) return false; // llena: la política la decide quien llama
    this.items[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    this.count += 1;
    return true;
  }

  dequeue(): T | undefined {
    if (this.count === 0) return undefined;
    const item = this.items[this.head];
    this.items[this.head] = undefined; // soltar la referencia, si no el recolector no la libera
    this.head = (this.head + 1) % this.capacity;
    this.count -= 1;
    return item;
  }
}

Las dos operaciones son $O(1)$ reales, sin amortizar, y el % capacity es todo el truco: el arreglo se recorre en círculo y los índices vuelven al principio al llegar al final. La variable count no es redundante con head y tail: sin ella, una cola llena y una cola vacía se ven exactamente igual, porque en los dos casos los dos índices coinciden.

Cuándo cada una, y qué se decide aparte

Cierre

Pilas y colas son contratos de acceso. LIFO prioriza lo reciente; FIFO conserva el orden de llegada. Elegir una obliga al algoritmo a declarar qué trabajo sale después y permite implementar esa decisión con operaciones constantes.