Part 7 — Queue & Deque Deep Dive¶

Queues are heavily used in multithreading, message processing, graph algorithms, task scheduling, and system design.

Senior interview questions often include:

• Why is ArrayDeque preferred over Stack?
• How does PriorityQueue work internally?
• Difference between Queue, Deque, and BlockingQueue
• Real-world producer-consumer implementations

1. What is a Queue?¶

A Queue follows the FIFO (First In, First Out) principle.

Example:

Queue

Front                    Rear

[A] -> [B] -> [C]

Remove here          Insert here

Example:

Queue<String> queue = new LinkedList<>();

queue.offer("A");
queue.offer("B");
queue.offer("C");

System.out.println(queue.poll());

Output:

A

2. Queue Interface Hierarchy¶

Iterable
    │
Collection
    │
Queue
    │
+-----------------------------+
| PriorityQueue               |
| LinkedList                  |
| ArrayDeque (via Deque)       |
| ConcurrentLinkedQueue        |
| BlockingQueue implementations|
+-----------------------------+

3. Queue Operations¶

Example:

Queue<Integer> q = new LinkedList<>();

q.offer(10);
q.offer(20);

System.out.println(q.peek());

Output:

10

Queue remains unchanged.

add() vs offer()¶

queue.add(item);

• Throws an exception if insertion fails.

queue.offer(item);

• Returns false if insertion fails.

For bounded queues, offer() is generally preferred because failure is handled without exceptions.

remove() vs poll()¶

Empty queue:

queue.remove();

Throws:

NoSuchElementException

queue.poll();

Returns:

null

element() vs peek()¶

Empty queue:

queue.element();

Throws exception.

queue.peek();

Returns:

null

4. Deque¶

Deque means:

Double Ended Queue

Operations:

Front <-------> Rear

Insert Front

Insert Rear

Delete Front

Delete Rear

Supports:

• Queue
• Stack

using the same implementation.

5. ArrayDeque¶

Interview favorite.

Deque<Integer> deque = new ArrayDeque<>();

Internally:

• Circular array
• No linked list
• No synchronization

Memory:

0 1 2 3 4 5 6 7

↓

Array

Head and tail indices wrap around the array.

6. Circular Array¶

Example:

Capacity = 8

Head = 6

Tail = 1

Memory:

0 1 2 3 4 5 6 7

B C _ _ _ _ A

The logical order is:

A

↓

B

↓

C

The array wraps around instead of shifting elements.

7. Why ArrayDeque is Faster Than LinkedList¶

LinkedList:

Each element is a separate node.

Node

↓

Node

↓

Node

Memory:

• Many object allocations
• Extra references
• Poor CPU cache locality

ArrayDeque:

Array

↓

Contiguous memory

Advantages:

• Better cache locality
• Fewer allocations
• Faster iteration

8. Why Stack is Legacy¶

Java provides:

Stack<Integer> stack = new Stack<>();

But interviews expect:

Deque<Integer> stack = new ArrayDeque<>();

Reasons:

• Stack extends Vector
• All operations are synchronized
• Higher overhead
• Legacy API

Modern Java code prefers ArrayDeque for stack behavior.

9. Stack Using Deque¶

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);

stack.push(20);

stack.pop();

Output:

20

LIFO.

10. Queue Using Deque¶

Deque<Integer> q = new ArrayDeque<>();

q.offer(10);

q.offer(20);

q.poll();

Output:

10

FIFO.

11. PriorityQueue¶

Another interview favorite.

Unlike a normal queue:

Arrival order

↓

Execution order

PriorityQueue:

Highest Priority

↓

Executed first

12. Internal Data Structure¶

PriorityQueue uses:

Binary Heap

Not:

• Red-Black Tree
• HashMap
• Linked List

Memory:

Array

↓

Heap

13. Min Heap¶

Default PriorityQueue:

        10
      /    \
    20      30
   /  \
 40   50

Root:

10

Always the smallest element.

14. Heap Property¶

Every parent:

<= children

Not fully sorted.

Only partially ordered.

15. Insert¶

Insert:

40

Heap:

      10
     /   \
   20     30
  /
40

Insert:

5

Initially:

      10
     /   \
   20     30
  / \
40  5

Heapify Up:

      5
     /  \
   10   30
  / \
40 20

16. Remove¶

Removing root:

5

Move last element:

20

Heapify Down:

      10
     /  \
   20   30
  /
40

Complexity:

O(log n)

