A Deque (pronounced "deck") is a double-ended queue, meaning elements can be added and removed from both the front and the back. That single property makes it a versatile tool for collection work: it can behave as a FIFO queue, as a LIFO stack, or as a sliding window over recent items. This lesson covers what Deque is, the full grid of methods it offers, how stack-style methods map onto it, why Deque (specifically ArrayDeque) is the modern replacement for the old Stack class, and the two implementations to use.

A regular queue has one rule: add to the tail, remove from the head. A stack has the opposite rule: add to the top, remove from the top. A Deque supports both rules from both ends. Add to the head, add to the tail, remove from the head, remove from the tail, peek at the head, peek at the tail. Six conceptual operations, each with several spellings.

The interface sits inside java.util and extends Queue, which itself extends Collection. Every Deque is also a Queue, and every Queue is also a Collection. The two main implementations are ArrayDeque (a resizable circular array) and LinkedList (the doubly-linked list).

The following program uses a deque to model a browser's back/forward navigation. Each visited page gets pushed onto the front. The most recent page sits at the head; older pages sit toward the tail.

Each addFirst pushes a new page onto the head, so the most recently visited page lives at the front. peekFirst returns the head without removing it; peekLast returns the tail without removing it. Nothing was popped, so the size is still 3.

A diagram clarifies the shape. A deque has two named ends, and every method targets one of them.

The orange boxes are the two families of methods, one per end. The cyan boxes are the conceptual endpoints. The teal nodes are the live elements between them. Every method on Deque is just a verb applied to one of the two ends.

Deque ships with a lot of methods, and the naming pattern is easier to learn from the grid. There are three operations (add, remove, examine), two ends (first, last), and two failure modes (throw an exception, return a special value). That gives twelve methods, plus six legacy Queue-style methods, plus three stack-style methods. The pattern is more important than the full list.

The two columns per end exist because real applications disagree about what should happen when the operation can't proceed. Calling removeFirst() on an empty deque throws NoSuchElementException. Calling pollFirst() returns null. The "throw" forms are for cases where an empty deque is a programming bug; the "special return" forms are for cases where an empty deque is just an expected condition to branch on.

Here's a program that exercises every cell of the matrix on a small order queue.

The deque starts empty. Three orders go in at the tail, then a VIP order jumps to the head. getFirst() returns the VIP without removing it. peekLast() returns order-3 without removing it. removeFirst() and pollLast() both remove and return their respective ends. What's left in the middle is order-1 and order-2.

The difference between the two columns shows up only when the deque is empty.

pollFirst and peekFirst return null when there is nothing to read. removeFirst throws, because asking to remove from an empty deque is usually a mistake worth surfacing. Pick the form that matches the intent: throw when emptiness is a bug, return null when emptiness is a branch.

All twelve of these head/tail operations run in O(1) amortized time on ArrayDeque. On LinkedList they are also O(1), because the list keeps direct references to both endpoints. The cost difference between the two implementations shows up in other places (memory per element, cache behavior), not here.

A stack is a deque used from one end only. To make that pattern read naturally, Deque adds three stack-style methods: push, pop, and peek. They are aliases for the head-side operations.

peek() here is the Queue.peek() method, which Deque redefines to mean "look at the head". peek() returns null on an empty deque, and peekFirst() (the Deque form) also returns null. The two names point to the same call.

A classic use case for the stack pattern is undo. The shopping cart application records every action the user takes on a stack. When the user clicks "undo", the most recent action gets popped off and reversed.

Three actions get pushed in order. peek() shows the most recent one without removing it. pop() removes it and returns it, which is the action the application would undo. After the pop, peek() shows the next action down, which is the one the next undo click would target.

The stack methods are convenient, but they are cosmetic. actions.push(x) and actions.addFirst(x) produce the same behavior. Use the stack names when the code is conceptually a stack; use the deque names when both ends are in play.

