El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Pila

Següent ►
►

A la lliçó anterior vas veure que canviar pollFirst per pollLast en una sola línia convertia un recorregut en amplada en un de profunditat. Aquesta línia tanca tota la diferència entre una cua i una pila: la cua atén qui fa més temps que espera, la pila atén l'últim que va arribar.

Una pila és LIFO: Last In, First Out. És l'estructura d'una pila de plats, d'un munt de papers en una safata, del botó "desfés" de qualsevol editor. I és, sobretot, l'estructura amb què funciona la mateixa màquina virtual de Java: cada vegada que crides un mètode, la JVM apila un marc amb les seves variables locals, i quan el mètode acaba el desapila. Aquest mecanisme —la pila de crides— explica el StackOverflowError que probablement ja has vist en equivocar-te amb una recursivitat a 03-03.

Aquesta lliçó té una particularitat: la classe que Java porta amb el nom Stack està desaconsellada, i en veuràs exactament el perquè amb una demostració que sorprèn. La forma correcta de fer servir una pila en Java modern és Deque, la interfície que ja coneixes. Acabaràs implementant una pila pròpia amb un array per entendre l'estructura des de dins, resolent dos problemes clàssics —parèntesis equilibrats i historial amb desfer i refer— i afegint a BiblioTech la pila que permet anul·lar l'última operació del catàleg.

Contingut

  1. LIFO: la semàntica d'una pila
  2. Per a què serveix realment una pila
  3. La pila de crides de la JVM i el StackOverflowError
  4. La classe Stack heretada
  5. Per què Stack està desaconsellada
  6. Deque com a pila: la recomanació oficial
  7. Taula comparativa de les tres opcions
  8. Implementar una pila pròpia amb un array
  9. Cas pràctic: parèntesis equilibrats
  10. Cas pràctic: historial amb desfer i refer
  11. De la recursivitat a la iteració amb una pila explícita
  12. Aplicació a BiblioTech
  13. Errors Habituals i Consells
  14. Exercicis

  1. LIFO: la semàntica d'una pila

Una pila (stack) és una col·lecció on els elements entren i surten pel mateix extrem, anomenat cim (top).

flowchart TB
    P["push / pop / peek"] --> C["CIM: modificacio"]
    C --> B["baixa"]
    B --> A["alta"]
    A --> F["FONS (el primer que va entrar,<br/>l'ultim que sortira)"]

Les seves tres operacions fonamentals:

Operació Què fa
push(e) Col·loca un element al cim
pop() Retira i retorna l'element del cim
peek() Consulta el cim sense retirar-lo

El comportament en una seqüència:

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("baixa:978-0000000001");

System.out.println(pila.peek());    // baixa:978-0000000001  (l'ultima que va entrar)
System.out.println(pila.pop());     // baixa:978-0000000001
System.out.println(pila.pop());     // alta:978-0000000002
System.out.println(pila.size());    // 1

L'ordre de sortida és exactament l'invers al d'entrada. I aquesta propietat —"inverteix l'ordre"— és la clau de gairebé totes les seves aplicacions: desfer una seqüència d'accions és refer-les a l'inrevés, avaluar una expressió imbricada és tancar l'últim que s'ha obert, i tornar d'una crida és reprendre la que hi havia just abans.

Compara les tres polítiques del mòdul:

Política Surt primer Metàfora Estructura
FIFO (cua) El que fa més temps que espera Cua del supermercat Queue / Deque
LIFO (pila) L'últim a arribar Pila de plats Deque
Prioritat El més urgent Urgències d'un hospital PriorityQueue

  1. Per a què serveix realment una pila

Quatre famílies d'aplicacions, i totes quatre apareixen constantment en programació real.

1. Desfer (undo). Cada acció de l'usuari s'apila; desfer és desapilar l'última i revertir-la. Si a més apiles les accions desfetes en una segona pila, tens refer de franc. Ho implementaràs a l'apartat 10.

2. Avaluació d'expressions i anàlisi sintàctica. Qualsevol estructura imbricada —parèntesis, claus, etiquetes HTML, blocs de codi— es valida i es processa amb una pila: cada obertura s'apila i cada tancament ha de correspondre amb el cim. Els compiladors, inclòs el de Java, fan servir piles per analitzar el codi font. És l'apartat 9.

3. Recorregut en profunditat (DFS). Com vas veure a 05-07, substituir la cua per una pila converteix un recorregut en amplada en un de profunditat. La pila manté "per on anava" mentre l'algorisme baixa per una branca.

4. La pila de crides de la JVM. No és una aplicació que programis: és com funciona el llenguatge. I mereix el seu propi apartat.

  1. La pila de crides de la JVM i el StackOverflowError

Cada fil d'una aplicació Java té la seva pròpia pila de crides (call stack). Cada vegada que s'invoca un mètode, la JVM apila un marc de pila (stack frame) que conté:

  • Els paràmetres del mètode.
  • Les seves variables locals.
  • L'adreça de retorn: a quina instrucció tornar quan acabi.

Quan el mètode acaba, el seu marc es desapila i l'execució continua on s'havia quedat qui l'havia cridat.

public class Traca {
    public static void main(String[] args) {
        System.out.println(calcularMulta(20, 15, 0.25));
    }
    static double calcularMulta(int dies, int termini, double tarifa) {
        return aplicarSostre(diesRetard(dies, termini) * tarifa);
    }
    static int diesRetard(int dies, int termini) { return Math.max(0, dies - termini); }
    static double aplicarSostre(double multa) { return Math.min(multa, 20.0); }
}
flowchart TB
    subgraph pila["Pila de crides en el moment d'executar diesRetard"]
        F3["diesRetard(20, 15)<br/>← CIM"]
        F2["calcularMulta(20, 15, 0.25)"]
        F1["main(args)<br/>← FONS"]
    end
    F3 --> F2 --> F1

Quan diesRetard retorna 5, el seu marc es desapila i l'execució torna a calcularMulta, que apila llavors el marc d'aplicarSostre. És exactament una pila: l'últim que s'apila és el primer que es retira.

I ara l'error que connecta amb 03-03. La pila d'un fil té una mida limitada (típicament 512 KB o 1 MB). Si hi apiles massa marcs —normalment per una recursivitat sense cas base o massa profunda—, s'esgota:

static int comptarSenseFi(int n) {
    return comptarSenseFi(n + 1);    // no para mai: cada crida apila un marc
}
// Exception in thread "main" java.lang.StackOverflowError

StackOverflowError és un Error, no una Exception: assenyala una fallada de l'entorn d'execució, no una condició que el teu programa hagi de tractar. Les seves dues causes típiques:

  • Recursivitat sense cas base o amb un cas base inabastable. És un bug: corregeix l'algorisme.
  • Recursivitat correcta però massa profunda per a la mida de la pila. Amb uns 10 000 nivells ja sol saltar. La solució és convertir la recursivitat en iteració amb una pila explícita, que és exactament el que faràs a l'apartat 11.

La diferència entre la pila de crides i una pila que crees tu és substancial: la primera viu en una zona de memòria reservada per fil i de mida fixa; la segona és un objecte normal al heap, que creix mentre hi hagi memòria. D'aquí que una recursivitat d'un milió de nivells peti i la seva equivalent iterativa amb ArrayDeque funcioni sense problemes. La memòria, el recol·lector i el -Xss que ajusta la mida de la pila són temes del mòdul 10-07.

  1. La classe Stack heretada

Java porta des de la versió 1.0 una classe anomenada literalment Stack:

import java.util.Stack;

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

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

La seva API:

