El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Pila

Siguiente ►
►

En la lección anterior viste que cambiar pollFirst por pollLast en una sola línea convertía un recorrido en anchura en uno en profundidad. Esa línea encierra toda la diferencia entre una cola y una pila: la cola atiende al que lleva más tiempo esperando, la pila atiende al último que llegó.

Una pila es LIFO: Last In, First Out. Es la estructura de una pila de platos, de un montón de papeles en una bandeja, del botón "deshacer" de cualquier editor. Y es, sobre todo, la estructura con la que funciona la propia máquina virtual de Java: cada vez que llamas a un método, la JVM apila un marco con sus variables locales, y cuando el método termina lo desapila. Ese mecanismo —la pila de llamadas— explica el StackOverflowError que probablemente ya has visto al equivocarte con una recursión en 03-03.

Esta lección tiene una particularidad: la clase que Java trae con el nombre Stack está desaconsejada, y verás exactamente por qué con una demostración que sorprende. La forma correcta de usar una pila en Java moderno es Deque, la interfaz que ya conoces. Terminarás implementando una pila propia con un array para entender la estructura desde dentro, resolviendo dos problemas clásicos —paréntesis equilibrados e historial con deshacer y rehacer— y añadiendo a BiblioTech la pila que permite anular la última operación del catálogo.

Contenido

  1. LIFO: la semántica de una pila
  2. Para qué sirve realmente una pila
  3. La pila de llamadas de la JVM y el StackOverflowError
  4. La clase Stack heredada
  5. Por qué Stack está desaconsejada
  6. Deque como pila: la recomendación oficial
  7. Tabla comparativa de las tres opciones
  8. Implementar una pila propia con un array
  9. Caso práctico: paréntesis equilibrados
  10. Caso práctico: historial con deshacer y rehacer
  11. De la recursión a la iteración con una pila explícita
  12. Aplicación a BiblioTech
  13. Errores Comunes y Consejos
  14. Ejercicios

  1. LIFO: la semántica de una pila

Una pila (stack) es una colección donde los elementos entran y salen por el mismo extremo, llamado cima (top).

flowchart TB
    P["push / pop / peek"] --> C["CIMA: modificacion"]
    C --> B["baja"]
    B --> A["alta"]
    A --> F["FONDO (el primero que entro,<br/>el ultimo que saldra)"]

Sus tres operaciones fundamentales:

Operación Qué hace
push(e) Coloca un elemento en la cima
pop() Retira y devuelve el elemento de la cima
peek() Consulta la cima sin retirarla

El comportamiento en una secuencia:

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

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

pila.push("alta:978-0000000001");
pila.push("alta:978-0000000002");
pila.push("baja:978-0000000001");

System.out.println(pila.peek());    // baja:978-0000000001  (la ultima que entro)
System.out.println(pila.pop());     // baja:978-0000000001
System.out.println(pila.pop());     // alta:978-0000000002
System.out.println(pila.size());    // 1

El orden de salida es exactamente el inverso al de entrada. Y esa propiedad —"invierte el orden"— es la clave de casi todas sus aplicaciones: deshacer una secuencia de acciones es rehacerlas al revés, evaluar una expresión anidada es cerrar lo último que se abrió, y volver de una llamada es retomar la que estaba justo antes.

Compara las tres políticas del módulo:

Política Sale primero Metáfora Estructura
FIFO (cola) El que más lleva esperando Cola del supermercado Queue / Deque
LIFO (pila) El último en llegar Pila de platos Deque
Prioridad El más urgente Urgencias de un hospital PriorityQueue

  1. Para qué sirve realmente una pila

Cuatro familias de aplicaciones, y las cuatro aparecen constantemente en programación real.

1. Deshacer (undo). Cada acción del usuario se apila; deshacer es desapilar la última y revertirla. Si además apilas las acciones deshechas en una segunda pila, tienes rehacer gratis. Lo implementarás en el apartado 10.

2. Evaluación de expresiones y análisis sintáctico. Cualquier estructura anidada —paréntesis, llaves, etiquetas HTML, bloques de código— se valida y se procesa con una pila: cada apertura se apila y cada cierre debe corresponder con la cima. Los compiladores, incluido el de Java, usan pilas para analizar el código fuente. Es el apartado 9.

3. Recorrido en profundidad (DFS). Como viste en 05-07, sustituir la cola por una pila convierte un recorrido en anchura en uno en profundidad. La pila mantiene "por dónde iba" mientras el algoritmo baja por una rama.

4. La pila de llamadas de la JVM. No es una aplicación que programes: es cómo funciona el lenguaje. Y merece su propio apartado.

  1. La pila de llamadas de la JVM y el StackOverflowError

Cada hilo de una aplicación Java tiene su propia pila de llamadas (call stack). Cada vez que se invoca un método, la JVM apila un marco de pila (stack frame) que contiene:

  • Los parámetros del método.
  • Sus variables locales.
  • La dirección de retorno: a qué instrucción volver cuando termine.

Cuando el método termina, su marco se desapila y la ejecución continúa donde se quedó quien lo llamó.

public class Traza {
    public static void main(String[] args) {
        System.out.println(calcularMulta(20, 15, 0.25));
    }
    static double calcularMulta(int dias, int plazo, double tarifa) {
        return aplicarTope(diasRetraso(dias, plazo) * tarifa);
    }
    static int diasRetraso(int dias, int plazo) { return Math.max(0, dias - plazo); }
    static double aplicarTope(double multa) { return Math.min(multa, 20.0); }
}
flowchart TB
    subgraph pila["Pila de llamadas en el momento de ejecutar diasRetraso"]
        F3["diasRetraso(20, 15)<br/>← CIMA"]
        F2["calcularMulta(20, 15, 0.25)"]
        F1["main(args)<br/>← FONDO"]
    end
    F3 --> F2 --> F1

Cuando diasRetraso devuelve 5, su marco se desapila y la ejecución vuelve a calcularMulta, que apila entonces el marco de aplicarTope. Es exactamente una pila: lo último que se apila es lo primero que se retira.

Y ahora el error que conecta con 03-03. La pila de un hilo tiene un tamaño limitado (típicamente 512 KB o 1 MB). Si apilas demasiados marcos —normalmente por una recursión sin caso base o demasiado profunda—, se agota:

static int contarSinFin(int n) {
    return contarSinFin(n + 1);      // nunca para: cada llamada apila un marco
}
// Exception in thread "main" java.lang.StackOverflowError

StackOverflowError es un Error, no una Exception: señala un fallo del entorno de ejecución, no una condición que tu programa deba tratar. Sus dos causas típicas:

  • Recursión sin caso base o con un caso base inalcanzable. Es un bug: corrige el algoritmo.
  • Recursión correcta pero demasiado profunda para el tamaño de la pila. Con unos 10 000 niveles ya suele saltar. La solución es convertir la recursión en iteración con una pila explícita, que es exactamente lo que harás en el apartado 11.

La diferencia entre la pila de llamadas y una pila que tú creas es sustancial: la primera vive en una zona de memoria reservada por hilo y de tamaño fijo; la segunda es un objeto normal en el heap, que crece mientras haya memoria. De ahí que una recursión de un millón de niveles reviente y su equivalente iterativa con ArrayDeque funcione sin problemas. La memoria, el recolector y el -Xss que ajusta el tamaño de la pila son temas del módulo 10-07.

  1. La clase Stack heredada

Java trae desde la versión 1.0 una clase llamada literalmente Stack:

import java.util.Stack;

Stack<String> pila = new Stack<>();
pila.push("alta:978-0000000001");
pila.push("baja:978-0000000002");

System.out.println(pila.peek());      // baja:978-0000000002
System.out.println(pila.pop());       // baja:978-0000000002
System.out.println(pila.empty());     // false
System.out.println(pila.search("alta:978-0000000001"));   // 1

Su API:

Método Qué hace Si está vacía
push(e) Apila —
pop() Desapila y devuelve EmptyStackException
peek() Consulta la cima EmptyStackException
empty() ¿Está vacía? —
search(o) Distancia desde la cima (1 para la cima), o -1 —

Dos detalles llamativos ya en esta tabla. empty() en lugar de isEmpty() (aunque también existe el segundo, heredado). Y search devuelve una posición basada en 1, no en 0, lo que rompe la convención de todo el resto de Java.

