TAD Pila y TAD Cola: Estructuras Lineales

En la lección anterior construiste una lista que hace de todo: insertar donde sea, borrar donde sea, leer donde sea.

Ahora vamos a hacer lo contrario: quitar poderes. Una pila y una cola son listas a las que les prohibimos casi todo. Solo se puede tocar un extremo.

Y esa restricción, que suena a limitación, es exactamente lo que las hace valiosas por dos razones:

1. Expresan intención. Si un método recibe una Pila, ya sabés que el orden importa y que solo se toca la punta. Con una Lista genérica no sabés nada.
2. Garantizan velocidad. Como solo se opera en los extremos, todas las operaciones son O(1). Siempre. Sin excepciones ni casos raros.

1. La Pila (LIFO): el último en entrar es el primero en salir

Pensá en una pila de platos: apilás arriba y sacás de arriba. Para llegar al de abajo tenés que sacar todos los de encima.

Las operaciones son solo cuatro:

Implementación sobre nodos

Acá se ve por qué la lección anterior importaba: una pila es exactamente una lista enlazada donde solo usás agregarAlInicio y eliminarPrimero. Las dos operaciones O(1) de la lista enlazada.

public class Pila<T> {
    private Nodo<T> tope;     // es la "cabeza" de la lección anterior, con otro nombre
    private int tamanio;

    public void push(T dato) {
        Nodo<T> nuevo = new Nodo<>(dato);
        nuevo.siguiente = tope;    // el mismo baile de referencias de siempre
        tope = nuevo;
        tamanio++;
    }

    public T pop() {
        if (estaVacia()) {
            throw new NoSuchElementException("La pila está vacía");
        }
        T dato = tope.dato;
        tope = tope.siguiente;     // el nodo viejo queda sin referencias: se lo lleva el GC
        tamanio--;
        return dato;
    }

    public T peek() {
        if (estaVacia()) {
            throw new NoSuchElementException("La pila está vacía");
        }
        return tope.dato;          // mira, no toca
    }

    public boolean estaVacia() { return tope == null; }
    public int tamanio() { return tamanio; }
}

Fijate que no hay ningún bucle. Ninguna operación recorre nada. Por eso todas son O(1).

Lanzar una excepción al hacer pop() sobre una pila vacía es la decisión correcta: sacar de una pila vacía es un error de uso del programador, no una condición esperable. Es RuntimeException, tal cual lo discutimos en la lección Manejo de Excepciones y Robustez.

2. La Cola (FIFO): el primero en entrar es el primero en salir

Una fila del banco. Se entra por atrás, se atiende por adelante, y nadie se cuela.

public class Cola<T> {
    private Nodo<T> frente;   // por acá se sale
    private Nodo<T> fondo;    // por acá se entra
    private int tamanio;

    public void enqueue(T dato) {
        Nodo<T> nuevo = new Nodo<>(dato);
        if (estaVacia()) {
            frente = nuevo;
            fondo = nuevo;        // con un solo elemento, ambos apuntan al mismo nodo
        } else {
            fondo.siguiente = nuevo;   // engancho al final
            fondo = nuevo;             // y muevo el fondo
        }
        tamanio++;
    }

    public T dequeue() {
        if (estaVacia()) {
            throw new NoSuchElementException("La cola está vacía");
        }
        T dato = frente.dato;
        frente = frente.siguiente;
        if (frente == null) {
            fondo = null;         // ← el caso que casi todos olvidan
        }
        tamanio--;
        return dato;
    }

    public T peek() {
        if (estaVacia()) throw new NoSuchElementException("La cola está vacía");
        return frente.dato;
    }

    public boolean estaVacia() { return frente == null; }
}

Ese if (frente == null) fondo = null; es el error clásico de esta estructura. Si sacás el último elemento y no limpiás fondo, queda apuntando a un nodo que ya no pertenece a la cola. El próximo enqueue lo engancha ahí y los datos aparecen en un lugar fantasma. Compila, corre, y da resultados incorrectos.

3. La cola circular: por qué existe el operador %

Si implementás la cola sobre un arreglo en lugar de nodos, aparece un problema que no es obvio.

public class ColaCircular<T> {
    private final Object[] datos;
    private int frente = 0;
    private int cantidad = 0;
    private final int capacidad;

    public ColaCircular(int capacidad) {
        this.capacidad = capacidad;
        this.datos = new Object[capacidad];
    }