Mètode Què fa Si és buida
push(e) Apila —
pop() Desapila i retorna EmptyStackException
peek() Consulta el cim EmptyStackException
empty() És buida? —
search(o) Distància des del cim (1 per al cim), o -1 —

Dos detalls cridaners ja en aquesta taula. empty() en lloc d'isEmpty() (encara que també existeix el segon, heretat). I search retorna una posició basada en 1, no en 0, cosa que trenca la convenció de tota la resta de Java.

Sobre EmptyStackException: és una RuntimeException que es llança en fer pop o peek sobre una pila buida. Com capturar-la és el mòdul 6; aquí n'hi ha prou de comprovar isEmpty() abans.

  1. Per què Stack està desaconsellada

La documentació oficial del JDK ho diu sense embuts: "Un conjunt més complet i coherent d'operacions LIFO el proporciona la interfície Deque, que s'hauria de fer servir amb preferència a aquesta classe". Les raons són tres, i la tercera és espectacular.

Raó 1: estén Vector

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

Vector és una llista amb accés per índex. En heretar-ne, Stack exposa tota l'API d'una llista, trencant la mateixa semàntica de pila:

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

// Tot aixo COMPILA i funciona sobre una "pila":
pila.get(0);              // acces per index
pila.add(1, "X");         // inserir al mig
pila.remove(0);           // eliminar del fons
pila.set(0, "Z");         // modificar el fons

Una pila que permet tocar el fons no és una pila: és una llista amb tres mètodes extra. I aquí no hi ha cap garantia estructural per protegir. És, a més, un exemple de manual de mal ús de l'herència, just l'error que vas estudiar a 03-05: Stack no és un Vector; una pila fa servir un emmagatzematge intern. Hauria d'haver estat composició.

Raó 2: està sincronitzada

Vector sincronitza tots els seus mètodes, així que Stack també. Això significa que cada push i cada pop adquireixen i alliberen un bloqueig, fins i tot en un programa d'un sol fil on no serveix absolutament de res.

I el cost no compra seguretat real: la sincronització mètode a mètode no fa atòmiques les seqüències compostes. Aquest codi continua tenint una condició de cursa:

if (!pila.isEmpty()) {        // un altre fil pot buidar-la justament aqui
    String x = pila.pop();    // EmptyStackException
}

És exactament la mateixa història d'Hashtable i Vector que vas veure a 05-05: sincronització global de Java 1.0, que surt cara i no resol el problema. Per a concurrència real, el mòdul 8.

Raó 3: l'iterador recorre a l'inrevés del que s'espera

Aquesta és la que més sorprèn, i mereix veure's executada.

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

Stack<String> stack = new Stack<>();
stack.push("primer");
stack.push("segon");
stack.push("tercer");      // el CIM

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("primer");
deque.push("segon");
deque.push("tercer");      // el CIM

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: [primer, segon, tercer]
Stack for-each: primer segon tercer
Deque toString: [tercer, segon, primer]
Deque for-each: tercer segon primer
Stack.pop(): tercer
Deque.pop(): tercer

Stack recorre del fons al cim: l'ordre invers al qual sortiran els elements. Com que hereta l'iterador de Vector, recorre l'array intern de la posició 0 endavant, i a Stack la posició 0 és el fons. Així que pop() retorna "tercer" però l'iterador comença per "primer".

ArrayDeque fa el correcte: recorre des del cim, en el mateix ordre en què sortirien els elements.

És una incoherència greu, perquè escriure un bucle que "processi la pila en ordre" produeix el resultat contrari a l'esperat, sense cap avís.

flowchart TB
    subgraph S["Stack: iterador del FONS al CIM"]
        direction TB
        S1["primer (fons) ← comenca aqui"]
        S2["segon"]
        S3["tercer (cim) ← surt primer amb pop"]
        S1 --> S2 --> S3
    end
    subgraph D["ArrayDeque: iterador del CIM al FONS"]
        direction TB
        D3["tercer (cim) ← comenca aqui, i surt primer"]
        D2["segon"]
        D1["primer (fons)"]
        D3 --> D2 --> D1
    end

El veredicte

Stack no està formalment marcada com a obsoleta —això trencaria massa codi antic—, però no s'ha de fer servir en codi nou. Només la faràs servir si te la trobes en un projecte heretat.

  1. Deque com a pila: la recomanació oficial

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

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

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

Els tres mètodes de pila són àlies d'operacions sobre el cap del Deque:

Mètode de pila Equival a Comportament si és buida
push(e) addFirst(e) —
pop() removeFirst() NoSuchElementException
peek() peekFirst() Retorna null

Fixa't en l'asimetria de l'última columna, que cal tenir present: pop() llança excepció però peek() retorna null. Si vols consistència, tens les dues famílies completes de 05-07: pollFirst() retorna null en lloc de llançar, i getFirst() llança en lloc de retornar null.

Un patró segur per consumir una pila sencera:

// Opcio 1: comprovar abans
while (!pila.isEmpty()) {
    processar(pila.pop());
}

// Opcio 2: l'idioma de 05-07, sense comprovacio previa
String op;
while ((op = pila.pollFirst()) != null) {
    processar(op);
}

Per què el cim és el cap del Deque i no la cua? Per rendiment: en un ArrayDeque, inserir i extreure pel cap és O(1) gràcies a l'array circular, igual que pel final. I push/pop sobre el cap permeten que l'iterador recorri en l'ordre de sortida, que és el que corregeix el defecte de Stack.

Declaració recomanada:

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

No ArrayDeque<String> pila, ni Stack<String> pila. La interfície Deque documenta la intenció i permet canviar la implementació.

  1. Taula comparativa de les tres opcions

Aspecte Stack ArrayDeque com a pila LinkedList com a pila
Estructura interna Vector (array sincronitzat) Array circular Nodes enllaçats
push / pop O(1), amb bloqueig O(1) sense bloqueig O(1)
Sincronitzada Sí (cost inútil) No No
Ordre de l'iterador Fons → cim (malament) Cim → fons (bé) Cim → fons
Exposa API de llista Sí (get, add(i,e)) No Sí (és una List)
Memòria per element ~4-8 bytes ~4-8 bytes ~28 bytes
Localitat de memòria cau Bona Excel·lent Dolenta
Admet null Sí No Sí
En fer pop buida EmptyStackException NoSuchElementException NoSuchElementException
Recomanada No Sí Només si necessites null o List

Conclusió: Deque<X> pila = new ArrayDeque<>(). És la resposta correcta llevat que necessitis emmagatzemar null (llavors LinkedList) o estiguis en codi heretat que ja fa servir Stack.

  1. Implementar una pila pròpia amb un array

Implementar una pila a mà és un exercici curt que aclareix l'estructura definitivament. Tot el que cal és un array i un índex.

package com.nexussoftware.bibliotech.servei;

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

/**
 * Pila de cadenes implementada sobre un array, amb finalitats didactiques.
 * Es, en essencia, el que fan ArrayDeque i Stack per dins.
 */
public class PilaArray {

    private static final int CAPACITAT_INICIAL = 10;

    private String[] elements;
    private int      cim;       // index de la SEGUENT posicio lliure = nombre d'elements

    public PilaArray() {
        this(CAPACITAT_INICIAL);
    }

    public PilaArray(int capacitatInicial) {
        this.elements = new String[Math.max(capacitatInicial, 1)];
        this.cim = 0;
    }

    /** Apila. O(1) amortitzat: nomes copia quan l'array s'omple. */
    public void push(String element) {
        if (cim == elements.length) {
            // Creixement MULTIPLICATIU (x2), igual que ArrayList (05-03):
            // es el que fa que el cost mitja per push sigui constant.
            elements = Arrays.copyOf(elements, elements.length * 2);
        }
        elements[cim] = element;
        cim++;
    }

