1. Introduction to the Deque Interface

The variable's type communicates which operations the code relies on, while the implementation can be changed later if the requirements change.

3. Understanding the Head and Tail

A deque has two named endpoints:

• Head / first: the front of the deque.
• Tail / last: the back of the deque.

Methods ending in First operate on the head. Methods ending in Last operate on the tail. Learning this naming pattern makes the large method list much easier to understand.

Imagine the deque contains three pages:

If a new element is added with addFirst, it becomes the new head. If it is added with addLast, it becomes the new tail. Similarly, removeFirst removes the head, while removeLast removes the tail.

A deque does not require the head to be the oldest item or the newest item. That depends on how the program inserts and removes elements. For a FIFO queue, add at the tail and remove from the head. For a stack, add and remove at the head.

4. The Three Operations at Each End

At either end, a deque supports three conceptual operations:

1. Insert: place a new element at the selected end.
2. Remove: take an element away from the selected end and return it.
3. Examine: read the element at the selected end without removing it.

Each operation has method names for the first and last ends. The insertion, removal, and examination methods also come in exception-based and special-return-value forms.

Method matrix

The methods with add, remove, or get in these pairs generally throw an exception if the operation cannot be completed. The corresponding offer, poll, or peek methods use a return value to communicate the outcome.

This distinction is especially important when the deque is empty. removeFirst() throws NoSuchElementException, while pollFirst() returns null. getFirst() throws when there is no first element, while peekFirst() returns null.

5. Insertion Methods: addFirst, offerFirst, addLast, and offerLast

The insertion methods add an element to one of the two ends.

• addFirst(e) inserts at the head and throws if insertion cannot be completed.
• offerFirst(e) attempts insertion at the head and returns a boolean indicating success.
• addLast(e) inserts at the tail and throws if insertion cannot be completed.
• offerLast(e) attempts insertion at the tail and returns a boolean indicating success.

For ordinary, non-capacity-restricted ArrayDeque usage, addFirst and offerFirst normally both succeed when a non-null element is supplied. The distinction matters for implementations or situations where insertion may fail, especially bounded queue implementations in the broader Queue family.

A short illustration:

The deque now has Urgent Task at the head, followed by Task A and Task B. The calls did not sort the tasks or automatically decide their urgency. The program chose the placement by using addFirst for the urgent task.

Use offer when the code wants to handle a failed insertion as an ordinary outcome. Use add when failure should be surfaced as an exception.

6. Removal Methods: removeFirst, pollFirst, removeLast, and pollLast

Removal methods return the element they remove.

• removeFirst() removes and returns the head; it throws NoSuchElementException if the deque is empty.
• pollFirst() removes and returns the head; it returns null if the deque is empty.
• removeLast() removes and returns the tail; it throws NoSuchElementException if the deque is empty.
• pollLast() removes and returns the tail; it returns null if the deque is empty.

Example:

The first call removes Order 1; the second removes Order 3. Order 2 remains in the deque.

This is useful when a workflow must process the oldest item and sometimes discard or retrieve the newest item. For a standard FIFO queue, use offerLast to insert and pollFirst to retrieve. For a stack, use push and pop, or the equivalent head methods.

7. Examination Methods: getFirst, peekFirst, getLast, and peekLast

Examination methods read an endpoint without changing the deque.

• getFirst() returns the head and throws if the deque is empty.
• peekFirst() returns the head or null if empty.
• getLast() returns the tail and throws if the deque is empty.
• peekLast() returns the tail or null if empty.

For example, if a deque contains Page A, Page B, and Page C, then peekFirst() returns Page A and peekLast() returns Page C. Neither method removes anything, so the size remains three.

This is an important distinction: peeking is not popping. A program can inspect the next element to decide what to do, while leaving it available for a later operation.

Choose peek when an empty deque is an expected condition that the program can handle. Choose get when the deque is required to contain an element and an empty deque indicates a problem.

8. Exception-Based Methods vs Special Return Values

Deque's paired method names provide two ways to handle unsuccessful operations.

This is not just a naming detail. It lets the code express its expectations.

If an empty deque means “there is currently no work,” a special-value method is often convenient:

If an element must exist at that point in the program, removeFirst() may be more appropriate because it reveals a broken assumption immediately.

One caveat: because null is used by the special-value methods to indicate the absence of an element, storing null in a deque can make the meaning of a returned null ambiguous. ArrayDeque avoids this ambiguity by rejecting null elements.

9. Using Deque as a FIFO Queue

A FIFO queue processes elements in the order they were added: first in, first out. To use a deque this way, insert at the tail and remove from the head.

Example:

The jobs are processed in arrival order: Report.pdf, Invoice.pdf, and Schedule.pdf.

This approach suits simple work queues, print jobs, pending operations, and other cases where the oldest waiting item should be handled next. For multi-threaded producer-consumer coordination, however, a normal ArrayDeque is not thread-safe; a suitable BlockingQueue is usually a better fit.

10. Using Deque as a LIFO Stack

A stack follows Last In, First Out (LIFO). The newest item is removed first. A deque can provide this behavior by using only its head.

Deque includes stack-style method names:

Example:

latestAction is Applied coupon, because that was the last action pushed. The next call to pop() would return Changed quantity.

The stack method names are aliases for head-side deque operations. Use push, pop, and peek when the data structure is conceptually a stack. Use the First and Last names when the program works with both ends.

Queue and stack behavior in one structure

Java includes java.util.Stack, a legacy class that extends Vector. For new code that needs ordinary single-threaded stack behavior, the Deque interface with an ArrayDeque implementation is generally preferred.

There are several reasons:

1. A clearer stack abstraction: Deque exposes operations at the ends rather than the indexed operations of a general-purpose vector.
2. Avoiding unnecessary synchronization overhead: Vector and Stack synchronize their methods. That does not automatically make a multi-operation workflow thread-safe, and it may add overhead when synchronization is not needed.
3. Flexible use: The same deque can act as a stack or queue, depending on the operations used.
4. Modern API guidance: Java's Stack documentation recommends using Deque implementations for a more complete and consistent set of LIFO operations.

A typical modern declaration is:

This does not mean ArrayDeque is thread-safe. It is not designed for unsynchronized concurrent modification by multiple threads. If multiple threads need coordinated access, select an appropriate concurrent design instead.

12. Sliding Windows and Keeping Recent Items

A sliding window maintains a limited number of recent elements. For example, a dashboard might display only the five most recently received orders, with the oldest displayed order removed whenever a new order arrives.

A deque makes this pattern natural:

1. Add each new item at the tail.
2. If the number of items exceeds the window limit, remove an item from the head.
3. Iterate from head to tail to display the current window.

4. Whiteboard

   Loading diagram...

   
   

For example, with a window size of five, the deque initially holds orders 1 through 5. When order 6 arrives, order 1 is removed from the head and order 6 is appended at the tail. The deque now represents orders 2 through 6. Repeating the process maintains a rolling window without shifting every remaining element as an array list would when removing its first element.

For ArrayDeque, adding or removing at an end is O(1) amortized. Thus, maintaining the window over n incoming items takes O(n) total time, assuming each item is inserted once and each eviction is performed at most once.

13. Browser Back and Forward Navigation

A browser's history is a useful illustration of how a deque can support stack-like behavior. A common simplified design uses two stacks:

• Back history: pages the user can return to.
• Forward history: pages the user can move forward to after going back.

When the user navigates to a new page, the current page is pushed onto the back history and the forward history is cleared. When the user clicks Back, the current page moves to forward history and the most recent page from back history becomes current. Forward navigation performs the opposite movement.

Two ArrayDeque instances can represent the two histories. Each uses push and pop to manage the most recently visited page. This is a simplified model; a production browser needs additional rules for URLs, redirects, tab state, and navigation events.

The lesson is broader than browser history: when the most recent item should be the first one retrieved, a stack-oriented use of Deque often matches the problem naturally.

14. ArrayDeque vs LinkedList

Both ArrayDeque and LinkedList implement Deque, so they share the same interface methods. The differences lie in their internal storage and other supported behaviors.

ArrayDeque is usually the default choice for new code that needs a stack or queue. Its array-based storage typically uses memory more efficiently and can have better cache behavior than a linked list.

LinkedList can still be reasonable when the program already needs its List capabilities or has a specific reason to use linked nodes. Its ability to store null is a difference, but using null as a regular deque element is usually best avoided because null is commonly used to signal that poll or peek found no element.

15. Why ArrayDeque Rejects Null

ArrayDeque does not permit null elements. Attempting to insert null throws NullPointerException.

This restriction supports clear empty-deque semantics. Methods such as pollFirst(), pollLast(), peekFirst(), and peekLast() return null when no element is available. If a real null value could also be stored, the caller would not be able to distinguish “the deque is empty” from “the returned element is a stored null.”

The simplest practice is to avoid storing null in a deque. If an application has optional data, represent absence explicitly with a separate condition or an appropriate wrapper rather than relying on null as an ordinary element.

Although LinkedList permits null, that does not automatically make null a good choice for queue-like processing. The meaning of a null returned by a polling operation can become ambiguous if null elements are present.

16. Performance and Time Complexity

The common end operations are efficient on both principal implementations, though their internal costs differ slightly.

Amortized O(1) means that an operation is constant-time on average across a sequence of operations, even though an occasional array resize can take longer. LinkedList does not need to resize an array, but each element requires a node and link references.

Do not assume that every operation on a deque is constant-time. Searching for a value or removing an arbitrary matching object requires finding it, which can take linear time. A deque is optimized for endpoint operations, not for arbitrary indexed access or fast membership tests.

17. Common Mistakes to Avoid

Mistake 1: Mixing up the ends

addFirst and addLast place an element at different ends. Similarly, pollFirst and pollLast remove different elements. Choose the method based on the intended behavior rather than treating all deque methods as interchangeable.

Mistake 2: Expecting FIFO behavior from every use of Deque

A deque supports FIFO only when the code inserts at the tail and removes from the head. If it uses push and pop, it behaves like a stack instead.

Mistake 3: Confusing peek with removal

peekFirst() and peekLast() do not change the deque. pollFirst() and pollLast() do. Use the inspection methods when the element must remain available.

Mistake 4: Ignoring the empty case

removeFirst() and getFirst() throw when the deque is empty. The poll and peek variants return null instead. Select the form that matches the application's expected control flow.

Mistake 5: Storing null in an ArrayDeque

ArrayDeque rejects null. Even with an implementation that permits null, using it as an ordinary element can make an empty result difficult to distinguish from a stored null.

Mistake 6: Using ArrayDeque as a thread-safe queue

ArrayDeque is not synchronized and is not designed for concurrent mutation by multiple threads. Use a suitable concurrent collection, such as a BlockingQueue, when producer-consumer coordination across threads is required.

Mistake 7: Using Stack for new stack code without considering Deque

For ordinary new LIFO code, Deque with ArrayDeque is the modern recommendation. It provides clear stack operations without inheriting the full indexed API of Vector.

18. Best Practices for Working with Deque

• Declare variables using Deque<E> when only deque behavior is required.
• Prefer ArrayDeque for typical single-threaded queue and stack tasks.
• Use offerLast with pollFirst for FIFO behavior.
• Use push, pop, and peek when the structure represents a stack.
• Use the First and Last methods explicitly when both ends matter.
• Choose exception-based methods when an empty deque violates a program invariant; choose special-value methods when emptiness is expected.
• Avoid storing null elements.
• Do not assume ArrayDeque is thread-safe.
• Use a BlockingQueue or another concurrency-appropriate type for cross-thread producer-consumer workflows.
• Remember that endpoint operations are efficient, but searching for an arbitrary value is linear-time.

19. Choosing the Right Structure

No collection is best for every task. The right choice depends on the operations the program needs, whether it must coordinate multiple threads, and which ordering rule the application expects.

20. Quick Revision

• Deque means double-ended queue.
• It extends Queue, which extends Collection.
• The head is the first end; the tail is the last end.
• addFirst and offerFirst insert at the head.
• addLast and offerLast insert at the tail.
• removeFirst and removeLast throw if the deque is empty.
• pollFirst and pollLast return null when the deque is empty.
• getFirst and getLast inspect endpoints and throw if empty.
• peekFirst and peekLast inspect endpoints and return null if empty.
• push, pop, and peek provide stack-style operations at the head.
• Use tail insertion and head removal for FIFO behavior.
• Use head insertion and head removal for LIFO behavior.
• ArrayDeque is generally the preferred implementation for ordinary stack and queue use.
• ArrayDeque rejects null and is not thread-safe.
• LinkedList also implements Deque, but usually has greater per-element memory overhead.
• Endpoint operations are O(1) amortized for ArrayDeque; searching for a value is O(n).

21. Conclusion

The Java Deque interface is a flexible building block because it exposes both ends of a collection. With a small set of consistently named methods, it can model a FIFO queue, a LIFO stack, a rolling window, or other workflows that need efficient endpoint operations.

The most useful skill is recognizing the intended pattern. Use offerLast and pollFirst when processing items in arrival order. Use push and pop when the newest item should be handled first. Use First and Last methods when the application needs control over both ends.

For most ordinary single-threaded stack and queue tasks, ArrayDeque is the recommended starting point. Choose LinkedList only when its additional list behavior or other specific properties justify it, and choose a concurrent queue implementation when threads must coordinate access. Matching the implementation and method choices to the required behavior makes collection code easier to read, more predictable, and easier to maintain.