Sobre EmptyStackException: es una RuntimeException que se lanza al hacer pop o peek sobre una pila vacía. Cómo capturarla es el módulo 6; aquí basta con comprobar isEmpty() antes.

  1. Por qué Stack está desaconsejada

La documentación oficial del JDK lo dice sin rodeos: "Un conjunto más completo y coherente de operaciones LIFO lo proporciona la interfaz Deque, que debería usarse con preferencia a esta clase". Las razones son tres, y la tercera es espectacular.

Razón 1: extiende Vector

public class Stack<E> extends Vector<E> { ... }

Vector es una lista con acceso por índice. Al heredar de ella, Stack expone toda la API de una lista, rompiendo la propia semántica de pila:

Stack<String> pila = new Stack<>();
pila.push("A");
pila.push("B");
pila.push("C");

// Todo esto COMPILA y funciona sobre una "pila":
pila.get(0);              // acceso por indice
pila.add(1, "X");         // insertar en medio
pila.remove(0);           // eliminar del fondo
pila.set(0, "Z");         // modificar el fondo

Una pila que permite tocar el fondo no es una pila: es una lista con tres métodos extra. Y ahí no hay ninguna garantía estructural que proteger. Es, además, un ejemplo de libro de mal uso de la herencia, justo el error que estudiaste en 03-05: Stack no es un Vector; una pila usa un almacenamiento interno. Debería haber sido composición.

Razón 2: está sincronizada

Vector sincroniza todos sus métodos, así que Stack también. Eso significa que cada push y cada pop adquieren y liberan un bloqueo, incluso en un programa de un solo hilo donde no sirve absolutamente para nada.

Y el coste no compra seguridad real: la sincronización método a método no hace atómicas las secuencias compuestas. Este código sigue teniendo una condición de carrera:

if (!pila.isEmpty()) {        // otro hilo puede vaciarla justo aqui
    String x = pila.pop();    // EmptyStackException
}

Es exactamente la misma historia de Hashtable y Vector que viste en 05-05: sincronización global de Java 1.0, que sale cara y no resuelve el problema. Para concurrencia real, el módulo 8.

Razón 3: el iterador recorre al revés de lo esperado

Esta es la que más sorprende, y merece verse ejecutada.

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

Stack<String> stack = new Stack<>();
stack.push("primero");
stack.push("segundo");
stack.push("tercero");     // la CIMA

System.out.println("Stack toString: " + stack);
System.out.print("Stack for-each: ");
for (String s : stack) { System.out.print(s + " "); }

Deque<String> deque = new ArrayDeque<>();
deque.push("primero");
deque.push("segundo");
deque.push("tercero");     // la CIMA

System.out.println("\nDeque toString: " + deque);
System.out.print("Deque for-each: ");
for (String s : deque) { System.out.print(s + " "); }

System.out.println("\nStack.pop(): " + stack.pop());
System.out.println("Deque.pop(): " + deque.pop());
Stack toString: [primero, segundo, tercero]
Stack for-each: primero segundo tercero
Deque toString: [tercero, segundo, primero]
Deque for-each: tercero segundo primero
Stack.pop(): tercero
Deque.pop(): tercero

Stack recorre del fondo a la cima: el orden inverso al que van a salir los elementos. Como hereda el iterador de Vector, recorre el array interno de la posición 0 en adelante, y en Stack la posición 0 es el fondo. Así que pop() devuelve "tercero" pero el iterador empieza por "primero".

ArrayDeque hace lo correcto: recorre desde la cima, en el mismo orden en que saldrían los elementos.

Es una incoherencia grave, porque escribir un bucle que "procese la pila en orden" produce el resultado contrario al esperado, sin ningún aviso.

flowchart TB
    subgraph S["Stack: iterador del FONDO a la CIMA"]
        direction TB
        S1["primero (fondo) ← empieza aqui"]
        S2["segundo"]
        S3["tercero (cima) ← sale primero con pop"]
        S1 --> S2 --> S3
    end
    subgraph D["ArrayDeque: iterador de la CIMA al FONDO"]
        direction TB
        D3["tercero (cima) ← empieza aqui, y sale primero"]
        D2["segundo"]
        D1["primero (fondo)"]
        D3 --> D2 --> D1
    end

El veredicto

Stack no está formalmente marcada como obsoleta —eso rompería demasiado código antiguo—, pero no debe usarse en código nuevo. La usarás solo si te la encuentras en un proyecto heredado.

  1. Deque como pila: la recomendación oficial

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

pila.push("alta:978-0000000001");     // = addFirst
pila.push("baja:978-0000000002");

System.out.println(pila.peek());      // = peekFirst. null si esta vacia
System.out.println(pila.pop());       // = removeFirst. NoSuchElementException si vacia
System.out.println(pila.isEmpty());
System.out.println(pila.size());

Los tres métodos de pila son alias de operaciones sobre la cabeza del Deque:

Método de pila Equivale a Comportamiento si está vacía
push(e) addFirst(e) —
pop() removeFirst() NoSuchElementException
peek() peekFirst() Devuelve null

Fíjate en la asimetría de la última columna, que hay que tener presente: pop() lanza excepción pero peek() devuelve null. Si quieres consistencia, tienes las dos familias completas de 05-07: pollFirst() devuelve null en lugar de lanzar, y getFirst() lanza en lugar de devolver null.

Un patrón seguro para consumir una pila entera:

// Opcion 1: comprobar antes
while (!pila.isEmpty()) {
    procesar(pila.pop());
}

// Opcion 2: el idioma de 05-07, sin comprobacion previa
String op;
while ((op = pila.pollFirst()) != null) {
    procesar(op);
}

¿Por qué la cima es la cabeza del Deque y no la cola? Por rendimiento: en un ArrayDeque, insertar y extraer por la cabeza es O(1) gracias al array circular, igual que por el final. Y push/pop sobre la cabeza permiten que el iterador recorra en el orden de salida, que es lo que corrige el defecto de Stack.

Declaración recomendada:

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

No ArrayDeque<String> pila, ni Stack<String> pila. La interfaz Deque documenta la intención y permite cambiar la implementación.

  1. Tabla comparativa de las tres opciones

Aspecto Stack ArrayDeque como pila LinkedList como pila
Estructura interna Vector (array sincronizado) Array circular Nodos enlazados
push / pop O(1), con bloqueo O(1) sin bloqueo O(1)
Sincronizada Sí (coste inútil) No No
Orden del iterador Fondo → cima (mal) Cima → fondo (bien) Cima → fondo
Expone API de lista Sí (get, add(i,e)) No Sí (es una List)
Memoria por elemento ~4-8 bytes ~4-8 bytes ~28 bytes
Localidad de caché Buena Excelente Mala
Admite null Sí No Sí
Al hacer pop vacía EmptyStackException NoSuchElementException NoSuchElementException
Recomendada No Sí Solo si necesitas null o List

Conclusión: Deque<X> pila = new ArrayDeque<>(). Es la respuesta correcta salvo que necesites almacenar null (entonces LinkedList) o estés en código heredado que ya usa Stack.

  1. Implementar una pila propia con un array

Implementar una pila a mano es un ejercicio corto que aclara la estructura definitivamente. Todo lo que hace falta es un array y un índice.

package com.nexussoftware.bibliotech.servicio;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * Pila de cadenas implementada sobre un array, con fines didacticos.
 * Es, en esencia, lo que hacen ArrayDeque y Stack por dentro.
 */
public class PilaArray {

    private static final int CAPACIDAD_INICIAL = 10;

    private String[] elementos;
    private int      cima;      // indice de la SIGUIENTE posicion libre = numero de elementos

    public PilaArray() {
        this(CAPACIDAD_INICIAL);
    }

    public PilaArray(int capacidadInicial) {
        this.elementos = new String[Math.max(capacidadInicial, 1)];
        this.cima = 0;
    }

    /** Apila. O(1) amortizado: solo copia cuando el array se llena. */
    public void push(String elemento) {
        if (cima == elementos.length) {
            // Crecimiento MULTIPLICATIVO (x2), igual que ArrayList (05-03):
            // es lo que hace que el coste medio por push sea constante.
            elementos = Arrays.copyOf(elementos, elementos.length * 2);
        }
        elementos[cima] = elemento;
        cima++;
    }

