Java Queue
Jakob Jenkov |
The Java Queue interface, java.util.Queue represents a data structure designed to have
elements inserted at the end of the queue, and elements removed from the beginning of the queue. This is similar
to how a queue in a supermarket works.
The Java Queue interface is a subtype of the Java Collection interface.
It represents an ordered sequence of objects just like a Java List, but its intended use is
slightly different.
Because the Java Queue interface is a subtype of the Java Collection interface,
all methods in the Collection interface are also available in the Queue interface.
Java Queue Tutorial Video
If you prefer video, I have a Java Queue tutorial video too:
Java Queue Implementations
Since Queue is an interface you need to instantiate a concrete implementation
of the interface in order to use it. You can choose between the following Queue
implementations in the Java Collections API:
- java.util.LinkedList
- java.util.PriorityQueue
LinkedList is a pretty standard queue implementation. Elements in the queue are stored
internally in a standard linked list data structure. This makes it fast to insert elements at the end (tail)
of the list, and remove elements from the beginning (head) of the list.
PriorityQueue stores its elements internally according to their natural order
(if they implement Comparable), or according to a Comparator passed
to the PriorityQueue.
There are also Queue implementations in the java.util.concurrent package,
but I will leave the concurrency utilities out of this tutorial.
Here are a few examples of how to create a Queue instance:
Queue queueA = new LinkedList(); Queue queueB = new PriorityQueue();
In most Queue implementations
the head and tail of the queue are at opposite ends. It is possible, however, to implement the
Queue interface so that the head and tail of the queue is in the same end.
In that case you would have a stack.
Generic Queue
By default you can put any Object into a Queue, but from Java 5, Java Generics
makes it possible to limit the types of object you can insert into a Queue. Here is an example:
Queue<MyObject> queue = new LinkedList<MyObject>();
This Queue can now only have MyObject instances inserted into it.
You can then access and iterate its elements without casting them. Here is how it looks:
Queue<MyObject> queue = new LinkedList<MyObject>();
MyObject myObject = queue.remove();
for(MyObject anObject : queue){
//do someting to anObject...
}
Notice how no cast is needed on the first line, and how the for-each loop can cast each element of the Queue
directly to a MyObject instance. This is possible because the Queue was created with MyObject
as generic type.
It is considered good practice to always specify a generic type for a Queue if you know it. That helps the Java compiler check the types, it helps you write more compact code, and it helps the next reader of your code understand what types of objects this Queue contains. For more information about Java Generics, see the Java Generics Tutorial.
Add Element to Queue
The Java Queue interface contains two methods you can use to add elements to a Queue. These methods are the
add() method and the offer() method. These two methods add an element to the end
of the Queue. The add() and offer() methods differ in how the behave if the Queue
is full, so no more elements can be added. The add() method throws an exception in that case,
whereas the offer() method just returns false. Here are two examples of adding elements
to a Java Queue via its add() and offer() methods:
Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.offer("element 2");
Take Element From Queue
To take an element from a Java Queue you can call either its poll() or remove() method.
The poll() and poll() method returns null if the Queue is empty.
The remove() method throws an exception if the Queue is empty. Here are two examples of taking
an element from a Java Queue using its poll() and remove() methods:
Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
String element1 = queue.poll();
String element2 = queue.remove();
The call to poll() will remove the first element of the Queue - which is the first
Java String instance added - "element 1".
The call to rmove() will remove the second element of the Queue - which after the
first poll() call is now the String instance added - "element 2".
Peek at the Queue
You can peek at the element at the head of a Queue without taking the element out of
the Queue. This is done via the Queue element() or peek() methods.
The element() method returns the first element in the Queue. If the Queue
is empty, the element() method throws a NoSuchElementException.
Here is an example of peeking at the first element of a Java Queue using the element()
method:
Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");
String firstElement = queue.element();
After running this Java code the firstElement variable will contain the value element 1
which is the first element in the Queue.
The peek() works like the element() method except it does not throw an exception if
the Queue is empty. Instead it just returns null. Here is an example of peeking at
the first element of a Queue using the peek() method:
Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");
String firstElement = queue.peek();
Remove Element From Queue
To remove elements from a Java Queue, you call the remove() method. This method
removes the element at the head of the Queue.
Here is an example of removing an element from a Java Queue:
Queue<String> queue = new LinkedList<>();
queue.add("element 0");
queue.add("element 1");
String removedElement = queue.remove();
Remove All Elements From Queue
You can remove all elements from a Java Queue using its clear() method. The clear()
method is actually inherited from the Collection interface. Here is an example
of removing all elements from a Java Queue via its clear() method:
queue.clear();
Get Queue Size
You can read the number of elements stored in a Java Queue via its size() method. Here is an example
of obtaining the size of a Java Queue via its size() method:
Queue<String> queue = new LinkedList<>();
queue.add("element 1");
queue.add("element 2");
queue.add("element 3");
int size = queue.size();
After running this code the size variable should contain the value 3 - because the Queue contains
3 elements at the time size() is called.
Check if Queue Contains Element
You can check if a Java Queue contains a certain element via its contains() method. The
contains() method will return true if the Queue contains the given element, and
false if not. The
contains() method is actually inherited from the Collection
interface, but in practice that doesn't matter. Here are two examples of checking if a Java Queue contains
a given element:
Queue<String> queue = new LinkedList<>();
queue.add("Mazda");
boolean containsMazda = queue.contains("Mazda");
boolean containsHonda = queue.contains("Honda");
After running this code the containsMazda variable will have the value true
whereas the containsHonda variable will have the value false - because the Queue
contains the "Mazda" string element, but not the "Honda" string element.
Iterate All Elements in Queue
You can also iterate all elements of a Java Queue, instead of just processing one at a time.
Here is an example of iterating all elements in a Java Queue:
Queue<String> queue = new LinkedList<>();
queue.add("element 0");
queue.add("element 1");
queue.add("element 2");
//access via Iterator
Iterator<String> iterator = queue.iterator();
while(iterator.hasNext(){
String element = iterator.next();
}
//access via new for-loop
for(String element : queue) {
//do something with each element
}
When iterating a Queue via its Iterator or via the for-each loop (which also uses the Iterator
behind the scene), the sequence in which the elements are iterated depends on the queue implementation.
More Details in the JavaDoc
There is a lot more you can do with a Queue, but you will have to check out the JavaDoc
for more details. This text focused on the two most common operations: Adding / removing elements,
and iterating the elements.
| Tweet | |
Jakob Jenkov | |
