Queue & Deque in Java

Queues and Deques are important interfaces in the Java Collections Framework used for storing elements in a specific order — mainly for FIFO and LIFO operations. They are widely used in real-world systems like task scheduling, messaging systems, caching, BFS traversal, and more.

Both Queue and Deque are part of the java.util package.

Queue in Java

A Queue is a linear data structure that stores elements in FIFO (First In, First Out) order.

The element inserted first is processed first — just like:

• People standing in line
• CPU job scheduling
• Tasks waiting in a printer queue

Queue is an interface under java.util.

Queue Hierarchy

Iterable
   └── Collection
          └── Queue
               ├── LinkedList
               ├── PriorityQueue
               └── ArrayDeque

Key Characteristics of Queue

• Follows FIFO order
• Allows duplicates
• Allows null (depends on implementation)
• No random access (unlike List)
• Used in scheduling, buffering, producer–consumer problems

Important Queue Methods

Notes

• add() vs offer() → offer() is safer
• remove() vs poll() → poll() is safer

Common Queue Implementations

1. LinkedList

• Implements Queue
• Allows null
• Maintains FIFO

2. PriorityQueue

• Orders elements by priority, not insertion order
• Uses Min-Heap internally
• Does not allow null
• Not thread-safe

3. ArrayDeque

• Faster than LinkedList
• No null allowed
• Works as both Queue and Stack

Example: Queue Using LinkedList

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

queue.offer("Java");
queue.offer("Python");
queue.offer("C++");

System.out.println(queue.poll()); // Java
System.out.println(queue.peek()); // Python

Deque in Java

A Deque (Double-Ended Queue) allows insertion and deletion from both front and rear.

• Works as FIFO (Queue)
• Works as LIFO (Stack)

Deque is also an interface in java.util.

Deque Hierarchy

Iterable
   └── Collection
          └── Queue
                └── Deque
                     ├── LinkedList
                     └── ArrayDeque

Important Deque Methods

Insertions

• addFirst(e) → Inserts at front
• addLast(e) → Inserts at rear
• offerFirst(e) → Inserts at front (safe)
• offerLast(e) → Inserts at rear (safe)

Removals

• removeFirst() → Removes first element (exception if empty)
• removeLast() → Removes last (exception if empty)
• pollFirst() → Removes first element (null if empty)
• pollLast() → Removes last (null if empty)

Access / Peeking

• getFirst() → Gets first element (exception if empty)
• getLast() → Gets last (exception if empty)
• peekFirst() → Gets first element (null if empty)
• peekLast() → Gets last (null if empty)

Common Implementations of Deque

1. ArrayDeque

• Very fast
• No null allowed
• Not thread-safe
• Best replacement for Stack
• Better performance than LinkedList

2. LinkedList

• Implements both Queue & Deque
• Allows null
• Slower than ArrayDeque

Example: Deque Using ArrayDeque

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

deque.addFirst("A");
deque.addLast("B");
deque.addLast("C");

System.out.println(deque.pollFirst()); // A
System.out.println(deque.pollLast());  // C

Queue vs Deque

When to Use What?

Use Queue when:

• You need FIFO
• Task scheduling
• Producer-consumer
• BFS algorithms

Use Deque when:

• You need both FIFO + LIFO
• Implementing Stack (ArrayDeque > Stack class)
• Faster Queue operations
• Algorithms like sliding window, palindrome checking

Points to Remember

• Queue → FIFO
• Deque → Double-ended (FIFO + LIFO)
• PriorityQueue → Ordered queue (min-heap)
• ArrayDeque → Fastest for Queue & Stack
• LinkedList → Can act as Queue & Deque

Use Queue for simple FIFO tasks.

Use Deque when you need more powerful two-ended operations.