Java 45: ArrayDeque — Stack, Queue & the Deque API
easy⏱ 5 mincoursejava
Dos familias de métodos: lanzar vs devolver
Deque expone operaciones en pares: que lanzan (addFirst/addLast/removeFirst/removeLast/getFirst) que fallan en vacío/lleno, y que devuelven valor (offerFirst/offerLast/pollFirst/pollLast/peekFirst) que devuelven false/null. Elige las que lanzan cuando el vacío es un bug; elige la familia offer/poll/peek cuando el vacío es flujo de control normal.
Deque<Integer> d = new ArrayDeque<>();
d.offerLast(1); d.offerLast(2); // queue: enqueue at tail
d.pollFirst(); // -> 1 (FIFO)
d.push(9); // stack: push == addFirst
d.pop(); // -> 9 (LIFO)
Stack con push/pop, Queue con offer/poll
Como stack: push = addFirst, pop = removeFirst, peek = peekFirst — LIFO en la cabeza. Como queue: offer (= offerLast) encola en la cola, poll (= pollFirst) desencola en la cabeza — FIFO. El mismo objeto, elegido por qué métodos llamas.
¿Por qué no Stack/Vector?
java.util.Stack extiende Vector — cada método es synchronized (overhead inútil en un solo hilo) e itera en el orden equivocado para un stack (de abajo a arriba). ArrayDeque es no sincronizado, contiguo (cache-friendly), crece amortizado O(1) y prohíbe elementos null (así null desde poll significa vacío sin ambigüedad). Es el default para stacks y queues no bloqueantes.
Un deque, tres roles
Implementa ArrayDeque<T> con addFirst/addLast/pollFirst/pollLast/peekFirst/peekLast/size. (1) Úsalo como stack para invertir [1,2,3,4,5]. (2) Úsalo como queue FIFO para procesar la misma lista en orden. (3) Úsalo como ventana deslizante: mantén el máximo de cada ventana de tamaño 3 sobre [4,1,7,2,9,3] con un deque monótono. Imprime los tres resultados.
Deque monótono = máximo de ventana deslizante
El máximo de ventana deslizante en O(n) mantiene índices en un deque cuyos valores decrecen de frente a fondo: antes de empujar, saca valores menores por la cola; saca el frente cuando deja la ventana. El frente siempre tiene el máximo de la ventana actual. Este truco con deque es una pregunta de entrevista frecuente.
Quiz: ArrayDeque vs LinkedList como queue
¿Cuál es la mejor Queue? ArrayDeque en casi todos los casos — memoria contigua significa menos cache misses y sin overhead de objeto por nodo. LinkedList solo gana cuando necesitas remover del medio por iterador, lo que las queues nunca hacen. Para BFS, colas de trabajo y stacks, usa ArrayDeque.