    /** Desapila. O(1). */
    public String pop() {
        if (isEmpty()) {
            // El modulo 6 ensena a tratar esto; aqui solo lo senalamos.
            throw new EmptyStackException();
        }
        cima--;
        String elemento = elementos[cima];
        elementos[cima] = null;      // IMPRESCINDIBLE: si no, el objeto no se puede
                                     // recolectar mientras la pila viva (fuga de memoria).
        return elemento;
    }

    /** Consulta la cima sin retirarla. O(1). */
    public String peek() {
        if (isEmpty()) { throw new EmptyStackException(); }
        return elementos[cima - 1];      // cima apunta a la SIGUIENTE libre
    }

    /** Version segura: null en vez de excepcion. */
    public String peekOrNull() {
        return isEmpty() ? null : elementos[cima - 1];
    }

    public boolean isEmpty() { return cima == 0; }
    public int     size()    { return cima; }

    public void clear() {
        Arrays.fill(elementos, 0, cima, null);   // libera todas las referencias
        cima = 0;
    }

    /** Recorre de la CIMA al FONDO: el orden de salida, como debe ser. */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = cima - 1; i >= 0; i--) {    // hacia atras: de la cima al fondo
            sb.append(elementos[i]);
            if (i > 0) { sb.append(", "); }
        }
        return sb.append("]").toString();
    }
}

Uso:

PilaArray pila = new PilaArray(2);        // capacidad pequena para forzar el crecimiento
pila.push("alta:978-0000000001");
pila.push("alta:978-0000000002");
pila.push("baja:978-0000000001");         // aqui el array se duplica

System.out.println(pila);                 // [baja:978-0000000001, alta:..002, alta:..001]
System.out.println("Cima:  " + pila.peek());
System.out.println("Saco:  " + pila.pop());
System.out.println("Quedan: " + pila.size());

Tres detalles de esta implementación merecen atención, porque son exactamente los que aparecen en el código real del JDK:

  1. cima apunta a la siguiente posición libre, así que coincide con el número de elementos y peek() tiene que mirar en cima - 1. La alternativa —que apunte al último elemento y valga -1 cuando está vacía— también funciona, pero obliga a más ajustes.
  2. elementos[cima] = null en pop. Sin esa línea, el array seguiría refiriéndose a un objeto que ya no forma parte de la pila, impidiendo que el recolector lo libere: una fuga de memoria silenciosa. Es el mismo cuidado que tomaste en el CatalogoArray de 05-01 y que ArrayList aplica en su remove.
  3. El crecimiento es multiplicativo, lo que da coste amortizado O(1) por la misma razón que en ArrayList (05-03).

Compárala con lo que ganas usando ArrayDeque: genéricos, comprobación de nulos, iterador correcto, descendingIterator, contains, removeIf, toArray, y veinticinco años de pruebas. La implementación propia es para aprender, no para producción.

  1. Caso práctico: paréntesis equilibrados

