Java Notes

Queue in Java

Complete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.

What is a Queue?

A Queue is a FIFO (First In, First Out) data structure — like a line at a store. The first person who joins the line is the first person to be served. In programming, the first element added to the queue is the first one to be removed.

This behavior contrasts with a Stack (LIFO — Last In, First Out) where the most recent element is removed first. Understanding when to use a Queue vs a Stack is a fundamental skill for solving algorithmic problems.

enqueue(4): [1, 2, 3]	[1, 2, 3, 4] (add to rear)
dequeue(): [1, 2, 3, 4]	[2, 3, 4] (remove from front, returns 1)
peek(): [2, 3, 4]	returns 2 (view front without removing)
isEmpty()	returns false
size()	returns 3
All basic operations	O(1) time complexity

Array-based Circular Queue Implementation

Understanding how to implement a queue from scratch is essential for interviews:

Example

public class CircularQueue<T> { private Object[] data; private int front, rear, size, capacity; public CircularQueue(int capacity) { this.capacity = capacity; this.data = new Object[capacity]; this.front = 0; this.rear = -1; this.size = 0; } public void enqueue(T item) { if (size == capacity) throw new IllegalStateException("Queue full"); rear = (rear + 1) % capacity; // Wrap around using modulo data[rear] = item; size++; } @SuppressWarnings("unchecked") public T dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue empty"); T item = (T) data[front]; data[front] = null; // Help garbage collection front = (front + 1) % capacity; // Wrap around size--; return item; } @SuppressWarnings("unchecked") public T peek() { if (isEmpty()) throw new NoSuchElementException(); return (T) data[front]; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == capacity; } public int size() { return size; } }

Why circular? Without the circular (modulo) logic, a linear array queue wastes space. As elements are dequeued, the front index advances leaving unused space behind it. The circular approach reuses that space by wrapping the rear pointer back to the beginning when it reaches the end of the array.

Priority Queue (Min-Heap)

A Priority Queue processes elements by priority rather than FIFO order. Java's PriorityQueue implements a min-heap by default:

Example

// Min-heap (smallest element has highest priority) PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1); System.out.println(minHeap.poll()); // 1 (smallest) System.out.println(minHeap.poll()); // 2 // Max-heap (largest element has highest priority) PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8); maxHeap.offer(1); System.out.println(maxHeap.poll()); // 8 (largest) // Custom priority — sort tasks by deadline PriorityQueue<int[]> taskQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]); taskQueue.offer(new int[]{1, 5}); // task 1, deadline 5 taskQueue.offer(new int[]{2, 2}); // task 2, deadline 2 taskQueue.offer(new int[]{3, 8}); // task 3, deadline 8 // poll() returns task 2 first (earliest deadline) // Classic problem: Find K largest elements efficiently public static int[] kLargest(int[] arr, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : arr) { minHeap.offer(num); if (minHeap.size() > k) minHeap.poll(); // Remove smallest } // Heap now contains k largest elements return minHeap.stream().mapToInt(Integer::intValue).toArray(); }

Time complexity: offer() and poll() are O(log n). peek() is O(1).

Deque (Double-Ended Queue)

A Deque allows insertion and removal from BOTH ends:

Example

Deque<Integer> deque = new ArrayDeque<>(); // Add to front or back deque.offerFirst(1); // [1] deque.offerLast(2); // [1, 2] deque.offerFirst(0); // [0, 1, 2] // Remove from front or back deque.pollFirst(); // returns 0, deque = [1, 2] deque.pollLast(); // returns 2, deque = [1] // Can be used as both Stack and Queue // As Queue: offerLast() + pollFirst() // As Stack: offerFirst() + pollFirst() (or offerLast() + pollLast())

BFS (Breadth-First Search) Using Queue

BFS is the most important algorithmic application of queues — it explores nodes level by level:

Example

// Level-order traversal of a binary tree public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // Nodes at current level List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; } // BFS on a graph (shortest path in unweighted graph) public int shortestPath(Map<Integer, List<Integer>> graph, int start, int end) { Queue<Integer> queue = new LinkedList<>(); Set<Integer> visited = new HashSet<>(); queue.offer(start); visited.add(start); int distance = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int node = queue.poll(); if (node == end) return distance; for (int neighbor : graph.getOrDefault(node, List.of())) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } distance++; } return -1; // Not reachable }

Queue Implementations Comparison

Implementation	Use Case	Thread-Safe?	Null Elements?
ArrayDeque	General purpose (fastest)	No	No
LinkedList	Need null elements or List interface	No	Yes
PriorityQueue	Priority-based processing	No	No
ConcurrentLinkedQueue	Multi-threaded producers/consumers	Yes	No
LinkedBlockingQueue	Producer-consumer with blocking	Yes	No
ArrayBlockingQueue	Bounded blocking queue	Yes	No

Interview Questions

Q1: How do you implement a queue using two stacks?

Answer: Stack1 for enqueue (push directly). Stack2 for dequeue: if Stack2 is empty, transfer ALL elements from Stack1 to Stack2 (this reverses the order), then pop from Stack2. Amortized O(1) per operation because each element is moved at most twice across its lifetime.

Q2: What is the difference between Queue, Deque, and PriorityQueue?

Answer: Queue enforces FIFO order. Deque allows insertion and removal at both ends (can act as both queue and stack). PriorityQueue orders elements by natural ordering or a comparator — it is NOT FIFO, elements come out in priority order regardless of insertion time.

Q3: What is a circular queue and why use it?

Answer: A circular queue uses modulo arithmetic to wrap pointers around the array, reusing space freed by dequeue operations. Without circularity, a linear array wastes all space before the front pointer. Circular queues provide O(1) operations with fixed memory.

Q4: How do you implement a sliding window maximum using a deque?

Answer: Maintain a monotonic decreasing deque storing indices. For each new element: remove indices outside the window from front, remove smaller elements from back (they can never be the maximum), add current index to back. The front of deque always holds the current window's maximum.

Q5: Where are queues used in real systems?

Answer: Task scheduling (CPU round-robin), print spooler (FIFO print jobs), BFS traversal (graph algorithms), message queues (Kafka, RabbitMQ), HTTP request handling (web server request queue), I/O buffering (disk and network buffers), thread pools (work queue for worker threads).

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Queue in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, dsa, queue, queue in java

Continue learning this concept

DSA in JavaDynamic Programming in JavaComplete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.DSA in JavaGraph Data Structure in JavaComplete guide to graphs — representation, BFS, DFS, shortest path algorithms, topological sort, and classic graph problems in Java.DSA in JavaHashing in JavaComplete guide to hashing — hash functions, collision resolution, HashMap internals, custom hashCode/equals, and applications of hashing in problem-solving.DSA in JavaHeap (DSA)Complete guide to Heap data structure in Java covering Min Heap, Max Heap, heap operations, heapify algorithm, PriorityQueue class, heap sort, and applications with detailed implementations.DSA in JavaLinked List in JavaComplete guide to Linked Lists — Singly, Doubly, and Circular linked lists with Java implementations, operations, and classic interview problems.DSA in JavaRecursion in JavaMaster recursion — base cases, recursive thinking, call stack visualization, tail recursion, memoization, backtracking, and converting recursion to iteration.

PreviousLinked List in Java NextRecursion in Java

Java Notes

Queue in Java

Complete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.

What is a Queue?

enqueue(4): [1, 2, 3]	[1, 2, 3, 4] (add to rear)
dequeue(): [1, 2, 3, 4]	[2, 3, 4] (remove from front, returns 1)
peek(): [2, 3, 4]	returns 2 (view front without removing)
isEmpty()	returns false
size()	returns 3
All basic operations	O(1) time complexity

Array-based Circular Queue Implementation

Understanding how to implement a queue from scratch is essential for interviews:

Example

Priority Queue (Min-Heap)

A Priority Queue processes elements by priority rather than FIFO order. Java's PriorityQueue implements a min-heap by default:

Example

Time complexity: offer() and poll() are O(log n). peek() is O(1).

Deque (Double-Ended Queue)

A Deque allows insertion and removal from BOTH ends:

Example

BFS (Breadth-First Search) Using Queue

BFS is the most important algorithmic application of queues — it explores nodes level by level:

Example

Queue Implementations Comparison

Implementation	Use Case	Thread-Safe?	Null Elements?
ArrayDeque	General purpose (fastest)	No	No
LinkedList	Need null elements or List interface	No	Yes
PriorityQueue	Priority-based processing	No	No
ConcurrentLinkedQueue	Multi-threaded producers/consumers	Yes	No
LinkedBlockingQueue	Producer-consumer with blocking	Yes	No
ArrayBlockingQueue	Bounded blocking queue	Yes	No

Interview Questions

Q1: How do you implement a queue using two stacks?

Q2: What is the difference between Queue, Deque, and PriorityQueue?

Q3: What is a circular queue and why use it?

Q4: How do you implement a sliding window maximum using a deque?

Q5: Where are queues used in real systems?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Queue in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, dsa, queue, queue in java

Continue learning this concept

PreviousLinked List in Java NextRecursion in Java