    /** Desapila. O(1). */
    public String pop() {
        if (isEmpty()) {
            // El modul 6 ensenya a tractar aixo; aqui nomes ho assenyalem.
            throw new EmptyStackException();
        }
        cim--;
        String element = elements[cim];
        elements[cim] = null;        // IMPRESCINDIBLE: si no, l'objecte no es pot
                                     // recollir mentre la pila visqui (fuita de memoria).
        return element;
    }

    /** Consulta el cim sense retirar-lo. O(1). */
    public String peek() {
        if (isEmpty()) { throw new EmptyStackException(); }
        return elements[cim - 1];        // cim apunta a la SEGUENT lliure
    }

    /** Versio segura: null en lloc d'excepcio. */
    public String peekOrNull() {
        return isEmpty() ? null : elements[cim - 1];
    }

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

    public void clear() {
        Arrays.fill(elements, 0, cim, null);     // allibera totes les referencies
        cim = 0;
    }

    /** Recorre del CIM al FONS: l'ordre de sortida, com ha de ser. */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = cim - 1; i >= 0; i--) {      // cap enrere: del cim al fons
            sb.append(elements[i]);
            if (i > 0) { sb.append(", "); }
        }
        return sb.append("]").toString();
    }
}

Ús:

PilaArray pila = new PilaArray(2);        // capacitat petita per forcar el creixement
pila.push("alta:978-0000000001");
pila.push("alta:978-0000000002");
pila.push("baixa:978-0000000001");        // aqui l'array es duplica

System.out.println(pila);                 // [baixa:978-0000000001, alta:..002, alta:..001]
System.out.println("Cim:    " + pila.peek());
System.out.println("Trec:   " + pila.pop());
System.out.println("Queden: " + pila.size());

Tres detalls d'aquesta implementació mereixen atenció, perquè són exactament els que apareixen al codi real del JDK:

  1. cim apunta a la posició lliure següent, així que coincideix amb el nombre d'elements i peek() ha de mirar a cim - 1. L'alternativa —que apunti a l'últim element i valgui -1 quan és buida— també funciona, però obliga a més ajustos.
  2. elements[cim] = null a pop. Sense aquesta línia, l'array continuaria referint-se a un objecte que ja no forma part de la pila, impedint que el recol·lector l'alliberi: una fuita de memòria silenciosa. És la mateixa cura que vas prendre al CatalegArray de 05-01 i que ArrayList aplica al seu remove.
  3. El creixement és multiplicatiu, cosa que dona cost amortitzat O(1) per la mateixa raó que a ArrayList (05-03).

Compara-la amb el que guanyes fent servir ArrayDeque: genèrics, comprovació de nuls, iterador correcte, descendingIterator, contains, removeIf, toArray, i vint-i-cinc anys de proves. La implementació pròpia és per aprendre, no per a producció.

  1. Cas pràctic: parèntesis equilibrats

