Queue and Deque Interfaces | Java Subject Material

Step 1 of 13

4.1 Introduction to Queue

Learning objective

Explain FIFO processing, identify the front and rear, and name common Queue implementations.

A Queue stores elements for processing, normally according to First In, First Out. A line of students at a fee counter is a familiar example: the first student to join is served first.

Queue interface relationship

public interface Queue<E> extends Collection<E>

Reading a queue

Front -> A, B, C <- Rear. A is removed first.

Common Queue implementations

PriorityQueue
LinkedList
ArrayDeque

Check your understanding: In a FIFO queue containing A, B, C, which value leaves first?

A, because it entered first and is at the front.

Step 2 of 13

4.2 Queue Methods

Learning objective

Choose between exception-throwing and special-value queue operations.

Two families of Queue methods
Operation	Throws an exception	Returns a special value
Insert	add()	offer()
Remove	remove()	poll()
Examine front	element()	peek()

Adding elements

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

Behavior when an operation cannot complete

add() may throw an exception; offer() returns false
remove() throws NoSuchElementException; poll() returns null
element() throws NoSuchElementException; peek() returns null

Check your understanding: What does poll() return when a queue is empty?

null.

Step 3 of 13

4.3 Queue Example Using LinkedList

Learning objective

Trace FIFO insertion, front inspection, and removal using a LinkedList-backed Queue.

QueueDemo.java

import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> students = new LinkedList<>();
        students.offer("Amit");
        students.offer("Neha");
        students.offer("Raj");

        System.out.println("Queue: " + students);
        System.out.println("Front: " + students.peek());
        System.out.println("Removed: " + students.poll());
        System.out.println("Queue after removal: " + students);
    }
}

Output

Queue: [Amit, Neha, Raj]
Front: Amit
Removed: Amit
Queue after removal: [Neha, Raj]

Check your understanding: After Amit is removed, which students remain and in what order?

Neha followed by Raj.

Step 4 of 13

4.4 PriorityQueue

Learning objective

Explain heap-based priority processing, natural and custom ordering, and the difference between display and removal order.

PriorityQueue processes elements by priority rather than strictly by insertion order. Natural ordering gives the smallest element the highest priority by default.

PriorityQueue characteristics

Uses natural ordering or a Comparator
Allows duplicate values
Does not allow null
Is not synchronized
Iteration does not guarantee sorted order
Repeated poll() operations produce priority order

PriorityQueueDemo.java

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(40);
        queue.offer(10);
        queue.offer(30);
        queue.offer(20);

        System.out.println("Highest priority: " + queue.peek());
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

Removal order

Highest priority: 10
10
20
30
40

MaximumPriorityQueueDemo.java

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MaximumPriorityQueueDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        queue.offer(10);
        queue.offer(40);
        queue.offer(20);

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

Output

40
20
10

PriorityQueue complexity
Operation	Complexity
offer()	O(log n)
poll()	O(log n)
peek()	O(1)
contains()	O(n)

Check your understanding: How can the largest integer be processed first?

Construct PriorityQueue with Comparator.reverseOrder().

Step 5 of 13

4.5 Introduction to Deque

Learning objective

Define Deque and explain how one structure supports FIFO, LIFO, and both-end processing.

Deque is normally pronounced “deck.” Its two accessible ends let it act as a normal queue, a stack, or a general double-ended queue.

Deque interface relationship

public interface Deque<E> extends Queue<E>

Two-ended processing

Front <-> A, B, C <-> Rear. Elements can be inserted or removed at either end.

A Deque can work as

A FIFO queue
A LIFO stack
A double-ended queue

Check your understanding: Which interface does Deque extend?

Queue.

Step 6 of 13

4.6 Important Deque Methods

Learning objective

Match insertion, removal, and examination methods to the first or last end and to their failure behavior.

Deque insertion methods
First end	Last end
addFirst(element)	addLast(element)
offerFirst(element)	offerLast(element)

Deque removal methods
First end	Last end
removeFirst()	removeLast()
pollFirst()	pollLast()

Deque examination methods
First end	Last end
getFirst()	getLast()
peekFirst()	peekLast()

Check your understanding: Which method safely removes the last element and returns null when empty?

pollLast().

Step 7 of 13

4.7 ArrayDeque

Learning objective

Use ArrayDeque at both ends and explain why it is the modern default for queue and stack behavior.

ArrayDeque characteristics

Supports insertion and removal at both ends
Acts as a queue or a stack
Does not allow null
Allows duplicates
Is not synchronized
Is generally faster than Stack
Is normally preferred over LinkedList for pure queue or stack use

