A request log keeps the last fifty events. Every new line appends, and the oldest line has to leave. The code uses an ArrayList: add at the tail is cheap, remove(0) slides every remaining element. Fifty is fine. Five hundred thousand in a hot path is a tax you pay on every write.

Someone else keeps a stack for undo and a queue for the worker, two collections that are the same sequence with different ends. Both jobs are one layout.

A deque is a sequence you can push and pop at either end in O(1). Not two structures glued together. Not a list you pretend is a queue. Terms such as ADT, amortized cost, and contiguous vs linked live on the Data Structures Roadmap; this post is the layout.

The ADT: four verbs

A deque (double-ended queue) is the contract, not the array. Four operations define it:

OperationJob
addFirstInsert at the front
addLastInsert at the back
removeFirstTake the front
removeLastTake the back

Peek variants (getFirst / getLast, or peekFirst / peekLast) read an end without removing it. That is the whole ADT. Index i is not part of it. Search is not part of it. If those are your hot operations, you picked the wrong shape.

A stack is a deque that only uses one end. A queue is a deque that inserts at one end and removes at the other. You do not need a second type for either job — you need the discipline to touch the right end.

Structure: deque (ArrayDeque)
addFirst / addLast       amortized O(1)
removeFirst / removeLast O(1)
peekFirst / peekLast     O(1)
get(i)                   not the ADT — do not ask
search                   O(n)

Pick it for the ends. Everything else is a scan.

How ArrayDeque keeps both ends cheap

java.util.ArrayDeque is a ring buffer: a contiguous array plus two indices, head (the first element) and tail (the next empty slot at the back). The logical sequence wraps around the physical end of the array.

index:  0  1  2  3  4  5  6  7
slot:   D  E  _  _  _  A  B  C
              ^tail    ^head

logical order: A, B, C, D, E   (head wraps past 7 to 0)

addLast writes at tail and advances tail. addFirst moves head backward and writes there. removeFirst clears head and advances it. removeLast backs tail up. When an index walks off either edge, it wraps with a mask — ArrayDeque keeps the capacity a power of two so wrap is a bitwise AND, not a modulo.

No element slides. The array is a circle of slots. That is why both ends are O(1): you are moving an index, not memmoving a prefix.

When the ring is full, the implementation allocates a larger array (typically double), copies the wrapped sequence into a linear layout, and resets head and tail. Same story as a dynamic array: usually O(1), occasionally O(n), amortized O(1). The glossary on the roadmap already warned that amortized is not a guarantee on the next call.

Note: ArrayDeque does not allow null. Empty slots are null in the backing array; a payload null would be indistinguishable from a hole. If you need nulls, that is a smell in the model, not a reason to switch layouts.

Why LinkedList is not the default deque

LinkedList implements Deque. It is a valid implementation. It is a poor default.

Each element is a node: pointers, object header, the payload. Insert and remove at the ends are O(1) after you pay for the allocation and the pointer chase. A ring buffer stays in one block. Sequential scans hit cache. A linked list walks the heap.

LinkedList also implements List, which invites get(i) — an O(n) walk dressed as random access. ArrayDeque does not implement List. You cannot ask for index i without noticing you left the ADT.

Program to Deque, construct ArrayDeque. Reach for LinkedList when you already need the list API and the ends, or when you hold a node and need to splice. That combination is rare in application code. For a stack, a queue, or a sliding window, the ring buffer wins.

One type, three jobs

The same four verbs cover the shapes you actually ship.

Stack (LIFO)

Undo, matching braces, DFS-style work: insert and remove at the same end.

Deque<String> undo = new ArrayDeque<>();
undo.push("type a");   // addFirst
undo.push("type b");
String lastEdit = undo.pop(); // "type b" — removeFirst

push / pop / peek on Deque are the first-end operations. Prefer this over java.util.Stack, a synchronized subclass of Vector. The name matches the textbook. The layout is the wrong decade.

Queue (FIFO)

Workers, buffers, BFS-style work: insert at the back, remove at the front.

Deque<Runnable> jobs = new ArrayDeque<>();
jobs.addLast(() -> persist(order));
jobs.addLast(() -> email(order));
Runnable next = jobs.removeFirst();
next.run();

Queue methods (offer, poll, peek) sit on the same object. A deque is a queue when you only use those two ends that way.

Sliding window

Keep the last n items: add at the back, drop from the front when the window is full. That is the request-log example with an O(1) bill.

int window = 50;
Deque<Request> recent = new ArrayDeque<>(window + 1);

void onRequest(Request req) {
    recent.addLast(req);
    if (recent.size() > window) {
        recent.removeFirst();
    }
}

Some window-maximum algorithms keep a deque of candidates (indices or values in decreasing order) so the front is always the current max. Same ADT, extra invariant. The layout job is unchanged: cheap drops at the front, cheap appends at the back.

Work-stealing pools (the JDK ForkJoinPool) give each worker a deque. The owner pushes and pops at one end (LIFO, which keeps related tasks hot in cache). An idle worker steals from the other end (FIFO, which takes the oldest, coarsest work). Two ends are the whole trick. You will not implement that pool; you will recognize why it is a deque and not a stack plus a queue.

Java: Deque and ArrayDeque

Declare the interface, pick the ring buffer:

Deque<String> events = new ArrayDeque<>();
events.addLast("login");
events.addFirst("boot");
String oldest = events.removeFirst();
String newest = events.removeLast();

Exception vs sentinel pairs matter at call sites:

Throws on failureReturns a sentinel
addFirst / addLast (full, if bounded)offerFirst / offerLast
removeFirst / removeLast (empty)pollFirst / pollLast
getFirst / getLast (empty)peekFirst / peekLast

On ArrayDeque, capacity grows, so add* and offer* behave the same for space. The empty-safe remove/get pair still matters: removeFirst throws NoSuchElementException; pollFirst returns null. Pick one style and stick to it. Mixing them is how a null from poll becomes an NPE three lines later.

Java 21 folded getFirst / getLast into a shared vocabulary for any ordered collection. Deque already had those methods; sequenced collections made lists, ordered sets, and deques speak the same language. That API is Sequenced Collections: First, Last, and Reversed Without the Ceremony. This post stays on the ring buffer underneath.

Note: ArrayDeque is not thread-safe. Concurrent modification from two threads is a data race, not a ConcurrentModificationException you can rely on.

When not to use a deque

A deque is the wrong default when the hot operation is not an end.

  • You need index i — recent.get(17), shuffle, binary search, or a List parameter. Use ArrayList. ArrayList.add(0, x) is O(n); that is the cost of keeping random access. Do not fake an index on a deque by iterating i times.
  • You need a blocking, concurrent hand-off. Producer waits when full, consumer waits when empty: BlockingDeque (LinkedBlockingDeque) or a blocking queue. Lock-free concurrent ends: ConcurrentLinkedDeque. Those are different types with different contracts. Wrapping ArrayDeque in Collections.synchronizedDeque does not give you waiting, and it is a poor substitute for a concurrent collection.
  • You need List methods (set, subList, listIterator at an index). That is a list. A deque that also implements List (LinkedList) will compile and then surprise you on get(i).
  • You need null elements. ArrayDeque refuses them. Usually the model should refuse them too.

If the job is “next-best item” (priority, leaderboard), a deque is not a heap. If the job is uniqueness, a deque is not a set. Same four verbs, wrong question.

Cheat sheet

ADT:     addFirst / addLast / removeFirst / removeLast  (all O(1) ends)
JDK:     Deque<E> events = new ArrayDeque<>();
Layout:  ring buffer — head/tail indices, wrap, grow by doubling
Stack:   push/pop at the same end (not java.util.Stack)
Queue:   addLast + removeFirst
Window:  addLast, removeFirst when size > n
Steal:   owner uses one end, thief uses the other
Avoid:   LinkedList as default; nulls; get(i); raw concurrent access

Do:

  • Program to Deque, construct ArrayDeque.
  • Use one deque as a stack or a queue or a window by choosing ends, not extra types.
  • Treat growth as amortized O(1), same as a dynamic array.

Don’t:

  • Call remove(0) on an ArrayList to drop the oldest item in a hot path.
  • Reach for java.util.Stack or LinkedList because the name matches the textbook.
  • Ask a deque for index i, or ask ArrayDeque to block across threads.

Wrap-up

A deque is both ends of a sequence at O(1), delivered in the JDK by a ring buffer. Stack, queue, and sliding window are the same type with a choice of ends. Work-stealing is the same type with two owners on opposite ends.

Reach for ArrayDeque unless you need an index, a blocking concurrent hand-off, or a real List. For the glossary behind ADT, amortized cost, and contiguous vs linked — and the rest of the series index — start at the Data Structures Roadmap.

Next optional step in the series Expected O(1) lookup when uniqueness or keys are the job. Hash Tables: Buckets and Collisions