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

Method	Description
add(e)	Inserts element, throws exception on failure
offer(e)	Inserts element, returns false if failed (safe)
remove()	Removes head, throws exception if empty
poll()	Removes head, returns null if empty
element()	Returns head without removing, exception if empty
peek()	Returns head without removing, null if empty

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

Feature	Queue	Deque
Order	FIFO	FIFO + LIFO
Insert	Rear	Both ends
Remove	Front	Both ends
Flexibility	Limited	Very flexible
Best Implementation	LinkedList / PriorityQueue / ArrayDeque	ArrayDeque

---

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.