És el problema canònic de piles i apareix en qualsevol analitzador sintàctic. Donada una cadena amb (, [ i {, comprovar si estan correctament oberts i tancats.

La idea: cada símbol d'obertura s'apila. Cada símbol de tancament ha de correspondre amb el del cim; si correspon, es desapila. Al final la pila ha de quedar buida.

package com.nexussoftware.bibliotech.servei;

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

public final class ValidadorExpressions {

    private ValidadorExpressions() { }

    /** Cada tancament, amb la seva obertura corresponent. */
    private static final Map<Character, Character> PARELLES =
        Map.of(')', '(', ']', '[', '}', '{');

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

        for (char c : expressio.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                pila.push(c);                       // obertura: s'apila
            } else if (PARELLES.containsKey(c)) {
                // tancament: el cim HA DE SER la seva obertura corresponent
                if (pila.isEmpty() || pila.pop() != PARELLES.get(c)) {
                    return false;
                }
            }
            // qualsevol altre caracter s'ignora
        }
        // Si sobra alguna obertura sense tancar, la pila no es buida
        return pila.isEmpty();
    }

    /** Versio que a mes informa d'ON esta el problema. */
    public static String diagnosticar(String expressio) {
        if (expressio == null) { return "OK (cadena nulla)"; }
        Deque<Character> simbols   = new ArrayDeque<>();
        Deque<Integer>   posicions = new ArrayDeque<>();   // pila parallela de posicions

        for (int i = 0; i < expressio.length(); i++) {
            char c = expressio.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                simbols.push(c);
                posicions.push(i);
            } else if (PARELLES.containsKey(c)) {
                if (simbols.isEmpty()) {
                    return String.format("Tancament '%c' sense obertura a la posicio %d", c, i);
                }
                char esperada = PARELLES.get(c);
                char oberta   = simbols.pop();
                int  posOberta = posicions.pop();
                if (oberta != esperada) {
                    return String.format(
                        "S'esperava tancar '%c' (obert a %d) pero s'ha trobat '%c' a %d",
                        oberta, posOberta, c, i);
                }
            }
        }
        if (!simbols.isEmpty()) {
            return String.format("Falta tancar '%c' obert a la posicio %d",
                                 simbols.peek(), posicions.peek());
        }
        return "OK";
    }

    public static void main(String[] args) {
        String[] casos = {
            "(titol AND autor)",
            "((titol OR isbn) AND (any > 2000))",
            "[tipus=Llibre] AND {tarifa<0.30}",
            "(titol AND autor",
            "titol AND autor)",
            "([tipus=Llibre)]",
            ""
        };
        for (String cas : casos) {
            System.out.printf("%-38s %-5s  %s%n",
                    "\"" + cas + "\"",
                    estaEquilibrada(cas) ? "OK" : "MAL",
                    diagnosticar(cas));
        }
    }
}
"(titol AND autor)"                    OK     OK
"((titol OR isbn) AND (any > 2000))"   OK     OK
"[tipus=Llibre] AND {tarifa<0.30}"     OK     OK
"(titol AND autor"                     MAL    Falta tancar '(' obert a la posicio 0
"titol AND autor)"                     MAL    Tancament ')' sense obertura a la posicio 15
"([tipus=Llibre)]"                     MAL    S'esperava tancar '[' (obert a 1) pero s'ha trobat ')' a 14
""                                     OK     OK

Per què només funciona amb una pila. L'imbricament correcte exigeix que l'últim símbol obert sigui el primer a tancar-se: això és LIFO literalment. Amb un comptador simple, ([)] passaria la validació —hi ha dues obertures i dos tancaments—, però està mal imbricat. La pila ho detecta perquè recorda què s'ha obert i en quin ordre.

Fixa't també en la tècnica de les dues piles paral·leles de diagnosticar: una guarda els símbols i l'altra les seves posicions, i totes dues s'apilen i es desapilen alhora. És un recurs habitual quan necessites arrossegar informació addicional per cada nivell; l'alternativa, en Java modern, seria una pila d'un record Obertura(char simbol, int posicio).

  1. Cas pràctic: historial amb desfer i refer

El segon patró clàssic: dues piles, una per desfer i una altra per refer.

flowchart LR
    A["Accio nova"] --> D["Pila DESFER"]
    D -->|desfer| R["Pila REFER"]
    R -->|refer| D
    A -.->|"l'accio nova<br/>BUIDA la pila de refer"| X["refer: buida"]

La mecànica:

  • Acció nova: s'apila a desfer i es buida la pila de refer (ja no té sentit refer un futur que ha canviat).
  • Desfer: es desapila de desfer, es reverteix i s'apila a refer.
  • Refer: es desapila de refer, es reaplica i s'apila a desfer.
package com.nexussoftware.bibliotech.servei;

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

/** Historial de navegacio amb desfer i refer, amb dues piles. */
public class HistorialNavegacio {

    private final Deque<String> enrere   = new ArrayDeque<>();
    private final Deque<String> endavant = new ArrayDeque<>();
    private String actual;

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

    /** Navegar a una pagina nova invalida tot l'"endavant". */
    public void visitar(String pagina) {
        if (pagina == null || pagina.equals(actual)) { return; }
        enrere.push(actual);
        actual = pagina;
        endavant.clear();      // ja no hi ha futur per refer
    }

    /** Desfer: l'actual passa a "endavant" i es recupera l'anterior. */
    public String enrere() {
        if (enrere.isEmpty()) { return actual; }    // res per desfer
        endavant.push(actual);
        actual = enrere.pop();
        return actual;
    }

    /** Refer: l'actual torna a "enrere" i es recupera la seguent. */
    public String endavant() {
        if (endavant.isEmpty()) { return actual; }
        enrere.push(actual);
        actual = endavant.pop();
        return actual;
    }

    public String  actual()          { return actual; }
    public boolean potAnarEnrere()   { return !enrere.isEmpty(); }
    public boolean potAnarEndavant() { return !endavant.isEmpty(); }

    /**
     * Historial visible, de la mes recent a la mes antiga.
     * L'iterador d'ArrayDeque ja recorre del cim al fons, que es
     * exactament l'ordre que volem. Amb Stack caldria invertir-lo.
     */
    public List<String> historialEnrere() {
        return new ArrayList<>(enrere);
    }

    public String barraEstat() {
        return String.format("%s %s %s  |  %s",
                potAnarEnrere()   ? "<" : "-",
                actual,
                potAnarEndavant() ? ">" : "-",
                enrere.isEmpty() ? "(inici)" : "enrere: " + enrere.peek());
    }
}

Ús:

HistorialNavegacio h = new HistorialNavegacio("cataleg");
h.visitar("cataleg/llibres");
h.visitar("cataleg/llibres/978-0000000001");
h.visitar("prestecs/marta-ruiz");

System.out.println(h.barraEstat());
System.out.println("Enrere -> " + h.enrere());
System.out.println("Enrere -> " + h.enrere());
System.out.println("Endavant -> " + h.endavant());
System.out.println("Historial: " + h.historialEnrere());

h.visitar("informes/multes");            // pagina NOVA: es perd l'"endavant"
System.out.println("Pot anar endavant: " + h.potAnarEndavant());
< prestecs/marta-ruiz -  |  enrere: cataleg/llibres/978-0000000001
Enrere -> cataleg/llibres/978-0000000001
Enrere -> cataleg/llibres
Endavant -> cataleg/llibres/978-0000000001
Historial: [cataleg/llibres, cataleg]
Pot anar endavant: false

Aquest és exactament el comportament dels botons "enrere" i "endavant" de qualsevol navegador, i de "desfés/refés" de qualsevol editor. I observa el detall d'historialEnrere(): l'iterador d'ArrayDeque ja retorna la llista en l'ordre correcte —de la més recent a la més antiga—, cosa que amb Stack caldria invertir a mà pel que vas veure a l'apartat 5.

  1. De la recursivitat a la iteració amb una pila explícita

Tota funció recursiva es pot convertir en iterativa fent servir una pila, perquè la recursivitat no és res més que l'ús implícit de la pila de crides de la JVM. Fer aquesta pila explícita elimina el risc de StackOverflowError, perquè la pila explícita viu al heap.

Un exemple concret: recórrer un arbre de categories del catàleg i acumular totes les referències.

package com.nexussoftware.bibliotech.servei;

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

/** Categoria del cataleg que pot contenir subcategories. */
class Categoria {
    private final String nom;
    private final List<Categoria> subcategories = new ArrayList<>();
    private final List<String>    referencies   = new ArrayList<>();

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

    Categoria afegirSub(Categoria c) { subcategories.add(c); return this; }
    Categoria afegirRef(String r)    { referencies.add(r);   return this; }

    String getNom()                   { return nom; }
    List<Categoria> getSubcategories(){ return subcategories; }
    List<String>    getReferencies()  { return referencies; }
}

public final class RecorregutCategories {

    private RecorregutCategories() { }

    /**
     * Versio RECURSIVA. Clara i curta, pero cada nivell apila un marc
     * a la pila de la JVM: amb un arbre molt profund, StackOverflowError.
     */
    public static List<String> recursiu(Categoria arrel) {
        List<String> resultat = new ArrayList<>();
        recollir(arrel, resultat);
        return resultat;
    }

    private static void recollir(Categoria c, List<String> acumulador) {
        if (c == null) { return; }
        acumulador.addAll(c.getReferencies());
        for (Categoria sub : c.getSubcategories()) {
            recollir(sub, acumulador);             // crida recursiva
        }
    }

    /**
     * Versio ITERATIVA amb pila EXPLICITA. Fa exactament el mateix,
     * pero la pila viu al heap: suporta arbres de qualsevol profunditat.
     */
    public static List<String> iteratiu(Categoria arrel) {
        List<String> resultat = new ArrayList<>();
        if (arrel == null) { return resultat; }

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

        while (!pila.isEmpty()) {
            Categoria actual = pila.pop();          // LIFO -> recorregut en PROFUNDITAT
            resultat.addAll(actual.getReferencies());

            // Apilem les subcategories EN ORDRE INVERS perque la primera
            // es processi primer: la pila inverteix l'ordre, aixi que
            // invertir-lo en apilar el deixa com a la versio recursiva.
            List<Categoria> subs = actual.getSubcategories();
            for (int i = subs.size() - 1; i >= 0; i--) {
                pila.push(subs.get(i));
            }
        }
        return resultat;
    }

    public static void main(String[] args) {
        Categoria arrel = new Categoria("Tecnica");
        Categoria java = new Categoria("Java")
                .afegirRef("978-0000000001")
                .afegirRef("REV-2024-03");
        Categoria disseny = new Categoria("Disseny")
                .afegirRef("978-0000000002")
                .afegirSub(new Categoria("Refactoritzacio")
                        .afegirRef("978-0000000003")
                        .afegirRef("DVD-0007"));
        arrel.afegirSub(java).afegirSub(disseny);

        System.out.println("Recursiu: " + recursiu(arrel));
        System.out.println("Iteratiu: " + iteratiu(arrel));
        System.out.println("Iguals:   " + recursiu(arrel).equals(iteratiu(arrel)));
    }
}
Recursiu: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Iteratiu: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Iguals:   true

Dues observacions importants:

El truc de l'ordre invers en apilar. Com que la pila inverteix, apilar les subcategories d'esquerra a dreta les processaria de dreta a esquerra. Apilar-les a l'inrevés compensa aquesta inversió i reprodueix exactament l'ordre de la versió recursiva. És un detall que s'oblida sovint i produeix recorreguts correctes però en ordre inesperat.

Quan fer aquesta conversió. La versió recursiva és més llegible i ha de ser l'opció per defecte. Converteix a iterativa només quan la profunditat pugui ser gran —estructures de dades que venen de fora, arbres de directoris molt imbricats, grafs amb milers de nivells— o quan necessitis controlar el recorregut (pausar-lo, reprendre'l, limitar-lo).

I compara amb 05-07: si a iteratiu canviessis la pila per una cua (pollFirst en lloc de pop), tindries un recorregut en amplada. Mateixa estructura de codi, dos algorismes.

  1. Aplicació a BiblioTech

La pila de desfer del catàleg, que permet anul·lar l'última alta o baixa.

Primer, modelem l'operació. Fem servir un record (04-07) perquè és una dada immutable, i un enum per al tipus:

package com.nexussoftware.bibliotech.domini;

/** Operacio reversible sobre el cataleg. */
public record OperacioCataleg(Tipus tipus, Material material, int dia) {

    public enum Tipus {
        ALTA("Alta de material"),
        BAIXA("Baixa de material");

        private final String descripcio;
        Tipus(String descripcio) { this.descripcio = descripcio; }
        public String getDescripcio() { return descripcio; }

        /** L'operacio contraria: el que cal fer per desfer aquesta. */
        public Tipus inversa() {
            return (this == ALTA) ? BAIXA : ALTA;
        }
    }

    public OperacioCataleg {
        if (tipus == null)    { tipus = Tipus.ALTA; }
        if (dia   < 0)        { dia = 0; }
    }

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

I el catàleg amb historial reversible:

package com.nexussoftware.bibliotech.servei;

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.domini.Material;
import com.nexussoftware.bibliotech.domini.OperacioCataleg;

/**
 * Cataleg amb pila de desfer i refer.
 *
 * Deque<OperacioCataleg> sobre ArrayDeque: push/pop en O(1), iterador
 * que recorre de la mes recent a la mes antiga (el que volem per
 * mostrar l'historial) i sense la sincronitzacio inutil de Stack.
 */
public class CatalegAmbHistorial {

    private static final int MAXIM_HISTORIAL = 50;

    private final Map<String, Material> perReferencia = new HashMap<>();
    private final Deque<OperacioCataleg> desfer = new ArrayDeque<>();
    private final Deque<OperacioCataleg> refer  = new ArrayDeque<>();

    /** Alta: registra l'operacio a la pila de desfer. */
    public boolean donarDeAlta(Material m, int dia) {
        if (m == null || perReferencia.containsKey(m.getReferencia())) { return false; }
        perReferencia.put(m.getReferencia(), m);
        registrar(new OperacioCataleg(OperacioCataleg.Tipus.ALTA, m, dia));
        return true;
    }

    /** Baixa: idem. */
    public boolean donarDeBaixa(String referencia, int dia) {
        Material m = perReferencia.remove(referencia);
        if (m == null) { return false; }
        registrar(new OperacioCataleg(OperacioCataleg.Tipus.BAIXA, m, dia));
        return true;
    }

    private void registrar(OperacioCataleg op) {
        desfer.push(op);
        refer.clear();                     // una operacio nova invalida el "refer"
        // Acotem l'historial descartant pel FONS: nomes un Deque permet aixo en O(1)
        if (desfer.size() > MAXIM_HISTORIAL) {
            desfer.pollLast();
        }
    }

    /** Anulla l'ultima operacio. Retorna null si no n'hi havia cap. */
    public OperacioCataleg desfer() {
        OperacioCataleg op = desfer.poll();         // poll: null si es buida
        if (op == null) { return null; }
        aplicarInversa(op);
        refer.push(op);
        return op;
    }

    /** Torna a aplicar l'ultima operacio desfeta. */
    public OperacioCataleg refer() {
        OperacioCataleg op = refer.poll();
        if (op == null) { return null; }
        aplicar(op);
        desfer.push(op);
        return op;
    }

    private void aplicar(OperacioCataleg op) {
        switch (op.tipus()) {          // switch sobre enum, sense default: exhaustiu (04-07)
            case ALTA  -> perReferencia.put(op.material().getReferencia(), op.material());
            case BAIXA -> perReferencia.remove(op.material().getReferencia());
        }
    }

    private void aplicarInversa(OperacioCataleg op) {
        switch (op.tipus().inversa()) {
            case ALTA  -> perReferencia.put(op.material().getReferencia(), op.material());
            case BAIXA -> perReferencia.remove(op.material().getReferencia());
        }
    }

    /** Desfa les N ultimes operacions. */
    public int desferDiverses(int quantes) {
        int fetes = 0;
        for (int i = 0; i < quantes && desfer() != null; i++) { fetes++; }
        return fetes;
    }

    /** Historial de la mes recent a la mes antiga: l'ordre de l'iterador d'ArrayDeque. */
    public List<OperacioCataleg> historial() {
        return new ArrayList<>(desfer);
    }

    public OperacioCataleg ultimaOperacio() { return desfer.peek(); }
    public boolean potDesfer()              { return !desfer.isEmpty(); }
    public boolean potRefer()               { return !refer.isEmpty(); }
    public int     mida()                   { return perReferencia.size(); }
    public Material cercar(String referencia) { return perReferencia.get(referencia); }
}

Ús:

CatalegAmbHistorial cataleg = new CatalegAmbHistorial();

Material javaEficac    = new Llibre("Java Eficac",        "Joshua Bloch",  "978-0000000001", 2018);
Material patrons       = new Llibre("Patrons de Disseny", "Erich Gamma",   "978-0000000002", 1994);
Material refactoritzar = new Llibre("Refactoritzacio",    "Martin Fowler", "978-0000000003", 1999);
Material revista       = new Revista("Java Magazine",     "REV-2024-03",   42, "Mensual");

cataleg.donarDeAlta(javaEficac,    100);
cataleg.donarDeAlta(patrons,       101);
cataleg.donarDeAlta(refactoritzar, 102);
cataleg.donarDeAlta(revista,       103);
cataleg.donarDeBaixa("978-0000000002", 105);     // baixa de Patrons de Disseny

System.out.println("Materials: " + cataleg.mida());
System.out.println("Ultima operacio: " + cataleg.ultimaOperacio());

System.out.println("\n--- Desfent ---");
System.out.println("Desfet: " + cataleg.desfer());
System.out.println("Materials: " + cataleg.mida()
                   + "  (Patrons ha tornat: " + (cataleg.cercar("978-0000000002") != null) + ")");

System.out.println("\n--- Refent ---");
System.out.println("Refet: " + cataleg.refer());
System.out.println("Materials: " + cataleg.mida());

System.out.println("\n--- Desfent tres operacions ---");
System.out.println("Desfetes: " + cataleg.desferDiverses(3));
System.out.println("Materials: " + cataleg.mida());

System.out.println("\n--- Historial pendent (mes recent primer) ---");
cataleg.historial().forEach(op -> System.out.println("  " + op));
Materials: 3
Ultima operacio: Baixa de material de 'Patrons de Disseny' (978-0000000002) el dia 105

--- Desfent ---
Desfet: Baixa de material de 'Patrons de Disseny' (978-0000000002) el dia 105
Materials: 4  (Patrons ha tornat: true)

--- Refent ---
Refet: Baixa de material de 'Patrons de Disseny' (978-0000000002) el dia 105
Materials: 3

--- Desfent tres operacions ---
Desfetes: 3
Materials: 2

--- Historial pendent (mes recent primer) ---
  Alta de material de 'Patrons de Disseny' (978-0000000002) el dia 101
  Alta de material de 'Java Eficac' (978-0000000001) el dia 100

Tres decisions de disseny que val la pena assenyalar. registrar acota l'historial descartant pel fons amb pollLast(): això és O(1) només perquè un Deque obre els dos extrems —amb una pila pura caldria buidar-la i reconstruir-la—. El switch sobre l'enum no porta default, així que si demà hi afegeixes un tipus d'operació el compilador et portarà als dos punts que cal actualitzar (04-07). I historial() aprofita que l'iterador d'ArrayDeque recorre del cim al fons, lliurant la llista en l'ordre que espera l'usuari.

Errors Habituals i Consells

Fer servir java.util.Stack en codi nou. Estén Vector, està sincronitzada innecessàriament, exposa l'API d'una llista sobre una pila i el seu iterador recorre del fons al cim, a l'inrevés de com surten els elements. Fes servir Deque<X> pila = new ArrayDeque<>().

Recórrer una Stack amb for-each esperant l'ordre de sortida. Retorna l'ordre invers. Amb ArrayDeque l'iterador sí que va del cim al fons.

pop() sobre una pila buida. Llança NoSuchElementException a ArrayDeque i EmptyStackException a Stack. Comprova isEmpty() abans, o fes servir pollFirst(), que retorna null.

Confondre l'asimetria de push/pop/peek a Deque. pop() llança excepció, però peek() retorna null. Si vols coherència, fes servir les famílies completes: pollFirst/peekFirst (retornen null) o removeFirst/getFirst (llancen).

Inserir null en un ArrayDeque. NullPointerException, igual que a les cues: null està reservat com a senyal de "buida".

Oblidar posar a null la cel·la alliberada en implementar una pila pròpia. L'array continua referint-se a l'objecte desapilat i impedeix que es reculli: fuita de memòria.

Oblidar buidar la pila de refer en registrar una acció nova. Refer un futur que ja no existeix produeix estats incoherents. És l'error més freqüent en implementar desfer/refer.

Oblidar invertir l'ordre en apilar fills en un recorregut en profunditat. La pila inverteix, així que apilar en ordre natural els processa a l'inrevés. Apila'ls en ordre invers si vols reproduir l'ordre de la versió recursiva.

Confondre la pila de crides amb una pila de dades. La primera és memòria reservada per fil, de mida fixa, i el seu esgotament produeix StackOverflowError. La segona és un objecte del heap i creix mentre hi hagi memòria. Per això convertir una recursivitat profunda en iteració amb ArrayDeque resol el problema.

Consell: si el problema esmenta "l'últim", "desfer", "imbricat" o "tornar enrere", és una pila. Igual que "per ordre d'arribada" era una cua i "sense repetits" era un Set, l'enunciat sol dir l'estructura.

Consell: Deque és la interfície més rendible del Framework. Amb una sola implementació —ArrayDeque— tens cua FIFO, pila LIFO i cua de doble extrem, tot en O(1) i amb la millor localitat de memòria cau.

Exercicis

Exercici 1: pila de desfer per a préstecs

Amplia BiblioTech amb GestorPrestecsReversible que mantingui una pila de les últimes operacions de préstec i devolució, permetent anul·lar-les:

