Java Stack

Uno stack è una collezione last-in-first-out: si inserisce un elemento con push, e il successivo pop restituisce ciò che è stato inserito più di recente. Java offre due modi per costruirne uno — la classe legacy java.util.Stack del 1995, e la raccomandazione moderna di Deque<E> (tipicamente ArrayDeque). Entrambi funzionano, entrambi hanno le stesse operazioni concettuali, ma il Javadoc ufficiale di Stack stesso consiglia di preferire Deque. Questo capitolo mostra come appare Stack, perché il JDK ora punta altrove e come utilizzare il sostituto raccomandato.

A cosa serve uno stack

Gli stack compaiono in qualsiasi algoritmo che sia naturalmente last-in-first-out:

• Cronologie undo / redo — ogni nuova azione viene inserita con push; undo estrae l'ultima.
• Stato di parser e interpreter — valutazione di espressioni, controllo di parentesi bilanciate, frame di chiamata.
• Attraversamento depth-first — si inseriscono i successori con push, si estrae con pop il prossimo nodo da visitare.
• Inversione di sequenze — si inserisce ogni elemento di una sequenza, poi lo si estrae con pop.

La forma è sempre la stessa: push, pop, peek, isEmpty, size. Cinque operazioni.

La classe Stack legacy

java.util.Stack<E> estende Vector<E>, il che significa che eredita tutto ciò che è nel capitolo precedente — incluso il synchronized per ogni metodo, i nomi dei metodi legacy e il fatto scomodo di essere una List. Uno Stack è, per ereditarietà, una lista indicizzabile — è possibile chiamare stack.get(3) su di esso, che è esattamente il tipo di errore API che motiva la raccomandazione di usare Deque.

Stack<String> s = new Stack<>();
s.push("a");
s.push("b");
s.push("c");
System.out.println(s.peek());   // c
System.out.println(s.pop());    // c
System.out.println(s.size());   // 2
System.out.println(s.empty());  // false  (note: empty(), not isEmpty())

Sei metodi specifici di Stack:

• E push(E item) — aggiunge in cima. Restituisce l'elemento.
• E pop() — rimuove e restituisce l'elemento in cima. Lancia EmptyStackException se vuoto.
• E peek() — elemento in cima senza rimuoverlo. Stessa eccezione.
• boolean empty() — notare la grafia in minuscolo, distinta da Collection.isEmpty().
• int search(Object o) — distanza 1-based dalla cima, oppure -1 se non presente. Scelta insolita — il risultato è "quanti pop per raggiungere o", il che è raramente utile.

Tutto il resto è ereditato da Vector e List.

Perché il Javadoc indica Deque

Aprendo il Javadoc effettivo di Stack in qualsiasi JDK moderno si trova la riga:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Le ragioni si allineano con il capitolo precedente su Vector:

• Stack è sincronizzato su ogni metodo. Si paga il costo del lock anche nel codice single-thread, e la sincronizzazione è alla granularità sbagliata per qualsiasi operazione composta.
• Stack è una List. L'accesso indicizzato su uno stack è un errore categoriale — permette di guardare nel mezzo, violando la disciplina LIFO che la classe è destinata a imporre.
• Le cinque operazioni di stack che si vogliono realmente sono già presenti in Deque (push, pop, peek, isEmpty, size), e ArrayDeque è l'implementazione più veloce nel JDK.

In sintesi: Stack funziona, ma è un design del 1995 incastrato in un framework del 1998. Il nuovo codice dovrebbe usare Deque.

Il sostituto raccomandato

L'idioma è una sola riga:

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

Poi si chiama push, pop, peek. L'interfaccia Deque li definisce internamente come addFirst, removeFirst, peekFirst, quindi la cima dello stack è la testa del deque.

Deque<String> calls = new ArrayDeque<>();
calls.push("main");
calls.push("parseArgs");
calls.push("split");
System.out.println(calls.peek());      // split
System.out.println(calls.pop());       // split
System.out.println(calls);              // [parseArgs, main]

Tre dettagli da sapere:

1. peek() su un Deque restituisce null quando è vuoto; peek() su Stack lancia un'eccezione. peekFirst() è la stessa forma che restituisce null. Se si preferisce l'eccezione, chiamare getFirst() (o element()).
2. La stessa distinzione pop() / removeFirst() si applica: pop() lancia un'eccezione quando è vuoto.
3. ArrayDeque rifiuta elementi null. Usarlo solo per valori non null — che è il caso tipico per gli stack.

Quando Stack è accettabile nel nuovo codice

Quasi mai, e la soglia è bassa:

• Mantenere vecchio codice che lo usa già — non conviene modificare solo per cambiare la classe.
• Lavorare con un'API che richiede specificamente Stack — estremamente raro. Le classi Swing che usavano Vector e simili non tendono a richiedere Stack.

Per tutto il resto, dichiarare Deque<E> e istanziare ArrayDeque<>.

Un esempio pratico: matcher di parentesi, due modi

Il programma seguente usa sia Stack che Deque<Character> per risolvere il classico problema delle parentesi bilanciate. Stesso algoritmo, due implementazioni — leggilo affiancato, poi guarda la forma Deque e decidi quale preferiresti leggere tra tre mesi.

Cosa vale la pena notare:

• Le due funzioni sono identiche a parte il nome del tipo e empty() vs isEmpty(). Non c'è alcuna ragione algoritmica per preferire Stack — il codice si legge allo stesso modo.
• Il blocco "Stack-specific API" in fondo rappresenta il caso contro la classe legacy: empty() ha un nome diverso dal resto del framework, search() restituisce una distanza 1-based (rara nel resto di Java), e get(0) permette di accedere al mezzo di uno stack — vanificando completamente il punto dell'astrazione.

Cosa viene dopo

Hai ora visto le tre implementazioni List fondamentali (ArrayList, LinkedList, Vector) e la specializzazione LIFO costruita sopra Vector. I prossimi quattro capitoli coprono la storia parallela per le cose-da-aggiungere-e-prelevare-in-ordine: l'interfaccia Queue, PriorityQueue, ArrayDeque, e il più generale contratto Deque.

Pratica