Es el problema canónico de pilas y aparece en cualquier analizador sintáctico. Dada una cadena con (, [ y {, comprobar si están correctamente abiertos y cerrados.

La idea: cada símbolo de apertura se apila. Cada símbolo de cierre debe corresponder con el de la cima; si corresponde, se desapila. Al final la pila debe quedar vacía.

package com.nexussoftware.bibliotech.servicio;

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

public final class ValidadorExpresiones {

    private ValidadorExpresiones() { }

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

    public static boolean estaEquilibrada(String expresion) {
        if (expresion == null) { return true; }
        Deque<Character> pila = new ArrayDeque<>();

        for (char c : expresion.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                pila.push(c);                       // apertura: se apila
            } else if (PAREJAS.containsKey(c)) {
                // cierre: la cima DEBE ser su apertura correspondiente
                if (pila.isEmpty() || pila.pop() != PAREJAS.get(c)) {
                    return false;
                }
            }
            // cualquier otro caracter se ignora
        }
        // Si sobra alguna apertura sin cerrar, la pila no esta vacia
        return pila.isEmpty();
    }

    /** Version que ademas informa de DONDE esta el problema. */
    public static String diagnosticar(String expresion) {
        if (expresion == null) { return "OK (cadena nula)"; }
        Deque<Character> simbolos  = new ArrayDeque<>();
        Deque<Integer>   posiciones = new ArrayDeque<>();   // pila paralela de posiciones

        for (int i = 0; i < expresion.length(); i++) {
            char c = expresion.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                simbolos.push(c);
                posiciones.push(i);
            } else if (PAREJAS.containsKey(c)) {
                if (simbolos.isEmpty()) {
                    return String.format("Cierre '%c' sin apertura en la posicion %d", c, i);
                }
                char esperada = PAREJAS.get(c);
                char abierta  = simbolos.pop();
                int  posAbierta = posiciones.pop();
                if (abierta != esperada) {
                    return String.format(
                        "Se esperaba cerrar '%c' (abierto en %d) pero se encontro '%c' en %d",
                        abierta, posAbierta, c, i);
                }
            }
        }
        if (!simbolos.isEmpty()) {
            return String.format("Falta cerrar '%c' abierto en la posicion %d",
                                 simbolos.peek(), posiciones.peek());
        }
        return "OK";
    }

    public static void main(String[] args) {
        String[] casos = {
            "(titulo AND autor)",
            "((titulo OR isbn) AND (anio > 2000))",
            "[tipo=Libro] AND {tarifa<0.30}",
            "(titulo AND autor",
            "titulo AND autor)",
            "([tipo=Libro)]",
            ""
        };
        for (String caso : casos) {
            System.out.printf("%-38s %-5s  %s%n",
                    "\"" + caso + "\"",
                    estaEquilibrada(caso) ? "OK" : "MAL",
                    diagnosticar(caso));
        }
    }
}
"(titulo AND autor)"                   OK     OK
"((titulo OR isbn) AND (anio > 2000))" OK     OK
"[tipo=Libro] AND {tarifa<0.30}"       OK     OK
"(titulo AND autor"                    MAL    Falta cerrar '(' abierto en la posicion 0
"titulo AND autor)"                    MAL    Cierre ')' sin apertura en la posicion 17
"([tipo=Libro)]"                       MAL    Se esperaba cerrar '[' (abierto en 1) pero se encontro ')' en 12
""                                     OK     OK

Por qué solo funciona con una pila. El anidamiento correcto exige que el último símbolo abierto sea el primero en cerrarse: eso es LIFO literalmente. Con un contador simple, ([)] pasaría la validación —hay dos aperturas y dos cierres—, pero está mal anidado. La pila lo detecta porque recuerda qué se abrió y en qué orden.

Fíjate también en la técnica de las dos pilas paralelas de diagnosticar: una guarda los símbolos y otra sus posiciones, y ambas se apilan y desapilan a la vez. Es un recurso habitual cuando necesitas arrastrar información adicional por cada nivel; la alternativa, en Java moderno, sería una pila de un record Apertura(char simbolo, int posicion).

  1. Caso práctico: historial con deshacer y rehacer

El segundo patrón clásico: dos pilas, una para deshacer y otra para rehacer.

flowchart LR
    A["Accion nueva"] --> D["Pila DESHACER"]
    D -->|deshacer| R["Pila REHACER"]
    R -->|rehacer| D
    A -.->|"la accion nueva<br/>VACIA la pila de rehacer"| X["rehacer: vacia"]

La mecánica:

  • Acción nueva: se apila en deshacer y se vacía la pila de rehacer (ya no tiene sentido rehacer un futuro que ha cambiado).
  • Deshacer: se desapila de deshacer, se revierte y se apila en rehacer.
  • Rehacer: se desapila de rehacer, se reaplica y se apila en deshacer.
package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/** Historial de navegacion con deshacer y rehacer, con dos pilas. */
public class HistorialNavegacion {

    private final Deque<String> atras    = new ArrayDeque<>();
    private final Deque<String> adelante = new ArrayDeque<>();
    private String actual;

    public HistorialNavegacion(String paginaInicial) {
        this.actual = paginaInicial;
    }

    /** Navegar a una pagina nueva invalida todo el "adelante". */
    public void visitar(String pagina) {
        if (pagina == null || pagina.equals(actual)) { return; }
        atras.push(actual);
        actual = pagina;
        adelante.clear();      // ya no hay futuro que rehacer
    }

    /** Deshacer: la actual pasa a "adelante" y se recupera la anterior. */
    public String atras() {
        if (atras.isEmpty()) { return actual; }    // nada que deshacer
        adelante.push(actual);
        actual = atras.pop();
        return actual;
    }

    /** Rehacer: la actual vuelve a "atras" y se recupera la siguiente. */
    public String adelante() {
        if (adelante.isEmpty()) { return actual; }
        atras.push(actual);
        actual = adelante.pop();
        return actual;
    }

    public String  actual()       { return actual; }
    public boolean puedeIrAtras() { return !atras.isEmpty(); }
    public boolean puedeIrAdelante() { return !adelante.isEmpty(); }

    /**
     * Historial visible, de la mas reciente a la mas antigua.
     * El iterador de ArrayDeque ya recorre de la cima al fondo, que es
     * exactamente el orden que queremos. Con Stack habria que invertirlo.
     */
    public List<String> historialAtras() {
        return new ArrayList<>(atras);
    }

    public String barraEstado() {
        return String.format("%s %s %s  |  %s",
                puedeIrAtras()    ? "<" : "-",
                actual,
                puedeIrAdelante() ? ">" : "-",
                atras.isEmpty() ? "(inicio)" : "atras: " + atras.peek());
    }
}

Uso:

HistorialNavegacion h = new HistorialNavegacion("catalogo");
h.visitar("catalogo/libros");
h.visitar("catalogo/libros/978-0000000001");
h.visitar("prestamos/marta-ruiz");

System.out.println(h.barraEstado());
System.out.println("Atras -> " + h.atras());
System.out.println("Atras -> " + h.atras());
System.out.println("Adelante -> " + h.adelante());
System.out.println("Historial: " + h.historialAtras());

h.visitar("informes/multas");            // pagina NUEVA: se pierde el "adelante"
System.out.println("Puede ir adelante: " + h.puedeIrAdelante());
< prestamos/marta-ruiz -  |  atras: catalogo/libros/978-0000000001
Atras -> catalogo/libros/978-0000000001
Atras -> catalogo/libros
Adelante -> catalogo/libros/978-0000000001
Historial: [catalogo/libros, catalogo]
Puede ir adelante: false

Este es exactamente el comportamiento de los botones "atrás" y "adelante" de cualquier navegador, y de "deshacer/rehacer" de cualquier editor. Y observa el detalle de historialAtras(): el iterador de ArrayDeque ya devuelve la lista en el orden correcto —de lo más reciente a lo más antiguo—, cosa que con Stack habría que invertir a mano por lo que viste en el apartado 5.

  1. De la recursión a la iteración con una pila explícita

Toda función recursiva puede convertirse en iterativa usando una pila, porque la recursión no es más que el uso implícito de la pila de llamadas de la JVM. Hacer esa pila explícita elimina el riesgo de StackOverflowError, porque la pila explícita vive en el heap.

Un ejemplo concreto: recorrer un árbol de categorías del catálogo y acumular todas las referencias.

package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/** Categoria del catalogo que puede contener subcategorias. */
class Categoria {
    private final String nombre;
    private final List<Categoria> subcategorias = new ArrayList<>();
    private final List<String>    referencias   = new ArrayList<>();

    Categoria(String nombre) { this.nombre = nombre; }

    Categoria anadirSub(Categoria c) { subcategorias.add(c); return this; }
    Categoria anadirRef(String r)    { referencias.add(r);   return this; }

    String getNombre()                { return nombre; }
    List<Categoria> getSubcategorias(){ return subcategorias; }
    List<String>    getReferencias()  { return referencias; }
}

public final class RecorridoCategorias {

    private RecorridoCategorias() { }

    /**
     * Version RECURSIVA. Clara y corta, pero cada nivel apila un marco
     * en la pila de la JVM: con un arbol muy profundo, StackOverflowError.
     */
    public static List<String> recursivo(Categoria raiz) {
        List<String> resultado = new ArrayList<>();
        recolectar(raiz, resultado);
        return resultado;
    }

    private static void recolectar(Categoria c, List<String> acumulador) {
        if (c == null) { return; }
        acumulador.addAll(c.getReferencias());
        for (Categoria sub : c.getSubcategorias()) {
            recolectar(sub, acumulador);           // llamada recursiva
        }
    }

    /**
     * Version ITERATIVA con pila EXPLICITA. Hace exactamente lo mismo,
     * pero la pila vive en el heap: soporta arboles de cualquier profundidad.
     */
    public static List<String> iterativo(Categoria raiz) {
        List<String> resultado = new ArrayList<>();
        if (raiz == null) { return resultado; }

        Deque<Categoria> pila = new ArrayDeque<>();
        pila.push(raiz);

        while (!pila.isEmpty()) {
            Categoria actual = pila.pop();          // LIFO -> recorrido en PROFUNDIDAD
            resultado.addAll(actual.getReferencias());

            // Apilamos las subcategorias EN ORDEN INVERSO para que la primera
            // se procese primero: la pila invierte el orden, asi que
            // invertirlo al apilar lo deja como en la version recursiva.
            List<Categoria> subs = actual.getSubcategorias();
            for (int i = subs.size() - 1; i >= 0; i--) {
                pila.push(subs.get(i));
            }
        }
        return resultado;
    }

    public static void main(String[] args) {
        Categoria raiz = new Categoria("Tecnica");
        Categoria java = new Categoria("Java")
                .anadirRef("978-0000000001")
                .anadirRef("REV-2024-03");
        Categoria diseno = new Categoria("Diseno")
                .anadirRef("978-0000000002")
                .anadirSub(new Categoria("Refactorizacion")
                        .anadirRef("978-0000000003")
                        .anadirRef("DVD-0007"));
        raiz.anadirSub(java).anadirSub(diseno);

        System.out.println("Recursivo: " + recursivo(raiz));
        System.out.println("Iterativo: " + iterativo(raiz));
        System.out.println("Iguales:   " + recursivo(raiz).equals(iterativo(raiz)));
    }
}
Recursivo: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Iterativo: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Iguales:   true

Dos observaciones importantes:

El truco del orden inverso al apilar. Como la pila invierte, apilar las subcategorías de izquierda a derecha las procesaría de derecha a izquierda. Apilarlas al revés compensa esa inversión y reproduce exactamente el orden de la versión recursiva. Es un detalle que se olvida a menudo y produce recorridos correctos pero en orden inesperado.

Cuándo hacer esta conversión. La versión recursiva es más legible y debe ser la opción por defecto. Convierte a iterativa solo cuando la profundidad pueda ser grande —estructuras de datos que vienen de fuera, árboles de directorios muy anidados, grafos con miles de niveles— o cuando necesites controlar el recorrido (pausarlo, reanudarlo, limitarlo).

Y compara con 05-07: si en iterativo cambiaras la pila por una cola (pollFirst en lugar de pop), tendrías un recorrido en anchura. Misma estructura de código, dos algoritmos.

  1. Aplicación a BiblioTech

La pila de deshacer del catálogo, que permite anular la última alta o baja.

Primero, modelamos la operación. Usamos un record (04-07) porque es un dato inmutable, y un enum para el tipo:

package com.nexussoftware.bibliotech.dominio;

/** Operacion reversible sobre el catalogo. */
public record OperacionCatalogo(Tipo tipo, Material material, int dia) {

    public enum Tipo {
        ALTA("Alta de material"),
        BAJA("Baja de material");

        private final String descripcion;
        Tipo(String descripcion) { this.descripcion = descripcion; }
        public String getDescripcion() { return descripcion; }

        /** La operacion contraria: lo que hay que hacer para deshacer esta. */
        public Tipo inversa() {
            return (this == ALTA) ? BAJA : ALTA;
        }
    }

    public OperacionCatalogo {
        if (tipo == null)     { tipo = Tipo.ALTA; }
        if (dia  < 0)         { dia = 0; }
    }

    @Override
    public String toString() {
        return String.format("%s de '%s' (%s) el dia %d",
                tipo.getDescripcion(), material.getTitulo(), material.getReferencia(), dia);
    }
}

Y el catálogo con historial reversible:

package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.nexussoftware.bibliotech.dominio.Material;
import com.nexussoftware.bibliotech.dominio.OperacionCatalogo;

/**
 * Catalogo con pila de deshacer y rehacer.
 *
 * Deque<OperacionCatalogo> sobre ArrayDeque: push/pop en O(1), iterador
 * que recorre de la mas reciente a la mas antigua (lo que queremos para
 * mostrar el historial) y sin la sincronizacion inutil de Stack.
 */
public class CatalogoConHistorial {

    private static final int MAXIMO_HISTORIAL = 50;

    private final Map<String, Material> porReferencia = new HashMap<>();
    private final Deque<OperacionCatalogo> deshacer = new ArrayDeque<>();
    private final Deque<OperacionCatalogo> rehacer  = new ArrayDeque<>();

    /** Alta: registra la operacion en la pila de deshacer. */
    public boolean darDeAlta(Material m, int dia) {
        if (m == null || porReferencia.containsKey(m.getReferencia())) { return false; }
        porReferencia.put(m.getReferencia(), m);
        registrar(new OperacionCatalogo(OperacionCatalogo.Tipo.ALTA, m, dia));
        return true;
    }

    /** Baja: idem. */
    public boolean darDeBaja(String referencia, int dia) {
        Material m = porReferencia.remove(referencia);
        if (m == null) { return false; }
        registrar(new OperacionCatalogo(OperacionCatalogo.Tipo.BAJA, m, dia));
        return true;
    }

    private void registrar(OperacionCatalogo op) {
        deshacer.push(op);
        rehacer.clear();                   // una operacion nueva invalida el "rehacer"
        // Acotamos el historial descartando por el FONDO: solo un Deque permite esto en O(1)
        if (deshacer.size() > MAXIMO_HISTORIAL) {
            deshacer.pollLast();
        }
    }

    /** Anula la ultima operacion. Devuelve null si no habia ninguna. */
    public OperacionCatalogo deshacer() {
        OperacionCatalogo op = deshacer.poll();     // poll: null si esta vacia
        if (op == null) { return null; }
        aplicarInversa(op);
        rehacer.push(op);
        return op;
    }

    /** Vuelve a aplicar la ultima operacion deshecha. */
    public OperacionCatalogo rehacer() {
        OperacionCatalogo op = rehacer.poll();
        if (op == null) { return null; }
        aplicar(op);
        deshacer.push(op);
        return op;
    }

    private void aplicar(OperacionCatalogo op) {
        switch (op.tipo()) {           // switch sobre enum, sin default: exhaustivo (04-07)
            case ALTA -> porReferencia.put(op.material().getReferencia(), op.material());
            case BAJA -> porReferencia.remove(op.material().getReferencia());
        }
    }

    private void aplicarInversa(OperacionCatalogo op) {
        switch (op.tipo().inversa()) {
            case ALTA -> porReferencia.put(op.material().getReferencia(), op.material());
            case BAJA -> porReferencia.remove(op.material().getReferencia());
        }
    }

    /** Deshace las N ultimas operaciones. */
    public int deshacerVarias(int cuantas) {
        int hechas = 0;
        for (int i = 0; i < cuantas && deshacer() != null; i++) { hechas++; }
        return hechas;
    }

    /** Historial de la mas reciente a la mas antigua: el orden del iterador de ArrayDeque. */
    public List<OperacionCatalogo> historial() {
        return new ArrayList<>(deshacer);
    }

    public OperacionCatalogo ultimaOperacion() { return deshacer.peek(); }
    public boolean puedeDeshacer()             { return !deshacer.isEmpty(); }
    public boolean puedeRehacer()              { return !rehacer.isEmpty(); }
    public int     tamano()                    { return porReferencia.size(); }
    public Material buscar(String referencia)  { return porReferencia.get(referencia); }
}

Uso:

CatalogoConHistorial catalogo = new CatalogoConHistorial();

Material javaEfectivo  = new Libro("Java Efectivo",      "Joshua Bloch",  "978-0000000001", 2018);
Material patrones      = new Libro("Patrones de Diseno", "Erich Gamma",   "978-0000000002", 1994);
Material refactorizar  = new Libro("Refactorizacion",    "Martin Fowler", "978-0000000003", 1999);
Material revista       = new Revista("Java Magazine",    "REV-2024-03",   42, "Mensual");

catalogo.darDeAlta(javaEfectivo, 100);
catalogo.darDeAlta(patrones,     101);
catalogo.darDeAlta(refactorizar, 102);
catalogo.darDeAlta(revista,      103);
catalogo.darDeBaja("978-0000000002", 105);      // baja de Patrones de Diseno

System.out.println("Materiales: " + catalogo.tamano());
System.out.println("Ultima operacion: " + catalogo.ultimaOperacion());

System.out.println("\n--- Deshaciendo ---");
System.out.println("Deshecho: " + catalogo.deshacer());
System.out.println("Materiales: " + catalogo.tamano()
                   + "  (Patrones ha vuelto: " + (catalogo.buscar("978-0000000002") != null) + ")");

System.out.println("\n--- Rehaciendo ---");
System.out.println("Rehecho: " + catalogo.rehacer());
System.out.println("Materiales: " + catalogo.tamano());

System.out.println("\n--- Deshaciendo tres operaciones ---");
System.out.println("Deshechas: " + catalogo.deshacerVarias(3));
System.out.println("Materiales: " + catalogo.tamano());

System.out.println("\n--- Historial pendiente (mas reciente primero) ---");
catalogo.historial().forEach(op -> System.out.println("  " + op));
Materiales: 3
Ultima operacion: Baja de material de 'Patrones de Diseno' (978-0000000002) el dia 105

--- Deshaciendo ---
Deshecho: Baja de material de 'Patrones de Diseno' (978-0000000002) el dia 105
Materiales: 4  (Patrones ha vuelto: true)

--- Rehaciendo ---
Rehecho: Baja de material de 'Patrones de Diseno' (978-0000000002) el dia 105
Materiales: 3

--- Deshaciendo tres operaciones ---
Deshechas: 3
Materiales: 2

--- Historial pendiente (mas reciente primero) ---
  Alta de material de 'Patrones de Diseno' (978-0000000002) el dia 101
  Alta de material de 'Java Efectivo' (978-0000000001) el dia 100

Tres decisiones de diseño que vale la pena señalar. registrar acota el historial descartando por el fondo con pollLast(): eso es O(1) solo porque un Deque abre los dos extremos —con una pila pura habría que vaciarla y reconstruirla—. El switch sobre el enum no lleva default, así que si mañana añades un tipo de operación el compilador te llevará a los dos puntos que hay que actualizar (04-07). Y historial() aprovecha que el iterador de ArrayDeque recorre de la cima al fondo, entregando la lista en el orden que espera el usuario.

Errores Comunes y Consejos

Usar java.util.Stack en código nuevo. Extiende Vector, está sincronizada innecesariamente, expone la API de una lista sobre una pila y su iterador recorre del fondo a la cima, al revés de como salen los elementos. Usa Deque<X> pila = new ArrayDeque<>().

Recorrer una Stack con for-each esperando el orden de salida. Devuelve el orden inverso. Con ArrayDeque el iterador sí va de la cima al fondo.

pop() sobre una pila vacía. Lanza NoSuchElementException en ArrayDeque y EmptyStackException en Stack. Comprueba isEmpty() antes, o usa pollFirst(), que devuelve null.

Confundir la asimetría de push/pop/peek en Deque. pop() lanza excepción, pero peek() devuelve null. Si quieres coherencia, usa las familias completas: pollFirst/peekFirst (devuelven null) o removeFirst/getFirst (lanzan).

Insertar null en un ArrayDeque. NullPointerException, igual que en las colas: null está reservado como señal de "vacío".

Olvidar poner a null la celda liberada al implementar una pila propia. El array sigue refiriéndose al objeto desapilado e impide que se recolecte: fuga de memoria.

Olvidar vaciar la pila de rehacer al registrar una acción nueva. Rehacer un futuro que ya no existe produce estados incoherentes. Es el error más frecuente al implementar deshacer/rehacer.

Olvidar invertir el orden al apilar hijos en un recorrido en profundidad. La pila invierte, así que apilar en orden natural los procesa al revés. Apílalos en orden inverso si quieres reproducir el orden de la versión recursiva.

Confundir la pila de llamadas con una pila de datos. La primera es memoria reservada por hilo, de tamaño fijo, y su agotamiento produce StackOverflowError. La segunda es un objeto del heap y crece mientras haya memoria. Por eso convertir una recursión profunda en iteración con ArrayDeque resuelve el problema.

Consejo: si el problema menciona "el último", "deshacer", "anidado" o "volver atrás", es una pila. Igual que "por orden de llegada" era una cola y "sin repetidos" era un Set, el enunciado suele decir la estructura.

Consejo: Deque es la interfaz más rentable del Framework. Con una sola implementación —ArrayDeque— tienes cola FIFO, pila LIFO y cola de doble extremo, todo en O(1) y con la mejor localidad de caché.

Ejercicios

Ejercicio 1: pila de deshacer para préstamos

Amplía BiblioTech con GestorPrestamosReversible que mantenga una pila de las últimas operaciones de préstamo y devolución, permitiendo anularlas:

  • Crea un record OperacionPrestamo(Tipo tipo, Prestamo prestamo, int dia) con enum Tipo { PRESTAMO, DEVOLUCION }.
  • void prestar(Prestamo p, int dia) y void devolver(Prestamo p, int dia), que registren la operación.
  • OperacionPrestamo deshacer(): revierte la última (un préstamo deshecho devuelve el material; una devolución deshecha vuelve a marcarlo como prestado).
  • List<OperacionPrestamo> ultimas(int cuantas): sin vaciar la pila.
  • int deshacerHasta(int dia): deshace todas las operaciones posteriores a ese día.
  • Limita el historial a 20 operaciones descartando las más antiguas.

Ejercicio 2: Stack frente a ArrayDeque

Escribe ComparativaPilas con un main que demuestre, imprimiendo y explicando cada punto:

  1. Que Stack y ArrayDeque dan el mismo resultado con push/pop/peek.
  2. Que sus iteradores y sus toString recorren en órdenes opuestos, y por qué.
  3. Que Stack permite operaciones de lista que rompen la semántica de pila (get(0), add(1, x), remove(0)), y que ArrayDeque no las ofrece.
  4. Que Stack.search devuelve una posición basada en 1.
  5. Una medición ilustrativa de un millón de push/pop en ambas, con la advertencia sobre JMH.

Ejercicio 3: evaluador de expresiones en notación polaca inversa

La notación polaca inversa (RPN) coloca el operador después de sus operandos: 3 4 + es 3 + 4, y 5 1 2 + 4 * + 3 - es 5 + ((1+2)*4) - 3 = 14. Su gran virtud es que no necesita paréntesis y se evalúa con una sola pila.

Escribe EvaluadorRPN con:

  • double evaluar(String expresion): recorre los símbolos separados por espacios; si es un número lo apila, y si es un operador (+, -, *, /) desapila dos operandos, opera y apila el resultado. Al final debe quedar exactamente un valor.
  • Manejo de casos inválidos sin excepciones propias (módulo 6): devuelve Double.NaN e imprime un aviso.
  • String traza(String expresion): muestra el estado de la pila tras cada símbolo.

Aplícalo a una tarifa de BiblioTech: "15 0.25 * 20 min" no es RPN estándar, así que usa "20 15 - 0.25 *" para calcular la multa de un libro devuelto el día 20 con plazo 15.

Soluciones

Solución 1

package com.nexussoftware.bibliotech.servicio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import com.nexussoftware.bibliotech.dominio.Prestamo;

/** Operacion reversible sobre un prestamo. */
record OperacionPrestamo(Tipo tipo, Prestamo prestamo, int dia) {

    enum Tipo { PRESTAMO, DEVOLUCION }

    @Override
    public String toString() {
        return String.format("%-11s %s (%s) dia %d", tipo, prestamo.getReferencia(),
                prestamo.getMaterial().getTitulo(), dia);
    }
}

public class GestorPrestamosReversible {

    private static final int MAXIMO_HISTORIAL = 20;

    private final Deque<OperacionPrestamo> historial = new ArrayDeque<>();

    private void registrar(OperacionPrestamo op) {
        historial.push(op);
        // Acotar por el FONDO en O(1): solo posible con un Deque, no con una pila pura
        if (historial.size() > MAXIMO_HISTORIAL) {
            historial.pollLast();
        }
    }

    public void prestar(Prestamo p, int dia) {
        if (p == null) { return; }
        p.getMaterial().prestar();
        registrar(new OperacionPrestamo(OperacionPrestamo.Tipo.PRESTAMO, p, dia));
    }

    public void devolver(Prestamo p, int dia) {
        if (p == null) { return; }
        p.registrarDevolucion(dia);
        registrar(new OperacionPrestamo(OperacionPrestamo.Tipo.DEVOLUCION, p, dia));
    }

    /** Revierte la ultima operacion. poll devuelve null si no hay ninguna. */
    public OperacionPrestamo deshacer() {
        OperacionPrestamo op = historial.poll();
        if (op == null) { return null; }

        // switch exhaustivo sobre enum, sin default (04-07): si manana anadimos
        // un tipo de operacion, el compilador nos traera aqui.
        switch (op.tipo()) {
            case PRESTAMO   -> op.prestamo().getMaterial().devolver();  // deshacer prestar
            case DEVOLUCION -> op.prestamo().getMaterial().prestar();   // deshacer devolver
        }
        return op;
    }

    /**
     * Las N ultimas SIN vaciar la pila.
     * El iterador de ArrayDeque va de la cima al fondo: justo el orden que queremos.
     */
    public List<OperacionPrestamo> ultimas(int cuantas) {
        List<OperacionPrestamo> resultado = new ArrayList<>();
        int n = 0;
        for (OperacionPrestamo op : historial) {
            if (n++ >= cuantas) { break; }
            resultado.add(op);
        }
        return resultado;
    }

    /**
     * Deshace todo lo posterior a 'dia'. peek() consulta sin sacar, para
     * decidir si conviene deshacer antes de comprometerse.
     */
    public int deshacerHasta(int dia) {
        int deshechas = 0;
        while (!historial.isEmpty() && historial.peek().dia() > dia) {
            deshacer();
            deshechas++;
        }
        return deshechas;
    }

    public OperacionPrestamo ultima()   { return historial.peek(); }
    public boolean puedeDeshacer()      { return !historial.isEmpty(); }
    public int     operacionesEnPila()  { return historial.size(); }
}

Prueba:

Empleado marta = new Empleado("Marta Ruiz", "EMP-001");
Material javaEfectivo = new Libro("Java Efectivo", "Joshua Bloch", "978-0000000001", 2018);
Material patrones     = new Libro("Patrones de Diseno", "Erich Gamma", "978-0000000002", 1994);

GestorPrestamosReversible g = new GestorPrestamosReversible();
Prestamo p1 = new Prestamo(javaEfectivo, marta, 100);
Prestamo p2 = new Prestamo(patrones,     marta, 105);

g.prestar(p1, 100);
g.prestar(p2, 105);
g.devolver(p1, 118);

System.out.println("Ultima: " + g.ultima());
System.out.println("Java Efectivo disponible: " + javaEfectivo.estaDisponible());  // true

System.out.println("Deshecho: " + g.deshacer());
System.out.println("Java Efectivo disponible: " + javaEfectivo.estaDisponible());  // false

System.out.println("Deshechas hasta el dia 100: " + g.deshacerHasta(100));
System.out.println("Operaciones en pila: " + g.operacionesEnPila());

El punto clave es peek() en deshacerHasta: permite consultar la cima sin sacarla, decidir si toca deshacerla y solo entonces comprometerse. Sin peek, habría que sacar el elemento para mirarlo y volver a apilarlo si no procedía, lo que además dejaría la pila en un estado transitorio incorrecto. Es la razón exacta por la que las tres operaciones de una pila son push, pop y peek.

Solución 2

package com.nexussoftware.bibliotech.presentacion;

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

public class ComparativaPilas {

    public static void main(String[] args) {
        mismoResultado();
        ordenesOpuestos();
        stackRompeLaSemantica();
        searchBasadoEn1();
        rendimiento();
    }

    static void mismoResultado() {
        System.out.println("=== 1. push/pop/peek dan lo mismo ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "alta", "baja", "modificacion" }) {
            stack.push(s);
            deque.push(s);
        }
        System.out.println("Stack peek: " + stack.peek() + " | Deque peek: " + deque.peek());
        System.out.println("Stack pop:  " + stack.pop()  + " | Deque pop:  " + deque.pop());
        System.out.println("Ambas devuelven la CIMA: LIFO correcto en las dos.\n");
    }

    static void ordenesOpuestos() {
        System.out.println("=== 2. Iteradores en ordenes OPUESTOS ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "primero", "segundo", "tercero" }) {
            stack.push(s);
            deque.push(s);
        }

        System.out.println("Stack toString: " + stack);   // [primero, segundo, tercero]
        System.out.println("Deque toString: " + deque);   // [tercero, segundo, primero]

        System.out.print("Stack for-each: ");
        for (String s : stack) { System.out.print(s + " "); }
        System.out.print("  <- del FONDO a la cima: al reves de como saldran");

        System.out.print("\nDeque for-each: ");
        for (String s : deque) { System.out.print(s + " "); }
        System.out.print("  <- de la CIMA al fondo: el orden de salida");

        System.out.println("\n\nCausa: Stack hereda el iterador de Vector, que recorre el");
        System.out.println("array del indice 0 en adelante, y en Stack el indice 0 es el FONDO.");
        System.out.println("Consecuencia: un bucle que 'procese la pila en orden' hace lo contrario.\n");
    }

    static void stackRompeLaSemantica() {
        System.out.println("=== 3. Stack expone la API de una lista ===");
        Stack<String> stack = new Stack<>();
        stack.push("A"); stack.push("B"); stack.push("C");

        System.out.println("Pila inicial: " + stack);
        System.out.println("stack.get(0):    " + stack.get(0) + "   <- acceso al FONDO");
        stack.add(1, "X");
        System.out.println("stack.add(1,X):  " + stack + "   <- insercion en MEDIO");
        stack.remove(0);
        System.out.println("stack.remove(0): " + stack + "   <- borrado del FONDO");
        stack.set(0, "Z");
        System.out.println("stack.set(0,Z):  " + stack + "   <- modificacion del FONDO");

        System.out.println("Ninguna de estas operaciones existe en Deque: la interfaz");
        System.out.println("solo ofrece los extremos, y esa restriccion ES la garantia.");
        System.out.println("Causa: 'class Stack extends Vector' es mala herencia (03-05):");
        System.out.println("una pila USA un almacenamiento, no ES un vector.\n");
    }

    static void searchBasadoEn1() {
        System.out.println("=== 4. Stack.search esta basado en 1 ===");
        Stack<String> stack = new Stack<>();
        stack.push("fondo"); stack.push("medio"); stack.push("cima");

        System.out.println("search('cima'):  " + stack.search("cima")
                           + "   <- 1, no 0: rompe la convencion de todo Java");
        System.out.println("search('fondo'): " + stack.search("fondo"));
        System.out.println("search('nada'):  " + stack.search("nada") + "   <- -1 si no esta");
        System.out.println("Deque no tiene search: usa contains (O(n)) si lo necesitas.\n");
    }

    static void rendimiento() {
        System.out.println("=== 5. Rendimiento ilustrativo ===");
        System.out.println("ADVERTENCIA: no es un benchmark riguroso. El JIT, el recolector");
        System.out.println("y la eliminacion de codigo muerto distorsionan estas cifras.");
        System.out.println("Para medir en serio, JMH (05-04).\n");

        final int N = 1_000_000;

        for (int i = 0; i < 3; i++) { ciclo(new Stack<>(), 10_000); }   // calentamiento
        for (int i = 0; i < 3; i++) { ciclo(new ArrayDeque<>(), 10_000); }

        long tStack = ciclo(new Stack<>(), N);
        long tDeque = ciclo(new ArrayDeque<>(), N);

        System.out.printf("Stack       %d push+pop: %5d ms%n", N, tStack);
        System.out.printf("ArrayDeque  %d push+pop: %5d ms%n", N, tDeque);
        System.out.println("La diferencia viene sobre todo de la sincronizacion de Vector,");
        System.out.println("que adquiere y libera un bloqueo en CADA operacion, sin servir");
        System.out.println("para nada en un programa de un solo hilo.");
    }

    static long ciclo(Deque<Integer> pila, int n) {
        long t = System.nanoTime();
        for (int i = 0; i < n; i++) { pila.push(i); }
        while (!pila.isEmpty()) { pila.pop(); }
        return (System.nanoTime() - t) / 1_000_000;
    }

    static long ciclo(Stack<Integer> pila, int n) {
        long t = System.nanoTime();
        for (int i = 0; i < n; i++) { pila.push(i); }
        while (!pila.isEmpty()) { pila.pop(); }
        return (System.nanoTime() - t) / 1_000_000;
    }
}

El apartado 2 es el más importante del ejercicio. Stack y ArrayDeque hacen lo mismo con pop, pero recorren al revés, y esa incoherencia no produce ningún error visible: simplemente da resultados equivocados. Es el argumento más contundente contra Stack, por encima incluso de la sincronización.

El apartado 3 muestra el problema de diseño de fondo: extends Vector regala a Stack cuarenta métodos que contradicen su propia semántica. Es el ejemplo canónico de por qué 03-05 insistía en preguntarse "¿es un?" antes de heredar. La respuesta correcta era composición.

Solución 3

package com.nexussoftware.bibliotech.servicio;

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

/**
 * Evaluador de expresiones en notacion polaca inversa (RPN).
 *
 * En RPN el operador va DESPUES de sus operandos, lo que elimina los
 * parentesis y permite evaluar con una sola pila:
 *   "3 4 +"             = 3 + 4          = 7
 *   "5 1 2 + 4 * + 3 -" = 5 + (1+2)*4 -3 = 14
 */
public final class EvaluadorRPN {

    private EvaluadorRPN() { }

    private static final Set<String> OPERADORES = Set.of("+", "-", "*", "/");

    public static double evaluar(String expresion) {
        if (expresion == null || expresion.isBlank()) {
            System.out.println("AVISO: expresion vacia");
            return Double.NaN;
        }

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

        for (String simbolo : expresion.trim().split("\\s+")) {
            if (OPERADORES.contains(simbolo)) {
                if (pila.size() < 2) {
                    System.out.println("AVISO: faltan operandos para '" + simbolo + "'");
                    return Double.NaN;
                }
                // ORDEN IMPORTANTE: el primero que sale es el operando DERECHO,
                // porque fue el ultimo en apilarse. Invertirlo rompe '-' y '/'.
                double derecho  = pila.pop();
                double izquierdo = pila.pop();
                Double resultado = operar(izquierdo, derecho, simbolo);
                if (resultado == null) { return Double.NaN; }
                pila.push(resultado);
            } else {
                Double numero = aNumero(simbolo);
                if (numero == null) {
                    System.out.println("AVISO: simbolo no reconocido -> '" + simbolo + "'");
                    return Double.NaN;
                }
                pila.push(numero);
            }
        }

        if (pila.size() != 1) {
            System.out.println("AVISO: expresion mal formada, quedan "
                               + pila.size() + " valores en la pila");
            return Double.NaN;
        }
        return pila.pop();
    }

    private static Double operar(double a, double b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/":
                if (b == 0) {
                    // El modulo 6 ensenara a senalarlo con una excepcion propia
                    System.out.println("AVISO: division por cero");
                    return null;
                }
                return a / b;
            default:  return null;
        }
    }

    /** Conversion sin try/catch: comprobamos el formato antes (modulo 6 lo hara mejor). */
    private static Double aNumero(String s) {
        if (!s.matches("-?\\d+(\\.\\d+)?")) { return null; }
        return Double.valueOf(s);
    }

    /** Muestra el estado de la pila tras cada simbolo. */
    public static String traza(String expresion) {
        StringBuilder sb = new StringBuilder();
        Deque<Double> pila = new ArrayDeque<>();

        sb.append(String.format("%-8s %s%n", "SIMBOLO", "PILA (cima primero)"));
        for (String simbolo : expresion.trim().split("\\s+")) {
            if (OPERADORES.contains(simbolo) && pila.size() >= 2) {
                double derecho = pila.pop();
                double izq     = pila.pop();
                Double r = operar(izq, derecho, simbolo);
                pila.push(r == null ? Double.NaN : r);
            } else {
                Double n = aNumero(simbolo);
                if (n != null) { pila.push(n); }
            }
            // El iterador de ArrayDeque va de la cima al fondo: el orden util
            sb.append(String.format("%-8s %s%n", simbolo, pila));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("3 4 +               = " + evaluar("3 4 +"));
        System.out.println("5 1 2 + 4 * + 3 -   = " + evaluar("5 1 2 + 4 * + 3 -"));

        // Multa de BiblioTech: libro devuelto el dia 20 con plazo de 15 dias,
        // tarifa 0,25 EUR/dia. En RPN: (20 - 15) * 0.25
        System.out.println("20 15 - 0.25 *      = " + evaluar("20 15 - 0.25 *")
                           + " EUR de multa");

        System.out.println("\n--- Casos invalidos ---");
        System.out.println("Resultado: " + evaluar("3 +"));
        System.out.println("Resultado: " + evaluar("3 4 5 +"));
        System.out.println("Resultado: " + evaluar("3 0 /"));
        System.out.println("Resultado: " + evaluar("3 4 %"));

        System.out.println("\n--- Traza de '5 1 2 + 4 * + 3 -' ---");
        System.out.print(traza("5 1 2 + 4 * + 3 -"));
    }
}
3 4 +               = 7.0
5 1 2 + 4 * + 3 -   = 14.0
20 15 - 0.25 *      = 1.25 EUR de multa

--- Casos invalidos ---
AVISO: faltan operandos para '+'
Resultado: NaN
AVISO: expresion mal formada, quedan 2 valores en la pila
Resultado: NaN
AVISO: division por cero
Resultado: NaN
AVISO: simbolo no reconocido -> '%'
Resultado: NaN

--- Traza de '5 1 2 + 4 * + 3 -' ---
SIMBOLO  PILA (cima primero)
5        [5.0]
1        [1.0, 5.0]
2        [2.0, 1.0, 5.0]
+        [3.0, 5.0]
4        [4.0, 3.0, 5.0]
*        [12.0, 5.0]
+        [17.0]
3        [3.0, 17.0]
-        [14.0]

La traza muestra la esencia de la estructura: la pila guarda los resultados parciales pendientes de combinar, y cada operador consume exactamente los dos últimos. Que sea LIFO es lo que garantiza que se combinen los operandos correctos: cuando llega el + de la posición 4, los dos valores en la cima (2.0 y 1.0) son precisamente los que le corresponden, y el 5.0 del fondo espera pacientemente su turno.

Dos detalles que suelen dar problemas. El orden de los operandos: el primero que sale de la pila es el operando derecho, porque fue el último en apilarse; invertirlo daría resultados correctos para + y * pero equivocados para - y /, que es la clase de bug que tarda horas en aparecer. Y la comprobación final de que queda exactamente un valor: si sobran, la expresión estaba mal formada aunque cada operación individual haya funcionado.

Este es también, en esencia, el funcionamiento de la propia JVM: su código de bytes es una máquina de pila, donde iadd desapila dos enteros y apila su suma. Evaluar 20 15 - 0.25 * con un ArrayDeque es, conceptualmente, lo mismo que hace la máquina virtual al ejecutar calcularMulta.

Conclusión

Ya dominas la tercera política de acceso del módulo. Sabes que una pila es LIFO: los elementos entran y salen por la cima con push, pop y peek, y que su propiedad esencial —invertir el orden— es lo que la hace idónea para deshacer, para analizar estructuras anidadas, para el recorrido en profundidad y para la propia ejecución de los programas.

Entiendes la pila de llamadas de la JVM: cada invocación apila un marco con parámetros, variables locales y dirección de retorno, y cada retorno lo desapila. Con eso has cerrado el círculo abierto en 03-03: el StackOverflowError es el agotamiento de esa pila, tiene tamaño fijo por hilo y es un Error, no una excepción que debas tratar; sus causas son una recursión sin caso base —un bug— o una recursión correcta pero demasiado profunda —que se resuelve con una pila explícita en el heap—.

Conoces la clase Stack y, sobre todo, por qué no debes usarla: extiende Vector, lo que es mala herencia de manual (una pila usa un almacenamiento, no es un vector) y le regala toda la API de una lista, permitiendo get(0), add(1, x) y remove(0) sobre una supuesta pila; está sincronizada con un coste que no compra seguridad real; y —el defecto más traicionero— su iterador recorre del fondo a la cima, justo al revés del orden en que saldrán los elementos, produciendo resultados equivocados sin ningún aviso. Su search basado en 1 remata el cuadro.

La respuesta correcta es Deque<X> pila = new ArrayDeque<>(): push, pop y peek como alias de las operaciones sobre la cabeza, O(1) sin bloqueos, la mejor localidad de caché, y un iterador que recorre en el orden de salida. Tienes clara la asimetría de pop() (lanza) frente a peek() (devuelve null) y las familias completas de 05-07 para elegir el comportamiento que quieras.

Has implementado una pila propia con un array y un índice, entendiendo desde dentro por qué cima apunta a la siguiente posición libre, por qué hay que poner la celda a null al desapilar —fuga de memoria— y por qué el crecimiento multiplicativo da coste amortizado O(1). Y has resuelto los dos problemas canónicos: paréntesis equilibrados, donde la pila detecta el mal anidamiento que un simple contador dejaría pasar, y deshacer/rehacer con dos pilas, incluido el detalle que casi todo el mundo olvida —una acción nueva debe vaciar la pila de rehacer—. Y sabes convertir una recursión en iteración con una pila explícita, con el truco de apilar los hijos en orden inverso para conservar el orden del recorrido.

BiblioTech tiene ahora un CatalogoConHistorial con Deque<OperacionCatalogo> que permite anular la última alta o baja, rehacerla, deshacer varias de golpe y consultar el historial en el orden correcto, con el historial acotado descartando por el fondo en O(1) —algo que solo un Deque permite—.

En la lección siguiente, Ordenación y Búsqueda en Colecciones, cierras el módulo recogiendo todos los hilos. Volverás sobre Comparable y su contrato completo —signo del resultado, antisimetría, transitividad, coherencia con equals y qué se rompe exactamente en un TreeSet cuando no lo es—, incluido el error clásico de restar enteros y desbordar. Retomarás Comparator desde 04-06 con comparing, thenComparing, reversed, nullsFirst, comparingInt y por qué esta última evita el autoboxing. Verás las cuatro estrategias de ordenación —Collections.sort, List.sort, Arrays.sort y las colecciones que se mantienen ordenadas solas—, qué significa que una ordenación sea estable y por qué importa al ordenar por criterios sucesivos, y qué algoritmos usa Java realmente: TimSort para objetos y quicksort de doble pivote para primitivos. Después, la búsqueda: lineal frente a binaria frente a clave de mapa, con la interpretación del valor negativo que devuelve binarySearch, y las utilidades de Collections que quedan por conocer. Y al final, el balance del módulo: qué es capaz de hacer BiblioTech ahora, qué sigue siendo frágil y por qué el módulo 6 es el siguiente paso inevitable.

◄ Anterior
◄
Siguiente ►
►

Curso de Programación en Java

Módulo 1: Introducción a Java

Módulo 2: Flujo de Control

Módulo 3: Programación Orientada a Objetos

Módulo 4: Programación Orientada a Objetos Avanzada

Módulo 5: Estructuras de Datos y Colecciones

Módulo 6: Manejo de Excepciones

Módulo 7: Entrada/Salida de Archivos

Módulo 8: Multihilo y Concurrencia

Módulo 9: Redes

Módulo 10: Temas Avanzados

Módulo 11: Frameworks y Librerías de Java

Módulo 12: Construcción de Aplicaciones del Mundo Real

El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados