The Queue
core interface in the collection framework, is a collection that stores elements that can be accessed at some later point to process (like waiting in line at the bank teller). A Queue
accesses elements in a (usually) First In First Out (FIFO) manner where elements are inserted at the tail (back) of the collection and removed from the head (front).
A Queue
has two types of access methods for inserting, removing, and getting but not removing the head of the Queue
.
The following methods throw an exception when:
add()
- there is no space for the elementremove()
- there are no elements to removeelement()
- there are no elements to get
The following methods return
a special value:
offer()
-false
there is no space for the elementpoll()
-null
there are no elements to removepeek()
-null
there are no elements to get
The methods that return a special value should be used when working with a statically sized Queue
and the exception throwing methods when using a dynamic Queue
.
Like the other collection framework interfaces, Queue
has many implementations. We’ll focus on LinkedList
and PriorityQueue
. We’ve seen LinkedList
be used as a List
implementation and it’s also perfect when needing a basic Queue
implementation. Being able to use a LinkedList
as both a List
and Queue
implementation is a perfect example of the compatibility within the collection framework. The PriorityQueue
ensures the top element is the smallest relative to the data type’s natural ordering (or some custom comparison algorithm you provide).
Let’s look at an example of Queue
with a LinkedList
implementation:
Queue<String> stringQueue = new LinkedList<>(); stringQueue.add("Mike"); // true - state of queue -> "Mike" stringQueue.offer("Jeff"); // true - state of queue -> "Mike", "Jeff" String a = stringQueue.remove() // Returns "Mike" - state of queue -> 1 String b = stringQueue.poll() // Returns "Jeff" - state of queue -> empty String c = stringQueue.peek() // Returns null String d = stringQueue.element() // Throws NoSuchElementException
In the example above we:
- Created a new
String Queue
reference with aLinkedList
implementation. - Called
add()
andoffer()
to insert elements into theQueue
. Note the state of theQueue
after each call. - Called
remove()
andpoll()
to remove and retrieve the element at the front of theQueue
. - Called
peek()
andelement()
to retrieve but not remove the element at the front of theQueue
. Note the results whenstringQueue
is empty.
We can iterate through a Queue
using the enhanced for-loop
. For example:
// Assuming `stringQueue` has elements -> "Mike", "Jack", "John" for (String name: stringQueue) { System.out.println(name); } // OUTPUT TERMINAL: "Mike", "Jack", "John"
One thing to note about a PriorityQueue
is that an enhanced for-loop
(or Iterator
) makes no guarantee in the ordering of elements after the head.
Let’s practice creating a Queue
and iterating through it.
Instructions
In main()
of Main.java we’ve made a Queue
named line
with names (String
s) and printed out the contents of the Queue
. We’d like to be able to process line
in alphabetical order rather than FIFO.
Let’s start by defining a new public static
method named processAlphabetically
with a String Queue
parameter named queue
. This method returns no value.
Recall that a PriorityQueue
will have the smallest element at the head of the collection. The smallest element in a collection of String
s will be in lexicographic (alphabetical) order.
In processAlphabetically()
create a String Queue
reference with a PriorityQueue
implementation named alphabeticalQueue
.
Next, let’s add all the elements in queue
into alphabeticalQueue
by using an enhanced for-loop
. The for-loop
should iterate through queue
using a String
reference called name
. Add name
to alphabeticalQueue
during each iteration of the loop.
Let’s process the names in alphabeticalQueue
alphabetically.
Under the for-loop
in processAlphabetically()
define a while
loop that will iterate until peek()
of alphabeticalQueue
returns null
. In the body of the while
loop create a String
reference named headElement
and store the result of removing the head from alphabeticalQueue
. Finally, use System.out.println()
to print the following message:
Processing: <element>