Java Stack

Uma pilha (stack) é uma coleção último-a-entrar-primeiro-a-sair: você usa push para adicionar um item e o próximo pop retorna o que foi colocado mais recentemente. O Java tem duas formas de criar uma — a classe legada java.util.Stack de 1995 e a recomendação moderna de Deque<E> (normalmente ArrayDeque). Ambas funcionam, ambas têm as mesmas operações conceituais, mas o próprio Javadoc oficial do Stack orienta a preferir o Deque. Este capítulo mostra como o Stack funciona, por que o JDK agora aponta para outra direção e como usar o substituto recomendado.

Para que serve uma pilha

Pilhas aparecem em qualquer algoritmo que seja naturalmente último-a-entrar-primeiro-a-sair:

• Históricos de desfazer/refazer — cada nova ação é empilhada com push; desfazer retira a mais recente com pop.
• Estado de parser e interpretador — avaliação de expressões, verificação de colchetes balanceados, frames de chamada.
• Travessia em profundidade — empilha os sucessores, retira com pop o próximo nó a visitar.
• Inversão de sequências — empilha cada elemento de uma sequência e depois os retira com pop.

A forma é sempre a mesma: push, pop, peek, isEmpty, size. Cinco operações.

A classe Stack legada

java.util.Stack<E> estende Vector<E>, o que significa que herda tudo do capítulo anterior — incluindo o synchronized por método, os nomes de métodos legados e o fato desconfortável de ser uma List. Um Stack é, por herança, uma lista indexável — você pode chamar stack.get(3) nele, que é exatamente o tipo de erro de API que motiva a recomendação 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 do Stack:

• E push(E item) — adiciona ao topo. Retorna o item.
• E pop() — remove e retorna o topo. Lança EmptyStackException se estiver vazio.
• E peek() — topo sem remover. Mesma exceção.
• boolean empty() — note a grafia em minúsculas, distinta de Collection.isEmpty().
• int search(Object o) — distância baseada em 1 a partir do topo, ou -1 se não presente. Escolha estranha — o resultado é "quantos pops para alcançar o", o que raramente é útil.

Todo o restante é herdado de Vector e List.

Por que o Javadoc aponta para Deque

Abra o Javadoc real do Stack em qualquer JDK moderno e você encontrará a linha:

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.

Os motivos se alinham com o capítulo anterior sobre Vector:

• Stack é sincronizado em cada método. Você paga o custo do lock mesmo em código de thread único, e a sincronização está na granularidade errada para qualquer operação composta.
• Stack é uma List. Acesso indexado em uma pilha é um erro de categoria — permite espiar o meio, o que viola a disciplina LIFO que a classe deveria impor.
• As cinco operações de pilha que você realmente quer já estão em Deque (push, pop, peek, isEmpty, size), e ArrayDeque é a implementação mais rápida no JDK.

Em resumo: Stack funciona, mas é um design de 1995 encaixado num framework de 1998. Código novo deve usar Deque.

O substituto recomendado

O idioma é uma linha:

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

Depois chame push, pop, peek. A interface Deque os define internamente como addFirst, removeFirst, peekFirst, então o topo da pilha é a cabeça do 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]

Três detalhes a saber:

1. peek() em um Deque retorna null quando vazio; peek() em Stack lança exceção. peekFirst() é a mesma forma que retorna null. Se preferir a exceção, chame getFirst() (ou element()).
2. A mesma distinção pop() / removeFirst() se aplica: pop() lança exceção quando vazio.
3. ArrayDeque rejeita elementos null. Use-o apenas para valores não nulos — que é o caso usual para pilhas.

Quando Stack é aceitável em código novo

Quase nunca, e a barra é baixa:

• Manutenção de código antigo que já o usa — não faça refatoração só para trocar a classe.
• Trabalhar com uma API que exige Stack especificamente — extremamente raro. As classes Swing que usavam Vector e similares não tendem a exigir Stack.

Para tudo mais, declare Deque<E> e instancie ArrayDeque<>.

Um exemplo prático: verificador de parênteses, de duas formas

O programa abaixo usa tanto Stack quanto Deque<Character> para resolver o clássico problema dos parênteses balanceados. Mesmo algoritmo, duas implementações — leia lado a lado e depois olhe a forma com Deque e decida qual preferiria ler daqui a três meses.

O que vale notar:

• As duas funções são idênticas exceto pelo nome do tipo e empty() vs isEmpty(). Não há razão algorítmica para preferir Stack — o código lê-se da mesma forma.
• O bloco "Stack-specific API" no final é o argumento contra a classe legada: empty() tem um nome diferente do restante do framework, search() retorna uma distância baseada em 1 (raro no resto do Java) e get(0) permite acessar o meio de uma pilha — derrotando todo o propósito da abstração.

O que vem a seguir

Você já viu as três implementações List mais usadas (ArrayList, LinkedList, Vector) e a especialização LIFO construída sobre Vector. Os próximos quatro capítulos cobrem a história paralela para coisas-que-você-adiciona-e-retira-em-ordem: a interface Queue, PriorityQueue, ArrayDeque e o mais geral contrato Deque.

Prática