Java ArrayDeque

ArrayDeque<E> é um array circular que cresce sob demanda. Ele implementa tanto Queue<E> quanto Deque<E>, podendo atuar como fila FIFO, pilha LIFO ou fila de duas pontas sem alterações no código. O Javadoc de Stack recomenda Deque em vez da classe legada; o Javadoc de Deque acrescenta a recomendação prática de que ArrayDeque deve ser sua implementação padrão. Quase sempre é mais rápido que LinkedList, ocupa menos memória e é a escolha preferida da biblioteca padrão assim que você não precisa mais da interface List.

Por que um array circular

Uma "fila a partir de um array" clássica encontra um problema: depois de alguns ciclos de adicionar-na-cauda e remover-da-cabeça, o array fica cheio na cauda enquanto posições vazias se acumulam na cabeça. Uma solução ingênua deslocaria tudo para a esquerda a cada remoção — O(n) por remoção, arruinando o desempenho.

O truque do array circular resolve isso. A classe mantém dois índices, head e tail, e os deixa dar a volta:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst decrementa head, addLast incrementa tail, ambos em módulo do comprimento do array. removeFirst e removeLast fazem o inverso. Toda operação é O(1); o único custo é dobrar o array de suporte quando head colidir com tail, o que é amortizado.

O resultado: sem alocação de nós por elemento, sem perseguição de ponteiros, acesso favorável ao cache. Esse é o motivo técnico pelo qual ArrayDeque costuma ser a escolha mais rápida para cargas de trabalho com filas e pilhas.

Revisão da interface Deque

Um Deque tem duas pontas. Cada operação vem em três variantes:

Além disso, os sinônimos de Queue e pilha mapeiam para a ponta da cabeça:

Portanto, Deque é uma interface que expõe fila e pilha ao mesmo tempo, dependendo de qual nome você chama a cabeça. Cobrimos esses mapeamentos nos capítulos de Queue e Stack; Deque é onde eles se encontram.

O que ArrayDeque adiciona além disso

Na prática, muito pouco em termos de API — esse é o ponto. A classe expõe o contrato Deque de forma honesta: as duas pontas, os três estilos de erro por operação, e clear(), iterator(), descendingIterator(), contains, size, isEmpty. A iteração com o iterador padrão vai da cabeça para a cauda; descendingIterator é a forma barata de percorrer da cauda para a cabeça sem inverter.

Os construtores espelham ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Pré-dimensione quando você conhece a carga de trabalho. O padrão de 16 é arredondado para a potência de dois mais próxima, e o crescimento dobra o array — portanto, um milhão de chamadas offerLast a partir de um deque com tamanho padrão dispara cerca de 16 operações de crescimento e cópia.

As regras: sem nulls, não thread-safe, fail-fast

Três regras para internalizar:

1. ArrayDeque não permite elementos null. Toda inserção lança NullPointerException. É assim que pollFirst() retornando null para um deque vazio permanece sem ambiguidade.
2. Não é thread-safe. Duas threads mutando o mesmo ArrayDeque vão corrompê-lo. Para uso concorrente, veja ConcurrentLinkedDeque (sem bloqueio, ilimitado) ou LinkedBlockingDeque (limitado, bloqueante).
3. Iteração fail-fast. Modificar o deque fora do iterador durante a iteração lança ConcurrentModificationException. Use Iterator.remove() ou removeIf para mutação segura.

Quando escolher ArrayDeque em vez das alternativas

O fluxo de decisão:

• Precisa de uma Queue? → ArrayDeque. Padrão.
• Precisa de uma pilha? → ArrayDeque. Padrão. Use push / pop / peek.
• Precisa de um Deque? → ArrayDeque. Padrão.
• Precisa de semânticas de Deque e List no mesmo objeto? → LinkedList. Raro.
• Precisa de ordem de prioridade? → PriorityQueue. Abstração diferente.
• Precisa de acesso concorrente? → ConcurrentLinkedDeque (ilimitado) ou LinkedBlockingDeque (limitado). A escolha certa depende de você precisar ou não de contrapressão.

O Javadoc explicita a recomendação em texto direto: "Esta classe provavelmente é mais rápida que Stack quando usada como pilha, e mais rápida que LinkedList quando usada como fila." Isso vem diretamente dos autores do JDK; vale ser levado ao pé da letra.

Um exemplo completo: fila, pilha, deque, janela deslizante

O programa abaixo usa uma instância de ArrayDeque como fila FIFO, outra como pilha LIFO e uma terceira como armazenamento para um máximo de janela deslizante — um problema clássico onde ArrayDeque é a resposta consagrada porque você precisa de mutação barata nas duas pontas.

O que você pode tirar desta execução:

• As seções 1 e 2 são a mesma classe fazendo dois trabalhos ao chamar métodos diferentes. Fila FIFO: offerLast / pollFirst. Pilha LIFO: push / pop. Não há classe separada para aprender.
• descendingIterator() é a forma barata de percorrer em sentido inverso — útil quando você construiu um deque como pilha e quer imprimi-lo de baixo para cima.
• A função de janela deslizante usa as duas pontas no mesmo loop — pollFirst para descartar índices que saíram da janela, pollLast para manter uma pilha monotônica decrescente, peekFirst para ler o máximo atual. Esse acesso de duas pontas é a razão pela qual ArrayDeque existe; tentar fazer isso com um ArrayList seria quadrático.

O que vem a seguir

Você viu como ArrayDeque implementa ambas as pontas da história de fila/pilha. A interface que ele vem implementando o tempo todo merece seu próprio capítulo — Deque é o contrato que une tudo o que cobrimos para coleções semelhantes a filas. Vemos isso na próxima sessão.

Prática