  • Crea un record OperacioPrestec(Tipus tipus, Prestec prestec, int dia) amb enum Tipus { PRESTEC, DEVOLUCIO }.
  • void prestar(Prestec p, int dia) i void retornar(Prestec p, int dia), que registrin l'operació.
  • OperacioPrestec desfer(): reverteix l'última (un préstec desfet retorna el material; una devolució desfeta el torna a marcar com a prestat).
  • List<OperacioPrestec> ultimes(int quantes): sense buidar la pila.
  • int desferFinsA(int dia): desfà totes les operacions posteriors a aquell dia.
  • Limita l'historial a 20 operacions descartant les més antigues.

Exercici 2: Stack enfront d'ArrayDeque

Escriu ComparativaPiles amb un main que demostri, imprimint i explicant cada punt:

  1. Que Stack i ArrayDeque donen el mateix resultat amb push/pop/peek.
  2. Que els seus iteradors i els seus toString recorren en ordres oposats, i per què.
  3. Que Stack permet operacions de llista que trenquen la semàntica de pila (get(0), add(1, x), remove(0)), i que ArrayDeque no les ofereix.
  4. Que Stack.search retorna una posició basada en 1.
  5. Una mesura il·lustrativa d'un milió de push/pop a totes dues, amb l'advertiment sobre JMH.

Exercici 3: avaluador d'expressions en notació polonesa inversa

La notació polonesa inversa (RPN) col·loca l'operador després dels seus operands: 3 4 + és 3 + 4, i 5 1 2 + 4 * + 3 - és 5 + ((1+2)*4) - 3 = 14. La seva gran virtut és que no necessita parèntesis i s'avalua amb una sola pila.

Escriu AvaluadorRPN amb:

  • double avaluar(String expressio): recorre els símbols separats per espais; si és un número l'apila, i si és un operador (+, -, *, /) desapila dos operands, opera i apila el resultat. Al final ha de quedar exactament un valor.
  • Tractament de casos invàlids sense excepcions pròpies (mòdul 6): retorna Double.NaN i imprimeix un avís.
  • String traca(String expressio): mostra l'estat de la pila després de cada símbol.

Aplica'l a una tarifa de BiblioTech: "15 0.25 * 20 min" no és RPN estàndard, així que fes servir "20 15 - 0.25 *" per calcular la multa d'un llibre retornat el dia 20 amb termini 15.

Solucions

Solució 1

package com.nexussoftware.bibliotech.servei;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import com.nexussoftware.bibliotech.domini.Prestec;

/** Operacio reversible sobre un prestec. */
record OperacioPrestec(Tipus tipus, Prestec prestec, int dia) {

    enum Tipus { PRESTEC, DEVOLUCIO }

    @Override
    public String toString() {
        return String.format("%-11s %s (%s) dia %d", tipus, prestec.getReferencia(),
                prestec.getMaterial().getTitol(), dia);
    }
}

public class GestorPrestecsReversible {

    private static final int MAXIM_HISTORIAL = 20;

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

    private void registrar(OperacioPrestec op) {
        historial.push(op);
        // Acotar pel FONS en O(1): nomes possible amb un Deque, no amb una pila pura
        if (historial.size() > MAXIM_HISTORIAL) {
            historial.pollLast();
        }
    }

    public void prestar(Prestec p, int dia) {
        if (p == null) { return; }
        p.getMaterial().prestar();
        registrar(new OperacioPrestec(OperacioPrestec.Tipus.PRESTEC, p, dia));
    }

    public void retornar(Prestec p, int dia) {
        if (p == null) { return; }
        p.registrarDevolucio(dia);
        registrar(new OperacioPrestec(OperacioPrestec.Tipus.DEVOLUCIO, p, dia));
    }

    /** Reverteix l'ultima operacio. poll retorna null si no n'hi ha cap. */
    public OperacioPrestec desfer() {
        OperacioPrestec op = historial.poll();
        if (op == null) { return null; }

        // switch exhaustiu sobre enum, sense default (04-07): si dema hi afegim
        // un tipus d'operacio, el compilador ens portara aqui.
        switch (op.tipus()) {
            case PRESTEC   -> op.prestec().getMaterial().retornar();  // desfer prestar
            case DEVOLUCIO -> op.prestec().getMaterial().prestar();   // desfer retornar
        }
        return op;
    }

    /**
     * Les N ultimes SENSE buidar la pila.
     * L'iterador d'ArrayDeque va del cim al fons: just l'ordre que volem.
     */
    public List<OperacioPrestec> ultimes(int quantes) {
        List<OperacioPrestec> resultat = new ArrayList<>();
        int n = 0;
        for (OperacioPrestec op : historial) {
            if (n++ >= quantes) { break; }
            resultat.add(op);
        }
        return resultat;
    }

    /**
     * Desfa tot el posterior a 'dia'. peek() consulta sense treure, per
     * decidir si convé desfer abans de comprometre's.
     */
    public int desferFinsA(int dia) {
        int desfetes = 0;
        while (!historial.isEmpty() && historial.peek().dia() > dia) {
            desfer();
            desfetes++;
        }
        return desfetes;
    }