    public void enqueue(T dato) {
        if (cantidad == capacidad) {
            throw new IllegalStateException("La cola está llena");
        }
        int fondo = (frente + cantidad) % capacidad;   // ← el módulo hace la magia
        datos[fondo] = dato;
        cantidad++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (cantidad == 0) {
            throw new NoSuchElementException("La cola está vacía");
        }
        T dato = (T) datos[frente];
        datos[frente] = null;                     // liberamos la referencia para el GC
        frente = (frente + 1) % capacidad;        // ← y acá también
        cantidad--;
        return dato;
    }
}

Este patrón —un arreglo de tamaño fijo con dos índices que dan la vuelta— se llama buffer circular, y está en todos lados: en los drivers de audio, en los buffers de red, en los sistemas de logging. Cuando lo veas en el mundo real, vas a saber exactamente qué es.

4. Dónde se usan de verdad

Pilas:

• La pila de llamadas de la JVM. Cada llamada a un método apila un stack frame; cada return lo desapila. El StackOverflowError de una recursión infinita es literalmente esta pila desbordándose. Y el stack trace de la lección Manejo de Excepciones y Robustez es esa pila, impresa.
• Deshacer (Ctrl+Z). Cada acción se apila; deshacer es un pop.
• El botón “atrás” del navegador.
• Evaluación de expresiones y verificación de sintaxis, que es el ejercicio de esta lección.

Colas:

• Cola de impresión, cola de tareas, cola de mensajes.
• Recorrido BFS de grafos y árboles, que vas a ver en las lecciones TAD Árbol: Recorridos y Árbol Binario de Búsqueda y Grafos: Matriz, Lista de Adyacencia, BFS, DFS y Dijkstra.
• Productor-consumidor entre hilos: un hilo encola trabajo, otro lo desencola. Es la base de los ExecutorService de la lección Programación Concurrente: Hilos, Sincronización y Pools.
• Atención de pedidos en cualquier sistema donde el orden de llegada sea la regla.

5. Cómo se hace en Java de verdad

No implementes esto en producción. Java ya lo trae, y bien hecho:

import java.util.ArrayDeque;
import java.util.Deque;

// PILA
Deque<String> pila = new ArrayDeque<>();
pila.push("A");
pila.push("B");
System.out.println(pila.pop());    // B
System.out.println(pila.peek());   // A (sin sacarlo)

// COLA
Deque<String> cola = new ArrayDeque<>();
cola.offer("A");                   // enqueue
cola.offer("B");
System.out.println(cola.poll());   // A — dequeue

Un Deque (“double ended queue”) permite operar en los dos extremos, así que sirve como pila y como cola. ArrayDeque es la implementación recomendada para ambos casos: usa por dentro exactamente un buffer circular como el que acabás de ver.

No uses la clase Stack de Java. Es de 1996, hereda de Vector, está sincronizada innecesariamente en cada operación —lo que la hace lenta— y, lo peor, itera de abajo hacia arriba, al revés de como funciona una pila. La documentación oficial de Java recomienda ArrayDeque en su lugar.

También existen offer/poll como alternativas a add/remove: las primeras devuelven null o false cuando la operación no se puede hacer, las segundas lanzan excepción. Elegí según si el caso es esperable o es un error.

6. El clásico: ¿está balanceada la expresión?

Este problema es el “hola mundo” de las pilas, y aparece en entrevistas laborales con una frecuencia sospechosa. La idea es verificar que cada (, [ y { tenga su cierre correspondiente, en el orden correcto.

La clave conceptual: el último símbolo que abriste es el primero que tenés que cerrar. Esa frase es, palabra por palabra, la definición de LIFO. Por eso el problema y la estructura encajan perfecto.

7. Errores frecuentes

8. Ejercicio práctico guiado

Desafío: esBalanceado(String expresion)

Escribí un método que devuelva true si todos los símbolos de apertura (, [, { tienen su cierre correspondiente en el orden correcto.

Casos que tiene que resolver bien:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class VerificadorDeBalanceo {

    // Cada cierre apunta a su apertura correspondiente
    private static final Map<Character, Character> PARES = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

    public static boolean esBalanceado(String expresion) {
        if (expresion == null) {
            return false;
        }

        Deque<Character> pila = new ArrayDeque<>();

        for (char c : expresion.toCharArray()) {

            if (PARES.containsValue(c)) {
                // Es una apertura: la anotamos y seguimos
                pila.push(c);

            } else if (PARES.containsKey(c)) {
                // Es un cierre. Dos formas de fallar acá:

                // 1) No hay nada abierto: se cierra algo que nunca se abrió
                if (pila.isEmpty()) {
                    return false;
                }

                // 2) Lo último que se abrió no es del mismo tipo
                if (pila.pop() != PARES.get(c)) {
                    return false;
                }
            }
            // Cualquier otro carácter no participa: se ignora
        }

        // Tercera forma de fallar: quedaron aperturas sin cerrar.
        // Si la pila está vacía, todo cerró correctamente.
        return pila.isEmpty();
    }

    public static void main(String[] args) {
        String[] casos = {
            "{ a + [ b * ( c ) ] }",   // true
            "( ( a )",                 // false: falta un cierre
            "( a ] )",                 // false: cierre cruzado
            ") a (",                   // false: cierra sin abrir
            "",                        // true: nada que desbalancear
            "sin simbolos"             // true
        };

        for (String caso : casos) {
            System.out.printf("%-24s → %s%n", "\"" + caso + "\"", esBalanceado(caso));
        }
    }
}

9. Simulación de eventos discretos con dos colas

Una simulación de eventos discretos no espera que transcurra tiempo real. Mantiene un reloj simulado y salta directamente al instante del próximo evento. Por eso no usa Thread.sleep: dormir haría la prueba lenta y dependiente del reloj del equipo sin mejorar el modelo.

Este problema necesita dos colas con responsabilidades diferentes:

Un instante no alcanza para ordenar: una llegada y una finalización pueden coincidir. La secuencia creciente funciona como desempate determinista. Con las mismas entradas, la simulación procesa exactamente el mismo orden.

Ejemplo ejecutable y acotado

El modelo siguiente representa un servidor, llegadas conocidas y una duración de servicio constante. Cada Evento y cada Cliente es un record inmutable.

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

public final class SimuladorCola {
    private static final int MAX_EVENTOS = 20_000;

    private enum Tipo { LLEGADA, FINALIZACION }

    private record Evento(long tiempo, long secuencia, Tipo tipo, int clienteId) {
        Evento {
            if (tiempo < 0 || secuencia < 0) {
                throw new IllegalArgumentException("tiempo y secuencia deben ser no negativos");
            }
            Objects.requireNonNull(tipo, "tipo es obligatorio");
        }
    }

    private record Cliente(int id, long llegada) {}

    public record Metricas(int atendidos, double esperaPromedio, int longitudMaximaCola) {}

    private final PriorityQueue<Evento> futuros = new PriorityQueue<>(
        Comparator.comparingLong(Evento::tiempo)
            .thenComparingLong(Evento::secuencia)
    );
    private final ArrayDeque<Cliente> colaServicio = new ArrayDeque<>();
    private final long duracionServicio;
    private long reloj = 0;
    private long siguienteSecuencia = 0;
    private long esperaTotal = 0;
    private int atendidos = 0;
    private int longitudMaxima = 0;
    private boolean servidorOcupado = false;

    private SimuladorCola(long duracionServicio) {
        if (duracionServicio <= 0) {
            throw new IllegalArgumentException("duracionServicio debe ser positiva");
        }
        this.duracionServicio = duracionServicio;
    }

    public static Metricas simular(long[] llegadas, long duracionServicio) {
        if (llegadas == null || llegadas.length == 0) {
            throw new IllegalArgumentException("llegadas debe contener al menos un instante");
        }
        if (llegadas.length * 2L > MAX_EVENTOS) {
            throw new IllegalArgumentException("la simulación supera MAX_EVENTOS");
        }

        SimuladorCola simulador = new SimuladorCola(duracionServicio);
        long anterior = -1;
        for (int id = 0; id < llegadas.length; id++) {
            long llegada = llegadas[id];
            if (llegada < 0 || llegada < anterior) {
                throw new IllegalArgumentException(
                    "las llegadas deben ser no negativas y monótonas"
                );
            }
            simulador.programar(llegada, Tipo.LLEGADA, id);
            anterior = llegada;
        }
        return simulador.ejecutar();
    }

    private void programar(long tiempo, Tipo tipo, int clienteId) {
        if (tiempo < reloj) {
            throw new IllegalArgumentException("no se puede programar en el pasado");
        }
        futuros.add(new Evento(tiempo, siguienteSecuencia++, tipo, clienteId));
    }

    private Metricas ejecutar() {
        int procesados = 0;
        while (!futuros.isEmpty()) {
            if (++procesados > MAX_EVENTOS) {
                throw new IllegalStateException("la simulación no converge dentro del límite");
            }

            Evento evento = futuros.remove();
            if (evento.tiempo() < reloj) {
                throw new IllegalStateException("el reloj simulado no puede retroceder");
            }
            reloj = evento.tiempo();

            if (evento.tipo() == Tipo.LLEGADA) {
                colaServicio.addLast(new Cliente(evento.clienteId(), reloj));
                if (!servidorOcupado) {
                    iniciarSiguiente();
                }
                longitudMaxima = Math.max(longitudMaxima, colaServicio.size());
            } else {
                atendidos++;
                servidorOcupado = false;
                iniciarSiguiente();
            }
        }

        if (servidorOcupado || !colaServicio.isEmpty()) {
            throw new IllegalStateException("terminó la agenda con trabajo pendiente");
        }
        return new Metricas(atendidos, (double) esperaTotal / atendidos, longitudMaxima);
    }

    private void iniciarSiguiente() {
        Cliente cliente = colaServicio.pollFirst();
        if (cliente == null) {
            return;
        }
        esperaTotal += reloj - cliente.llegada();
        servidorOcupado = true;
        long finalizacion = Math.addExact(reloj, duracionServicio);
        programar(finalizacion, Tipo.FINALIZACION, cliente.id());
    }

    public static void main(String[] args) {
        Metricas metricas = simular(new long[] {0, 1, 1, 5}, 3);
        System.out.println(metricas);
    }
}

Cómo avanza el modelo

1. Todas las LLEGADA válidas se programan en la cola de eventos futuros.
2. El bucle extrae el evento mínimo y mueve reloj a su instante; no incrementa el tiempo paso a paso.
3. Una llegada entra en la cola FIFO. Si el servidor está libre, comienza el servicio y se programa FINALIZACION.
4. Una finalización libera el servidor y comienza el siguiente servicio pendiente.
5. La simulación termina cuando la agenda queda vacía y no existe trabajo pendiente.

Cada llegada genera como máximo una finalización. Junto con MAX_EVENTOS, esa propiedad proporciona una terminación acotada. Math.addExact hace explícito un eventual desbordamiento del reloj.

Métricas y significado

• Tiempo de espera: reloj - llegada cuando comienza el servicio. El promedio usa solo clientes atendidos.
• Longitud de la cola: cantidad de clientes esperando, sin contar al que está en servicio. La longitud máxima ayuda a estimar capacidad.
• Reloj final: puede añadirse para calcular rendimiento por unidad de tiempo, pero no es tiempo real.

Fallos frecuentes

• Usar solo tiempo en el comparador: los empates quedan sin una política reproducible.
• Usar una cola FIFO para eventos futuros: procesa por inserción, no por instante.
• Usar PriorityQueue para clientes que deben conservar orden de llegada: cambia la disciplina de servicio.
• Ejecutar Thread.sleep: mezcla simulación con tiempo de pared y vuelve lentas las pruebas.
• Programar un evento anterior al reloj actual o aceptar tiempos negativos.
• Generar eventos sin límite ni condición de terminación.
• Calcular espera al llegar en vez de cuando empieza el servicio.
• Omitir validaciones y terminar con clientes pendientes fuera de la agenda.

La cola FIFO modela quién sigue; la cola de prioridad modela qué ocurre después. Confundir esas preguntas produce una simulación válida en sintaxis, pero incorrecta en comportamiento.

Para llevarte

• Pila y cola son listas con poderes restringidos, y esa restricción es la característica, no la carencia.
• Como solo se toca un extremo, todas las operaciones son O(1). Sin bucles, sin recorridos.
• La pila necesita un solo puntero (tope); la cola necesita dos (frente y fondo).
• Al desencolar el último elemento hay que limpiar fondo también. Es el bug más común de la cola.
• El operador % convierte un arreglo en un anillo: eso es una cola circular, y está en drivers, buffers de red y sistemas de logging.
• pop/dequeue sobre una estructura vacía es un error de uso: lanzá NoSuchElementException.
• En Java real usá ArrayDeque como Deque, nunca la vieja clase Stack.
• “Lo último que abrí es lo primero que tengo que cerrar” es LIFO expresado en palabras. Por eso la pila resuelve el balanceo.