Java Stack

Un stack es una colección de tipo último en entrar, primero en salir: se hace push de un elemento y el siguiente pop devuelve lo que se agregó más recientemente. Java tiene dos formas de construir uno: la clase heredada java.util.Stack de 1995, y la recomendación moderna de Deque<E> (típicamente ArrayDeque). Ambas funcionan, ambas tienen las mismas operaciones conceptuales, pero el Javadoc oficial de Stack indica que se prefiera Deque. Este capítulo muestra cómo luce Stack, por qué el JDK ahora apunta a otra parte, y cómo usar el reemplazo recomendado.

Para qué sirve un stack

Los stacks aparecen en cualquier algoritmo que sea naturalmente último en entrar, primero en salir:

• Historiales de deshacer / rehacer — cada nueva acción se hace push; deshacer hace pop de la más reciente.
• Estado de parsers e intérpretes — evaluación de expresiones, verificación de corchetes balanceados, marcos de llamada.
• Recorrido en profundidad — se hace push de los sucesores, pop del siguiente nodo a visitar.
• Invertir elementos — se hace push de cada elemento de una secuencia y luego pop de todos.

La forma es siempre la misma: push, pop, peek, isEmpty, size. Cinco operaciones.

La clase Stack heredada

java.util.Stack<E> extiende Vector<E>, lo que significa que hereda todo del capítulo anterior, incluido el synchronized por método, los nombres de métodos heredados, y el hecho incómodo de que es un List. Un Stack es, por herencia, una lista indexable; se puede llamar stack.get(3) sobre él, que es exactamente el tipo de error de API que motiva la recomendación de usar 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())

Seis métodos específicos de Stack:

• E push(E item) — agrega al tope. Devuelve el elemento.
• E pop() — elimina y devuelve el tope. Lanza EmptyStackException si está vacío.
• E peek() — tope sin eliminar. Misma excepción.
• boolean empty() — nótese la escritura en minúsculas, distinta de Collection.isEmpty().
• int search(Object o) — distancia basada en 1 desde el tope, o -1 si no está presente. Elección peculiar — el resultado es "cuántos pops se necesitan para alcanzar a o," lo cual raramente es útil.

Todo lo demás se hereda de Vector y List.

Por qué el Javadoc apunta a Deque

Abre el Javadoc real de Stack en cualquier JDK moderno y encontrarás la siguiente línea:

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.

Las razones se alinean con el capítulo anterior sobre Vector:

• Stack está sincronizado en cada método. Se paga el costo del bloqueo incluso en código de un solo hilo, y la sincronización tiene la granularidad incorrecta para cualquier operación compuesta.
• Stack es un List. El acceso indexado sobre un stack es un error categórico — permite ver el medio, lo cual viola la disciplina LIFO que la clase debería imponer.
• Las cinco operaciones de stack que realmente se necesitan ya están en Deque (push, pop, peek, isEmpty, size), y ArrayDeque es la implementación más rápida del JDK.

En resumen: Stack funciona, pero es un diseño de 1995 insertado en un framework de 1998. El código nuevo debería usar Deque.

El reemplazo recomendado

El idioma es una sola línea:

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

Luego se llama a push, pop, peek. La interfaz Deque los define internamente como addFirst, removeFirst, peekFirst, por lo que el tope del stack es la cabeza 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]

Tres detalles que conviene conocer:

1. peek() sobre un Deque devuelve null cuando está vacío; peek() sobre Stack lanza una excepción. peekFirst() es la forma que devuelve null. Si se prefiere la excepción, llama a getFirst() (o element()).
2. La misma distinción pop() / removeFirst() aplica: pop() lanza excepción cuando está vacío.
3. ArrayDeque rechaza elementos null. Úsalo solo para valores no nulos — que es el caso habitual para stacks.

Cuándo Stack es aceptable en código nuevo

Casi nunca, y el umbral es bajo:

• Mantenimiento de código antiguo que ya lo usa — no vale la pena cambiarlo solo para intercambiar la clase.
• Trabajar con una API que requiere Stack específicamente — extremadamente raro. Las clases de Swing que usaban Vector y similares no tienden a requerir Stack.

Para todo lo demás, declara Deque<E> e instancia ArrayDeque<>.

Un ejemplo práctico: verificador de paréntesis, de dos formas

El programa a continuación usa tanto Stack como Deque<Character> para resolver el clásico problema de paréntesis balanceados. Mismo algoritmo, dos implementaciones — léelo lado a lado, luego mira la forma con Deque y decide cuál preferirías leer en tres meses.

Lo que vale la pena notar:

• Las dos funciones son idénticas excepto por el nombre del tipo y empty() vs isEmpty(). No hay razón algorítmica para preferir Stack — el código se lee igual.
• El bloque "Stack-specific API" al final es el argumento contra la clase heredada: empty() tiene un nombre diferente al resto del framework, search() devuelve una distancia basada en 1 (infrecuente en el resto de Java), y get(0) permite acceder al medio de un stack, derrotando el propósito de la abstracción.

Qué sigue

Ya has visto las tres implementaciones de List más usadas (ArrayList, LinkedList, Vector) y la especialización LIFO construida sobre Vector. Los siguientes cuatro capítulos cubren la historia paralela para elementos que se agregan y extraen en orden: la interfaz Queue, PriorityQueue, ArrayDeque, y el contrato Deque más general.

Práctica