    public OperacioPrestec ultima()   { return historial.peek(); }
    public boolean potDesfer()        { return !historial.isEmpty(); }
    public int     operacionsEnPila() { return historial.size(); }
}

Prova:

Empleat marta = new Empleat("Marta Ruiz", "EMP-001");
Material javaEficac = new Llibre("Java Eficac", "Joshua Bloch", "978-0000000001", 2018);
Material patrons    = new Llibre("Patrons de Disseny", "Erich Gamma", "978-0000000002", 1994);

GestorPrestecsReversible g = new GestorPrestecsReversible();
Prestec p1 = new Prestec(javaEficac, marta, 100);
Prestec p2 = new Prestec(patrons,    marta, 105);

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

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

System.out.println("Desfet: " + g.desfer());
System.out.println("Java Eficac disponible: " + javaEficac.estaDisponible());  // false

System.out.println("Desfetes fins al dia 100: " + g.desferFinsA(100));
System.out.println("Operacions a la pila: " + g.operacionsEnPila());

El punt clau és peek() a desferFinsA: permet consultar el cim sense treure'l, decidir si toca desfer-lo i només llavors comprometre's. Sense peek, caldria treure l'element per mirar-lo i tornar-lo a apilar si no procedia, cosa que a més deixaria la pila en un estat transitori incorrecte. És la raó exacta per la qual les tres operacions d'una pila són push, pop i peek.

Solució 2

package com.nexussoftware.bibliotech.presentacio;

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

public class ComparativaPiles {

    public static void main(String[] args) {
        mateixResultat();
        ordresOposats();
        stackTrencaLaSemantica();
        searchBasatEn1();
        rendiment();
    }

    static void mateixResultat() {
        System.out.println("=== 1. push/pop/peek donen el mateix ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "alta", "baixa", "modificacio" }) {
            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("Totes dues retornen el CIM: LIFO correcte en les dues.\n");
    }

    static void ordresOposats() {
        System.out.println("=== 2. Iteradors en ordres OPOSATS ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "primer", "segon", "tercer" }) {
            stack.push(s);
            deque.push(s);
        }

        System.out.println("Stack toString: " + stack);   // [primer, segon, tercer]
        System.out.println("Deque toString: " + deque);   // [tercer, segon, primer]

        System.out.print("Stack for-each: ");
        for (String s : stack) { System.out.print(s + " "); }
        System.out.print("  <- del FONS al cim: a l'inreves de com sortiran");

        System.out.print("\nDeque for-each: ");
        for (String s : deque) { System.out.print(s + " "); }
        System.out.print("  <- del CIM al fons: l'ordre de sortida");

        System.out.println("\n\nCausa: Stack hereta l'iterador de Vector, que recorre l'");
        System.out.println("array de l'index 0 endavant, i a Stack l'index 0 es el FONS.");
        System.out.println("Consequencia: un bucle que 'processi la pila en ordre' fa el contrari.\n");
    }

    static void stackTrencaLaSemantica() {
        System.out.println("=== 3. Stack exposa l'API d'una llista ===");
        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) + "   <- acces al FONS");
        stack.add(1, "X");
        System.out.println("stack.add(1,X):  " + stack + "   <- insercio al MIG");
        stack.remove(0);
        System.out.println("stack.remove(0): " + stack + "   <- esborrat del FONS");
        stack.set(0, "Z");
        System.out.println("stack.set(0,Z):  " + stack + "   <- modificacio del FONS");

        System.out.println("Cap d'aquestes operacions existeix a Deque: la interficie");
        System.out.println("nomes ofereix els extrems, i aquesta restriccio ES la garantia.");
        System.out.println("Causa: 'class Stack extends Vector' es mala herencia (03-05):");
        System.out.println("una pila FA SERVIR un emmagatzematge, no ES un vector.\n");
    }

    static void searchBasatEn1() {
        System.out.println("=== 4. Stack.search esta basat en 1 ===");
        Stack<String> stack = new Stack<>();
        stack.push("fons"); stack.push("mig"); stack.push("cim");

        System.out.println("search('cim'):  " + stack.search("cim")
                           + "   <- 1, no 0: trenca la convencio de tot Java");
        System.out.println("search('fons'): " + stack.search("fons"));
        System.out.println("search('res'):  " + stack.search("res") + "   <- -1 si no hi es");
        System.out.println("Deque no te search: fes servir contains (O(n)) si el necessites.\n");
    }