push, pop, and peek are all O(1) on ArrayDeque. The amortized bound on push covers the occasional resize when the internal array fills up.

Java has a class called java.util.Stack. It has been around since Java 1.0, and it is the wrong class for new code.

Stack extends Vector, which is a synchronized, growable array. Every method on Vector (and therefore every method on Stack) acquires a lock, even when the program is not using more than one thread. That cost adds up, and it is not useful for code that does not need synchronization. Worse, because Stack extends Vector, every Vector method leaks through: add(int index, E element) on a Stack can insert into the middle, which makes the type's "stack" claim a suggestion rather than a guarantee.

ArrayDeque (the implementation behind most modern uses of Deque) is unsynchronized, doesn't expose middle-insertion methods through the Deque interface, and runs faster in single-threaded code. The official Stack Javadoc says exactly this: "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."

Here's the modern replacement side by side with the old way.

The two snippets produce the same result, but the Deque version is preferable. The only reason to touch java.util.Stack is to read old code that already uses it.

Two practical rules for new code:

A Deque covers both patterns from the same instance, which is one reason ArrayDeque shows up in so much modern Java code.

Some problems need to add at one end and remove from the other as a single rolling operation. A "recent orders" widget on a dashboard wants to show the last five orders, in arrival order. Every time a new order comes in, it gets added at the tail. If the window already has five orders, the oldest one at the head gets dropped. The deque handles both moves in O(1) without copying or shifting.

The first five orders go straight in. When order-6 arrives, the window is full, so removeFirst() evicts order-1. Then addLast("order-6") appends at the tail. The same thing happens for order-7, which evicts order-2. The final window holds orders 3 through 7, with the oldest at the head and the newest at the tail. Reading the window in order is just iterating the deque.

addLast and removeFirst on ArrayDeque are both O(1) amortized, so the whole sliding-window loop runs in O(n) for n incoming items. An ArrayList would also support this conceptually, but removeFirst() on an ArrayList is O(n) because it shifts every remaining element down by one slot.

Deque is an interface, so it can't be instantiated directly. Two classes implement it:

ArrayDeque is the modern default. It uses less memory per element than LinkedList, plays better with the CPU cache, and runs faster for the operations a deque actually needs.

LinkedList also implements Deque, so the same head/tail methods work on it. Two cases call for it. First, a variable already declared as LinkedList for positional List access can also be used as a deque without converting. Second, LinkedList accepts null elements, while ArrayDeque rejects them with NullPointerException. That difference matters in code where null is a meaningful value.

Here's the same program written against both implementations to show the interface is identical.

Both classes accept the same calls and produce the same logical result. The choice between them is about memory, performance, and the null question, not about syntax.

One trap to flag. ArrayDeque rejects null:

The throw happens immediately, on the first insert. ArrayDeque uses null internally as a sentinel for "no element here", so it can't tell a stored null apart from an empty slot. For storing null as a value, use LinkedList. The cleaner habit is to not store null at all, and let ArrayDeque enforce that.

A short program that exercises most of the surface in one place. The browser keeps a back stack and a forward stack. Navigating to a new page pushes the current page onto the back stack and clears the forward stack. Clicking "back" pops from the back stack and pushes the current page onto the forward stack. Clicking "forward" does the opposite.

Two deques, used purely as stacks via push and pop. Each navigation step has the same shape: push the current page onto the destination stack, then pop the new current page off the source stack. The forward stack only gets entries when the user clicks back, which matches typical browser behavior. Navigating to a new URL while the forward stack has entries clears the forward stack, which is the line forward.clear() in the initial two navigations.

The code reads naturally because the stack names match the intent. back.addFirst(current) and back.removeFirst() would do the same thing, but the program is about stacks, so push and pop fit the domain better. The same ArrayDeque type is also doing two different jobs (back and forward) without sharing state. Deque doesn't enforce a single role per instance, which is part of what makes it a flexible building block.