Think about the line at a railway ticket counter. The person who comes first is served first, and new people join at the back. Now think about a stack of plates: you always take the plate from the top, which is the one that was placed last. And in a hospital emergency room, patients are not served in arrival order at all; the most serious case goes first.
These three situations describe three very important ways of organizing data, and Java has a collection for each:
Queue → First In, First Out (FIFO) ticket counter
Stack (Deque) → Last In, First Out (LIFO) stack of plates
PriorityQueue → highest priority comes out first emergency roomIn the Collections chapter, we met List, Set, and Map. In this chapter, we will learn the Queue and Deque interfaces and the classes ArrayDeque and PriorityQueue. These are used constantly in real programs and in coding interviews (for example, BFS uses a queue and "top K" problems use a priority queue).
The Queue Interface
A Queue holds elements waiting to be processed. In a normal queue, elements are added at the back (tail) and removed from the front (head): First In, First Out.
remove here add here
↓ ↓
[ Asha | Bilal | Chetan ] ← Divya
head tailQueue is an interface in java.util. Two common classes implement it: LinkedList (which you already know) and ArrayDeque. Here is a queue at a ticket counter:
import java.util.LinkedList;
import java.util.Queue;
class Main {
public static void main(String[] args) {
Queue<String> ticketQueue = new LinkedList<>();
ticketQueue.offer("Asha"); // joins at the back
ticketQueue.offer("Bilal");
ticketQueue.offer("Chetan");
System.out.println("Queue: " + ticketQueue);
System.out.println("Next in line: " + ticketQueue.peek()); // look, don't remove
String served = ticketQueue.poll(); // remove from the front
System.out.println("Served: " + served);
System.out.println("Queue: " + ticketQueue);
ticketQueue.offer("Divya");
System.out.println("Queue: " + ticketQueue);
System.out.println("Size: " + ticketQueue.size());
}
}Output:
Queue: [Asha, Bilal, Chetan]
Next in line: Asha
Served: Asha
Queue: [Bilal, Chetan]
Queue: [Bilal, Chetan, Divya]
Size: 3The three main operations are:
offer(e): adds an element at the back.peek(): returns the front element without removing it.poll(): removes and returns the front element.
Two Versions of Each Operation
The Queue interface actually has two methods for each operation. They differ only in what happens when the operation fails, for example when the queue is empty:
Operation | Throws an exception | Returns a special value |
|---|---|---|
Add at the back |
|
|
Remove from the front |
|
|
Look at the front |
|
|
import java.util.ArrayDeque;
import java.util.Queue;
class Main {
public static void main(String[] args) {
Queue<Integer> queue = new ArrayDeque<>(); // empty queue
System.out.println(queue.peek()); // null
System.out.println(queue.poll()); // null
try {
queue.element();
} catch (Exception e) {
System.out.println("element() threw " + e.getClass().getSimpleName());
}
try {
queue.remove();
} catch (Exception e) {
System.out.println("remove() threw " + e.getClass().getSimpleName());
}
}
}Output:
null
null
element() threw NoSuchElementException
remove() threw NoSuchElementExceptionMost programmers use offer(), poll(), and peek(), and check for null or use isEmpty(). For the collections in this chapter, add() and offer() behave the same, because they never run out of space.
Deque: A Double-Ended Queue
A Deque (pronounced "deck") is a double-ended queue: you can add and remove elements at both the front and the back.
Deque extends Queue. The most popular implementation is ArrayDeque, which stores elements in a resizable circular array.
import java.util.ArrayDeque;
import java.util.Deque;
class Main {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(20); // [20]
deque.offerLast(30); // [20, 30]
deque.offerFirst(10); // [10, 20, 30]
deque.offerFirst(5); // [5, 10, 20, 30]
System.out.println(deque);
System.out.println("First: " + deque.peekFirst());
System.out.println("Last: " + deque.peekLast());
deque.pollFirst(); // removes 5
deque.pollLast(); // removes 30
System.out.println(deque);
}
}Output:
[5, 10, 20, 30]
First: 5
Last: 30
[10, 20]The method names follow a simple pattern: offer/poll/peek + First/Last. There are also throwing versions such as addFirst(), removeLast(), and getFirst(), just like in the table above.
Using a Deque as a Stack
A stack is Last In, First Out (LIFO): the last element added is the first one removed. Think of the browser's back button: the last page you visited is the first one you go back to.
Deque has the classic stack methods built in:
push(e): adds to the top (the front of the deque).pop(): removes and returns the top. ThrowsNoSuchElementExceptionif empty.peek(): returns the top without removing it, ornullif empty.
import java.util.ArrayDeque;
import java.util.Deque;
class Main {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("Page 1"); // push adds to the top (front)
stack.push("Page 2");
stack.push("Page 3");
System.out.println("Stack: " + stack);
System.out.println("Top: " + stack.peek());
System.out.println("Back to: " + stack.pop());
System.out.println("Back to: " + stack.pop());
System.out.println("Stack: " + stack);
}
}Output:
Stack: [Page 3, Page 2, Page 1]
Top: Page 3
Back to: Page 3
Back to: Page 2
Stack: [Page 1]Notice that the stack prints as [Page 3, Page 2, Page 1]: the top of the stack is at the front.
Java also has an older Stack class. It still works, but it is a legacy class (it extends Vector, and its operations are synchronized, which adds overhead even in single-threaded code). The Java documentation itself recommends using Deque and ArrayDeque for stacks instead.
Interview Classic: Balanced Brackets
Checking whether brackets are balanced is one of the most common stack problems. Push every opening bracket; when you see a closing bracket, pop and check that it matches:
import java.util.ArrayDeque;
import java.util.Deque;
class Main {
static boolean isBalanced(String text) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : text.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch); // remember the opening bracket
} else if (ch == ')' || ch == ']' || ch == '}') {
if (stack.isEmpty()) {
return false; // closing bracket with no opener
}
char open = stack.pop();
if ((ch == ')' && open != '(') ||
(ch == ']' && open != '[') ||
(ch == '}' && open != '{')) {
return false; // wrong type of bracket
}
}
}
return stack.isEmpty(); // every opener must be closed
}
public static void main(String[] args) {
System.out.println(isBalanced("{[a + b] * (c - d)}"));
System.out.println(isBalanced("([)]"));
System.out.println(isBalanced("((x)"));
}
}Output:
true
false
falseIn "([)]", the ) arrives when the top of the stack is [, so it fails. In "((x)", one ( is left on the stack at the end. This runs in O(n) time and uses O(n) extra space in the worst case.
PriorityQueue
A PriorityQueue always removes the element with the highest priority first. By default, the smallest element has the highest priority.
So elements come out in sorted order, no matter what order they went in:
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(50);
pq.offer(20);
pq.offer(40);
pq.offer(10);
pq.offer(30);
System.out.println("Printed: " + pq); // NOT sorted order!
System.out.println("Smallest: " + pq.peek());
System.out.print("Polling:");
while (!pq.isEmpty()) {
System.out.print(" " + pq.poll());
}
System.out.println();
}
}Output:
Printed: [10, 20, 40, 50, 30]
Smallest: 10
Polling: 10 20 30 40 50Look carefully at the first line. Printing the PriorityQueue gives [10, 20, 40, 50, 30], which is not sorted. That is because a PriorityQueue is internally a binary min-heap: a tree stored in an array, where every parent is smaller than or equal to its children. Only the top (the root) is guaranteed to be the smallest:
10 array: [10, 20, 40, 50, 30]
/ \
20 40 every parent ≤ its children
/ \
50 30Each poll() removes the root and then rearranges the heap so the next smallest element moves to the top. That is why polling gives the correct sorted order, while printing or looping with for-each does not.
Max-Heap and Other Orders
To get the largest element first, pass Collections.reverseOrder() to the constructor. Strings use alphabetical order by default:
import java.util.Collections;
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(40);
maxHeap.offer(10);
maxHeap.offer(30);
maxHeap.offer(20);
System.out.println("Largest: " + maxHeap.peek());
System.out.println(maxHeap.poll() + " " + maxHeap.poll() + " " + maxHeap.poll() + " " + maxHeap.poll());
PriorityQueue<String> names = new PriorityQueue<>();
names.offer("Meera");
names.offer("Arjun");
names.offer("Zoya");
names.offer("Kabir");
System.out.println(names.poll() + " " + names.poll() + " " + names.poll() + " " + names.poll());
}
}Output:
Largest: 40
40 30 20 10
Arjun Kabir Meera ZoyaPriorityQueue works with any type that has a natural order, such as numbers and Strings. To store your own objects, like a Patient sorted by severity, Java must know how to compare them. You will learn how to do that in the Comparable & Comparator chapter, and the same PriorityQueue will work for your own classes too.
Interview Classic: K-th Largest Element
A very common question: find the k-th largest number in an array. Sorting takes O(n log n). With a min-heap of size k, we can do it in O(n log k):
import java.util.PriorityQueue;
class Main {
// Returns the k-th largest number using a min-heap of size k
static int kthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // remove the smallest, keep the k largest
}
}
return minHeap.peek(); // smallest of the k largest = k-th largest
}
public static void main(String[] args) {
int[] scores = {72, 95, 61, 88, 99, 45, 80};
System.out.println("1st highest: " + kthLargest(scores, 1));
System.out.println("2nd highest: " + kthLargest(scores, 2));
System.out.println("3rd highest: " + kthLargest(scores, 3));
}
}Output:
1st highest: 99
2nd highest: 95
3rd highest: 88The heap always keeps the k largest numbers seen so far. Whenever it grows beyond k, we remove the smallest. At the end, the smallest number in the heap (its top) is the k-th largest overall. For k = 3, the heap ends up holding 88, 95, and 99, and its top is 88.
Time Complexity
Operation | ArrayDeque | PriorityQueue |
|---|---|---|
Add ( | O(1) on average | O(log n) |
Remove from front ( | O(1) | O(log n) |
Look at front ( | O(1) | O(1) |
| O(n) | O(n) |
Which One Should You Use?
You need | Use |
|---|---|
A FIFO queue |
|
A stack |
|
Add/remove at both ends |
|
Always get the smallest (or largest) next |
|
ArrayDeque is usually faster than LinkedList for queues and stacks, because it uses an array instead of separate node objects.
Common Mistakes
Expecting a PriorityQueue to print in sorted order. Only
poll()gives sorted order. Printing and for-each loops show the internal heap order.Adding null to an ArrayDeque or PriorityQueue. Both throw
NullPointerException, becausepoll()andpeek()usenullto mean "empty".Calling remove(), element(), or pop() on an empty collection. These throw
NoSuchElementException. Usepoll()/peek()or checkisEmpty()first.Using the legacy Stack class in new code. Prefer
ArrayDeque.Forgetting that push() adds to the front. If you mix
push()withoffer()(which adds to the back) on the same deque, the order gets confusing. Use one style per deque.
Practice Problems
Reverse a string using a stack.
Simulate a printer queue: add 5 print jobs and process them in order.
Find the 3 smallest numbers in an array using a max-heap of size 3.
Check whether a word is a palindrome using a
Deque(comparepollFirst()withpollLast()).
The Main Idea
Choose the collection by the order in which elements must come out.
Queue → first in, first out. Stack (Deque with push/pop) → last in, first out. PriorityQueue → smallest (or highest-priority) first.
For queues and stacks, ArrayDeque is the go-to class. For "always give me the best next item", use PriorityQueue.