For most people, the word "queue" brings to mind very few pleasant associations. But today we're talking about different queues — Java queues. In Java, a queue is anything that inherits the Queue interface, which in turn extends the Collection interface. That means that queues can be treated like collections.
Queues in Java support two operating principles: FIFO and LIFO.
The FIFO (First In, First Out) principle governs a regular queue — the first element added to the queue is the first to leave it.
The LIFO (Last In, First Out) principle describes the behavior of a stack — the last element added to the queue is the first to leave it. For example, this is how you work with a deck of cards: you take cards off of the top one at a time until you reach the bottom of the deck.
The Queue hierarchy in Java looks like this:
Here you can see that Queue has 3 implementation classes: LinkedList, ArrayDeque and PriorityQueue. LinkedList and ArrayDeque directly inherit not Queue, but Deque.
Deque is an interface that was added in Java 6. It includes several methods that are useful for queues and allows a queue to function as a double-ended (or bidirectional) queue. That means it can be FIFO and LIFO.
One of the Deque interface's two descendants is ArrayDeque. It supports a doubled-ended queue that lets you insert and remove elements from both ends. It is also a dynamic array that automatically grows in size.
There is also a PriorityQueue class, which is a direct descendant of Queue: it behaves differently than the classes that implement Deque.
PriorityQueue is a priority queue that organizes elements according to their natural ordering by default. Here the sorting uses the Comparable and Comparator interfaces. The principle is the same as with TreeSet or TreeMap — classes that use the Comparable interface and have their own sort order.
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));
priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
If you run this example, here's what you'll see in the console:
John
Andrew
Since we are working with queues and not regular collections, we need to remove the elements from the list. To do this, we use this construct:
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
The Deque interface inherits the Queue methods and adds several of its own interesting methods:
void addFirst(E obj) | Adds the obj element to the front of the queue |
void addLast(E obj) | Adds the obj element to the end of the queue |
E getFirst() | Returns the first element from the queue |
E getLast() | Returns the last element from the queue |
boolean offerFirst(E obj) | Adds the obj element to the front of the queue, and returns true if the element is added. Otherwise, returns false. |
boolean offerLast(E obj) | Adds the obj element to the end of the queue, and returns true if the element is added. Otherwise, returns false. |
E pop() | Gets the first element from the queue and removes it |
void push(E obj) | Adds the obj element to the front of the queue |
E peekFirst() | Returns (but does not remove) the first element from the queue |
E peekLast() | Returns (but does not remove) the last element from the queue |
E pollFirst() | Returns and removes the first element from the queue. Returns null if there are no elements. |
E pollLast() | Returns and removes the last element from the queue. Returns null if there are no elements. |
E removeLast() | Returns and removes the first element of the queue. Throws an exception if there are no elements. |
E removeFirst() | Returns and removes the last element of the queue. Throws an exception if there are no elements. |
boolean removeFirstOccurrence(Object obj) | Removes the first occurrence of obj from the queue |
boolean removeLastOccurrence(Object obj) | Removes the last occurrence of obj from the queue |
Let's now look at a few of these methods in practice.
First, let's add an element to a queue:
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple"); // Adds "Apple" to the end of the queue
deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
System.out.println(deque);
Now let's get values from a queue:
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
System.out.println("The first element is: "+ deque.getFirst());
System.out.println("The last element is: " + deque.getLast());
}
This code displays the first and last element of the queue.
The last element is: Pineapple
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
deque.add("Lemon");
System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue
System.out.println(deque);
Running this code, we get:
Apple
[Pineapple, Lemon]
The difference between pop() and poll() is that pop() will throw a NoSuchElementException if the list is empty list, but poll() will return null.
Now we'll consider the pollFirst() and pollLast() methods.
Deque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.addFirst("Orange");
deque.addLast("Pineapple");
deque.add("Lemon");
System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);
Lemon
[Apple, PineApple]
Both methods return and remove a value from the queue.
Here's an example of using the peekFirst() and peekLast() methods:
Deque<String> friends = new ArrayDeque<>();
friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");
System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());
System.out.println(friends);
The last element is: Oliver
[John, Rob, Greg, Max, Oliver]
Both methods return the first/last element from the queue and do not remove them. If the queue is empty, null will be returned.
Well done! Today we learned how to work with queues in Java. Now you know how to use them in practice.
GO TO FULL VERSION