Collections

70. Deque and Stack

Deque (double-ended queue) can be used as both a stack (LIFO) and a queue (FIFO); prefer ArrayDeque over LinkedList for better performance; avoid the legacy Stack class entirely.

Java 21 (core language)

Explanation

Stack (Java 1.0) extends Vector, is synchronised, and exposes unwanted inherited methods. Do not use it. Deque is the modern replacement for both stack and queue patterns.

Deque<E> API: stack usage: push(e) (addFirst), pop() (removeFirst), peek() (peekFirst). Queue usage: offer(e) (addLast), poll() (removeFirst), peek() (peekFirst). Both ends: addFirst/addLast, removeFirst/removeLast, peekFirst/peekLast.

ArrayDeque vs LinkedList: ArrayDeque is backed by a circular resizable array — O(1) amortised at both ends, better cache locality, no per-node pointer overhead. Prefer ArrayDeque in virtually all cases. Use LinkedList only if you need the List interface simultaneously or require null element support.

Example

import java.util.*;

public class DequeAndStack {
    public static void main(String[] args) {
        // ArrayDeque as STACK (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");   // addFirst
        stack.push("second");
        stack.push("third");
        System.out.println("Stack peek: " + stack.peek()); // third (top)
        while (!stack.isEmpty()) {
            System.out.println("Pop: " + stack.pop()); // third, second, first
        }

        // ArrayDeque as QUEUE (FIFO)
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("Alice");  // addLast
        queue.offer("Bob");
        queue.offer("Carol");
        System.out.println("Queue peek: " + queue.peek()); // Alice (front)
        while (!queue.isEmpty()) {
            System.out.println("Poll: " + queue.poll()); // Alice, Bob, Carol
        }

        // Double-ended usage
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addFirst(2);
        deque.addFirst(1);   // [1, 2]
        deque.addLast(3);
        deque.addLast(4);    // [1, 2, 3, 4]
        System.out.println("Deque: " + deque);
        System.out.println("First: " + deque.peekFirst()); // 1
        System.out.println("Last:  " + deque.peekLast());  // 4

        // Exception vs null return: offer/poll vs add/remove
        Deque<String> bounded = new ArrayDeque<>(2);
        bounded.offer("x"); bounded.offer("y");
        String polled = bounded.poll(); // returns null if empty
        System.out.println("Polled: " + polled); // x
    }
}

Sources