    static void rendiment() {
        System.out.println("=== 5. Rendiment illustratiu ===");
        System.out.println("ADVERTIMENT: no es un benchmark rigoros. El JIT, el recollidor");
        System.out.println("i l'eliminacio de codi mort distorsionen aquestes xifres.");
        System.out.println("Per mesurar de debo, JMH (05-04).\n");

        final int N = 1_000_000;

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

        long tStack = cicle(new Stack<>(), N);
        long tDeque = cicle(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 ve sobretot de la sincronitzacio de Vector,");
        System.out.println("que adquireix i allibera un bloqueig a CADA operacio, sense servir");
        System.out.println("per a res en un programa d'un sol fil.");
    }

    static long cicle(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 cicle(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;
    }
}

L'apartat 2 és el més important de l'exercici. Stack i ArrayDeque fan el mateix amb pop, però recorren a l'inrevés, i aquesta incoherència no produeix cap error visible: simplement dona resultats equivocats. És l'argument més contundent contra Stack, per damunt fins i tot de la sincronització.

L'apartat 3 mostra el problema de disseny de fons: extends Vector regala a Stack quaranta mètodes que contradiuen la seva pròpia semàntica. És l'exemple canònic de per què 03-05 insistia a preguntar-se "és un?" abans d'heretar. La resposta correcta era composició.

Solució 3

package com.nexussoftware.bibliotech.servei;

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

/**
 * Avaluador d'expressions en notacio polonesa inversa (RPN).
 *
 * En RPN l'operador va DESPRES dels seus operands, cosa que elimina els
 * parentesis i permet avaluar amb una sola pila:
 *   "3 4 +"             = 3 + 4          = 7
 *   "5 1 2 + 4 * + 3 -" = 5 + (1+2)*4 -3 = 14
 */
public final class AvaluadorRPN {

    private AvaluadorRPN() { }

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

    public static double avaluar(String expressio) {
        if (expressio == null || expressio.isBlank()) {
            System.out.println("AVIS: expressio buida");
            return Double.NaN;
        }

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

        for (String simbol : expressio.trim().split("\\s+")) {
            if (OPERADORS.contains(simbol)) {
                if (pila.size() < 2) {
                    System.out.println("AVIS: falten operands per a '" + simbol + "'");
                    return Double.NaN;
                }
                // ORDRE IMPORTANT: el primer que surt es l'operand DRET,
                // perque va ser l'ultim a apilar-se. Invertir-ho trenca '-' i '/'.
                double dret     = pila.pop();
                double esquerre = pila.pop();
                Double resultat = operar(esquerre, dret, simbol);
                if (resultat == null) { return Double.NaN; }
                pila.push(resultat);
            } else {
                Double numero = aNumero(simbol);
                if (numero == null) {
                    System.out.println("AVIS: simbol no reconegut -> '" + simbol + "'");
                    return Double.NaN;
                }
                pila.push(numero);
            }
        }

        if (pila.size() != 1) {
            System.out.println("AVIS: expressio mal formada, queden "
                               + pila.size() + " valors a 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 modul 6 ensenyara a assenyalar-ho amb una excepcio propia
                    System.out.println("AVIS: divisio per zero");
                    return null;
                }
                return a / b;
            default:  return null;
        }
    }

    /** Conversio sense try/catch: comprovem el format abans (el modul 6 ho fara millor). */
    private static Double aNumero(String s) {
        if (!s.matches("-?\\d+(\\.\\d+)?")) { return null; }
        return Double.valueOf(s);
    }

    /** Mostra l'estat de la pila despres de cada simbol. */
    public static String traca(String expressio) {
        StringBuilder sb = new StringBuilder();
        Deque<Double> pila = new ArrayDeque<>();

        sb.append(String.format("%-8s %s%n", "SIMBOL", "PILA (cim primer)"));
        for (String simbol : expressio.trim().split("\\s+")) {
            if (OPERADORS.contains(simbol) && pila.size() >= 2) {
                double dret = pila.pop();
                double esq  = pila.pop();
                Double r = operar(esq, dret, simbol);
                pila.push(r == null ? Double.NaN : r);
            } else {
                Double n = aNumero(simbol);
                if (n != null) { pila.push(n); }
            }
            // L'iterador d'ArrayDeque va del cim al fons: l'ordre util
            sb.append(String.format("%-8s %s%n", simbol, pila));
        }
        return sb.toString();
    }

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

        // Multa de BiblioTech: llibre retornat el dia 20 amb termini de 15 dies,
        // tarifa 0,25 EUR/dia. En RPN: (20 - 15) * 0.25
        System.out.println("20 15 - 0.25 *      = " + avaluar("20 15 - 0.25 *")
                           + " EUR de multa");

        System.out.println("\n--- Casos invalids ---");
        System.out.println("Resultat: " + avaluar("3 +"));
        System.out.println("Resultat: " + avaluar("3 4 5 +"));
        System.out.println("Resultat: " + avaluar("3 0 /"));
        System.out.println("Resultat: " + avaluar("3 4 %"));

        System.out.println("\n--- Traca de '5 1 2 + 4 * + 3 -' ---");
        System.out.print(traca("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 invalids ---
AVIS: falten operands per a '+'
Resultat: NaN
AVIS: expressio mal formada, queden 2 valors a la pila
Resultat: NaN
AVIS: divisio per zero
Resultat: NaN
AVIS: simbol no reconegut -> '%'
Resultat: NaN

--- Traca de '5 1 2 + 4 * + 3 -' ---
SIMBOL   PILA (cim primer)
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 traça mostra l'essència de l'estructura: la pila guarda els resultats parcials pendents de combinar, i cada operador consumeix exactament els dos últims. Que sigui LIFO és el que garanteix que es combinin els operands correctes: quan arriba el + de la posició 4, els dos valors del cim (2.0 i 1.0) són precisament els que li corresponen, i el 5.0 del fons espera pacientment el seu torn.

Dos detalls que solen donar problemes. L'ordre dels operands: el primer que surt de la pila és l'operand dret, perquè va ser l'últim a apilar-se; invertir-ho donaria resultats correctes per a + i * però equivocats per a - i /, que és la mena de bug que triga hores a aparèixer. I la comprovació final que queda exactament un valor: si en sobren, l'expressió estava mal formada encara que cada operació individual hagi funcionat.

Aquest és també, en essència, el funcionament de la mateixa JVM: el seu codi de bytes és una màquina de pila, on iadd desapila dos enters i apila la seva suma. Avaluar 20 15 - 0.25 * amb un ArrayDeque és, conceptualment, el mateix que fa la màquina virtual en executar calcularMulta.

Conclusió

Ja domines la tercera política d'accés del mòdul. Saps que una pila és LIFO: els elements entren i surten pel cim amb push, pop i peek, i que la seva propietat essencial —invertir l'ordre— és el que la fa idònia per desfer, per analitzar estructures imbricades, per al recorregut en profunditat i per a la mateixa execució dels programes.

Entens la pila de crides de la JVM: cada invocació apila un marc amb paràmetres, variables locals i adreça de retorn, i cada retorn el desapila. Amb això has tancat el cercle obert a 03-03: el StackOverflowError és l'esgotament d'aquesta pila, té mida fixa per fil i és un Error, no una excepció que hagis de tractar; les seves causes són una recursivitat sense cas base —un bug— o una recursivitat correcta però massa profunda —que es resol amb una pila explícita al heap—.

Coneixes la classe Stack i, sobretot, per què no l'has de fer servir: estén Vector, cosa que és mala herència de manual (una pila fa servir un emmagatzematge, no és un vector) i li regala tota l'API d'una llista, permetent get(0), add(1, x) i remove(0) sobre una suposada pila; està sincronitzada amb un cost que no compra seguretat real; i —el defecte més traïdor— el seu iterador recorre del fons al cim, just a l'inrevés de l'ordre en què sortiran els elements, produint resultats equivocats sense cap avís. El seu search basat en 1 remata el quadre.

La resposta correcta és Deque<X> pila = new ArrayDeque<>(): push, pop i peek com a àlies de les operacions sobre el cap, O(1) sense bloquejos, la millor localitat de memòria cau, i un iterador que recorre en l'ordre de sortida. Tens clara l'asimetria de pop() (llança) enfront de peek() (retorna null) i les famílies completes de 05-07 per triar el comportament que vulguis.

Has implementat una pila pròpia amb un array i un índex, entenent des de dins per què cim apunta a la posició lliure següent, per què cal posar la cel·la a null en desapilar —fuita de memòria— i per què el creixement multiplicatiu dona cost amortitzat O(1). I has resolt els dos problemes canònics: parèntesis equilibrats, on la pila detecta el mal imbricament que un simple comptador deixaria passar, i desfer/refer amb dues piles, inclòs el detall que gairebé tothom oblida —una acció nova ha de buidar la pila de refer—. I saps convertir una recursivitat en iteració amb una pila explícita, amb el truc d'apilar els fills en ordre invers per conservar l'ordre del recorregut.

BiblioTech té ara un CatalegAmbHistorial amb Deque<OperacioCataleg> que permet anul·lar l'última alta o baixa, refer-la, desfer-ne diverses de cop i consultar l'historial en l'ordre correcte, amb l'historial acotat descartant pel fons en O(1) —una cosa que només un Deque permet—.

A la lliçó següent, Ordenació i cerca en col·leccions, tanques el mòdul recollint tots els fils. Tornaràs sobre Comparable i el seu contracte complet —signe del resultat, antisimetria, transitivitat, coherència amb equals i què es trenca exactament en un TreeSet quan no ho és—, inclòs l'error clàssic de restar enters i desbordar. Reprendràs Comparator des de 04-06 amb comparing, thenComparing, reversed, nullsFirst, comparingInt i per què aquest últim evita l'autoboxing. Veuràs les quatre estratègies d'ordenació —Collections.sort, List.sort, Arrays.sort i les col·leccions que es mantenen ordenades soles—, què significa que una ordenació sigui estable i per què importa en ordenar per criteris successius, i quins algorismes fa servir Java realment: TimSort per a objectes i quicksort de doble pivot per a primitius. Després, la cerca: lineal enfront de binària enfront de clau de mapa, amb la interpretació del valor negatiu que retorna binarySearch, i les utilitats de Collections que queden per conèixer. I al final, el balanç del mòdul: què és capaç de fer BiblioTech ara, què continua sent fràgil i per què el mòdul 6 és el següent pas inevitable.

◄ Anterior
◄
Següent ►
►

Curs de Programació en Java

Mòdul 1: Introducció a Java

Mòdul 2: Flux de control

Mòdul 3: Programació orientada a objectes

Mòdul 4: Programació orientada a objectes avançada

Mòdul 5: Estructures de dades i col·leccions

Mòdul 6: Gestió d'excepcions

Mòdul 7: Entrada/sortida de fitxers

Mòdul 8: Multifil i concurrència

Mòdul 9: Xarxes

Mòdul 10: Temes avançats

Mòdul 11: Frameworks i llibreries de Java

Mòdul 12: Construcció d'aplicacions del món real

El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats