CodeWithYash

Foundation · Module 11 · Lesson 3

Deque

Efficient updates at both ends.

15–25 min readLesson 60 of 123

Lesson 60 of 123

1d streak

Double-Ended Queue (Deque): The Universal Sequential Primitive

A Deque (Double-Ended Queue, pronounced "deck") allows insertion and deletion at both the front and the back in O(1) time. Because it subsumes both Stack (LIFO) and Queue (FIFO) capabilities, modern language libraries (like Java and Python) recommend Deque as the primary sequential buffer.

Deque Dual-Ended Operations Layout
       addFirst(x)                           addLast(x)
       removeFirst()                         removeLast()
       peekFirst()                           peekLast()
            |                                     |
            v                                     v
       +----------+----------+----------+----------+
FRONT  |    10    |    20    |    30    |    40    |  BACK (REAR)
       +----------+----------+----------+----------+
            ^                                     ^
            |                                     |
       Head Pointer                          Tail Pointer
Role DesiredDeque Method (Add)Deque Method (Remove)Deque Method (Inspect)
Stack (LIFO)push(x) / addFirst(x)pop() / removeFirst()peek() / peekFirst()
Queue (FIFO)offer(x) / addLast(x)poll() / removeFirst()peek() / peekFirst()
Double-EndedaddFirst(x) / addLast(x)removeFirst() / removeLast()peekFirst() / peekLast()

Architectural Boundary · Do Not Confuse

Concept A

ArrayDeque (Circular Dynamic Buffer)

Concept B

LinkedList (Doubly Linked Nodes)

ArrayDeque is backed by a circular resizable array with zero node allocation overhead and superior CPU cache locality. LinkedList allocates a 24-32 byte Node object for every single element inserted. In 99% of benchmarks, ArrayDeque is 3-5x faster than LinkedList.

Why java.util.Stack is Deprecated in Practice

Never use java.util.Stack in modern Java. It extends the legacy Vector class, making every method synchronized. This causes severe lock acquisition overhead even in single-threaded programs. Java official documentation explicitly recommends Deque<Integer> stack = new ArrayDeque<>().

Cost Model

Complexity & Trade-offs

Either-end operation
O(1)
O(n) stored
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Nested parsing, undo, arrival order, buffering, and nearest-greater queries.
  • BFS frontiers and producer/consumer scheduling.
  • Maintaining range extremes or constrained access.

Common mistakes

  • Reading from an empty structure.
  • Confusing the logical front with an array index in a circular buffer.
  • Missing the amortized argument for transfers or monotonic pops.

Practice prompts

  • Reproduce the worked Deque example without looking at the trace.
  • Change one input condition and explain whether the Deque invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.