17. PriorityQueue Complexity¶

Notice:

contains() is not O(log n) because the heap is not globally sorted.

18. Custom Comparator¶

Max heap:

PriorityQueue<Integer> pq =
    new PriorityQueue<>(Comparator.reverseOrder());

Largest element first.

19. BFS¶

Breadth First Search:

      A
    /   \
   B     C
  / \   /
 D   E F

Uses:

Queue<Node>

Traversal:

A

↓

B C

↓

D E F

20. Producer-Consumer¶

Classic interview topic.

Producer:

Generate task

↓

Queue

Consumer:

Take task

↓

Process

Typically implemented using a BlockingQueue.

21. BlockingQueue¶

Unlike a normal queue:

If empty:

take()

↓

wait

If full:

put()

↓

wait

Perfect for multithreaded applications.

Common implementations:

ArrayBlockingQueue

LinkedBlockingQueue

PriorityBlockingQueue

DelayQueue

SynchronousQueue

22. ConcurrentLinkedQueue¶

Non-blocking.

Uses:

• CAS (Compare-And-Set)
• Lock-free algorithms

Suitable for:

• High-concurrency systems
• Low-latency applications

23. Real-World Uses¶

Queue¶

• Printer jobs
• Request processing
• Event queues

Deque¶

• Undo/Redo
• Browser history
• Sliding window algorithms

PriorityQueue¶

• CPU scheduling
• Dijkstra's algorithm
• A* search
• Task prioritization

BlockingQueue¶

• Thread pools
• Producer-consumer pipelines
• Logging systems

Common Interview Questions¶

Q1. Difference between Queue and Deque?¶

Queue:

One insertion end.

One removal end.

Deque:

Insertion and removal at both ends.

Q2. Why is ArrayDeque preferred over Stack?¶

• No unnecessary synchronization
• Better performance
• Modern API
• Implements both stack and queue operations

Q3. Why isn't PriorityQueue sorted?¶

Because it is a heap, not a sorted list.

Only the root is guaranteed to be the highest (or lowest) priority element.

Q4. Complexity of PriorityQueue insertion?¶

O(log n)

Q5. Complexity of peek()?¶

O(1)

Q6. Why doesn't PriorityQueue support binary search?¶

Because the heap is only partially ordered.

Q7. Which queue is thread-safe?¶

Examples:

• LinkedBlockingQueue
• ArrayBlockingQueue
• PriorityBlockingQueue
• ConcurrentLinkedQueue (thread-safe but non-blocking)

A plain LinkedList or ArrayDeque is not thread-safe.

Q8. Difference between BlockingQueue and Queue?¶

Queue:

Returns immediately.

BlockingQueue:

Can wait when empty or full.

Q9. Can ArrayDeque store null?¶

No.

It throws:

NullPointerException

This allows null to remain the sentinel return value for methods like poll().

Q10. Which collection would you choose for a task scheduler?¶

Usually:

PriorityQueue

or

DelayQueue

depending on whether tasks are ordered by priority or scheduled execution time.

Comparison Table¶

Senior Interview Scenario¶

Question:

Why is ArrayDeque recommended instead of Stack?

Strong Answer:

Stack is a legacy class that extends Vector, so every operation is synchronized, adding unnecessary overhead in single-threaded use. ArrayDeque uses a circular array, avoids synchronization, has better cache locality, and supports both stack and queue operations through the Deque interface. For modern Java applications, it is generally the preferred choice unless synchronization is specifically required.

Key Takeaways¶

• Queue implements FIFO.
• Deque supports both FIFO and LIFO operations.
• ArrayDeque is the preferred replacement for Stack.
• PriorityQueue is implemented using a binary heap, not a tree.
• PriorityQueue provides O(log n) insertion and removal, with O(1) access to the highest-priority element.
• BlockingQueue is fundamental for producer-consumer patterns.
• Choosing the correct queue implementation depends on ordering requirements, concurrency needs, and performance characteristics.

Next: Part 8 — Concurrent Collections Deep Dive (Most Important for Senior Java)¶

We'll cover:

• Why HashMap fails in multithreading
• ConcurrentHashMap internals (Java 8)
• CAS (Compare-And-Set)
• Lock striping and bucket-level synchronization
• CopyOnWriteArrayList
• ConcurrentLinkedQueue
• BlockingQueue
• ConcurrentSkipListMap
• WeakHashMap, IdentityHashMap, EnumMap
• Real production scenarios and senior interview questions