ArrayDequeDemo.java

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerFirst("C");

        System.out.println("Deque: " + deque);
        System.out.println("First: " + deque.peekFirst());
        System.out.println("Last: " + deque.peekLast());
        System.out.println("Removed first: " + deque.pollFirst());
        System.out.println("Removed last: " + deque.pollLast());
        System.out.println("Final deque: " + deque);
    }
}

Output

Deque: [C, A, B]
First: C
Last: B
Removed first: C
Removed last: B
Final deque: [A]

Check your understanding: Which element remains after removing C from the front and B from the rear?

A.

Step 8 of 13

4.8 Using Deque as a Queue

Learning objective

Implement FIFO behavior with insertion at the rear and removal from the front.

DequeAsQueueDemo.java

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsQueueDemo {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        queue.offerLast("Amit");
        queue.offerLast("Neha");
        queue.offerLast("Raj");
        System.out.println(queue.pollFirst());
    }
}

Output

Amit

Insertion occurs at the rear and removal occurs from the front, which preserves FIFO order.

Check your understanding: Which element is returned first after Amit, Neha, and Raj are added at the rear?

Amit.

Step 9 of 13

4.9 Using Deque as a Stack

Learning objective

Implement LIFO behavior with push(), pop(), and peek(), and map those methods to first-end operations.

DequeAsStackDemo.java

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStackDemo {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());
        System.out.println(stack.pop());
    }
}

Output

30
30

Stack methods and Deque equivalents
Stack operation	Deque equivalent
push(element)	addFirst(element)
pop()	removeFirst()
peek()	peekFirst()

Check your understanding: Which Deque method is equivalent to Stack pop()?

removeFirst(), exposed conveniently as pop().

Step 10 of 13

4.10 LinkedList as Queue and Deque

Learning objective

Use LinkedList through Deque and decide when ArrayDeque is the simpler choice.

LinkedList implements both List and Deque, so the same class can support positional list behavior or operations at either end.

LinkedListDequeDemo.java

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListDequeDemo {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.addFirst(10);
        deque.addLast(20);
        deque.addLast(30);
        System.out.println(deque.removeFirst());
        System.out.println(deque.removeLast());
    }
}

Output

10
30

Check your understanding: Which interfaces let LinkedList act as both a positional list and a double-ended queue?

List and Deque.

Step 11 of 13

4.11 Queue versus Deque

Learning objective

Compare one-ended queue behavior with double-ended deque behavior.

Queue and Deque comparison
Queue	Deque
Normally inserts at the rear	Inserts at both ends
Normally removes from the front	Removes from both ends
Primarily follows FIFO	Supports FIFO and LIFO
Uses offer(), poll(), and peek()	Uses first-end and last-end methods
Example: PriorityQueue	Example: ArrayDeque

Check your understanding: Can a Deque support both FIFO and LIFO?

Yes. Choosing opposite ends gives FIFO; choosing the same end gives LIFO.

Step 12 of 13

4.12 Queue Deque and Stack Comparison

Learning objective

Compare processing principles, end behavior, key methods, and recommended implementations.

Queue, Deque, and Stack comparison
Feature	Queue	Deque	Stack
Basic principle	FIFO	FIFO or LIFO	LIFO
Insertion	Normally at rear	At both ends	At top
Removal	Normally from front	From both ends	From top
Main methods	offer(), poll(), peek()	offerFirst(), offerLast(), pollFirst(), pollLast()	push(), pop(), peek()
Recommended implementation	ArrayDeque or LinkedList	ArrayDeque	ArrayDeque
Special priority support	PriorityQueue	No	No

Check your understanding: Which structure provides special priority processing?

Queue through PriorityQueue.

Step 13 of 13

4.13 Selection guide

Learning objective

Select Set, Queue, PriorityQueue, Deque, or stack behavior from a practical requirement.

Requirement and recommended structure
Requirement	Recommended choice
Fast unique-element storage	HashSet
Uniqueness plus insertion order	LinkedHashSet
Unique sorted elements	TreeSet
FIFO processing	Queue with ArrayDeque or LinkedList
Priority-based processing	PriorityQueue
Insertion and removal at both ends	ArrayDeque
Modern stack behavior	ArrayDeque through Deque

Final decision checklist

Do duplicates matter?
Must insertion or sorted order be preserved?
Is processing FIFO, LIFO, both-ended, or priority-based?
Is indexed access required?
Does the application need range navigation?

Check your understanding: Which implementation should new code normally use for stack behavior?

ArrayDeque.