Queue, Deque and ArrayDeque

For this lesson, we'll focus on the Queue method families, Deque as both queue and stack, ArrayDeque internals, why it usually beats Stack and LinkedList, and the interview patterns you should write from memory: FIFO scheduling, BFS and a monotonic deque for sliding windows. We'll leave priority ordering to PriorityQueue and binary heaps and thread coordination to Blocking and concurrent queues at a glance.

01Picture it first: a circular waiting line

Think of an ArrayDeque as seats arranged in a circle, not a straight line. head marks the next person to serve. tail marks the next empty seat where a new person joins. When either marker reaches the end of the array, it wraps back to slot 0.

The trick is no shifting. Removing the front element clears one slot and moves head; adding at the back writes one slot and moves tail.

Fig. 1

ArrayDeque circular buffer with an Object array, head pointing to the first element, tail pointing to the next empty slot, and wrapped live elements occupying the end and beginning of the array

Notice the empty slot at tail. Internally, ArrayDeque keeps enough space to distinguish full from empty and grows when an add would make the markers collide. It does not store null elements, which lets poll, peek and empty slots all use null safely.

02Queue under the hood: two method families

The Queue interface gives every core operation two names. One family throws on failure. The other returns a special value. The right choice depends on whether failure is exceptional or expected.

For unbounded ordinary queues, add and offer usually both succeed. The difference matters for bounded queues such as ArrayBlockingQueue, where offer can say false instead of throwing.

Queue<String> jobs = new ArrayDeque<>();

System.out.println(jobs.peek());    // null
System.out.println(jobs.poll());    // null

// jobs.element();                  // NoSuchElementException
// jobs.remove();                   // NoSuchElementException

jobs.offer("reindex");
jobs.add("email-digest");

System.out.println(jobs.remove());  // reindex
System.out.println(jobs.poll());    // email-digest

Notice three things:

• peek and poll can return null, so ArrayDeque forbids storing null elements.
• offer reads better than add when queue capacity might matter.
• remove and element are fine when an empty queue means your program has a bug.

The scenario version shows up often: "You are scheduling jobs FIFO. Which collection do you use?" If this is single-threaded or externally synchronized, I use ArrayDeque<Job> and call offer and poll. If the prompt says producers must wait when the queue is full and consumers must wait when it is empty, I switch to a bounded BlockingQueue, usually ArrayBlockingQueue or LinkedBlockingQueue.

03Deque as both queue and stack