Queue, Priority Queue and Stack
Table of contents
Queue
A Queue is an abstract data structure that elements can be added and removed one at a time. The order in which the elements are retrieved is defined by the queue implementation.
There are three main queue implementations
- The FIFO queue is the most common implementation of a queue, where elements are retrieved in a first in first out manner.
- The Priority queue orders the elements based on their priority. Elements with the highest priority are returned first.
- The LIFO queue, also known as stack, returns the element that was added last first, hence LIFO queue.
There are other queue implementations, such as BlockingQueue where the caller may block until more elements are added to the queue. These implementations do not define the order in which elements are retrieved and are suited for more specific applications, such as concurrency.
FIFO Queue
A FIFO queue is a data structure that supports the first in first out (FIFO) ordering, as shown in the following diagram.
Elements are added at the back of the queue and are retrieved from the front of the queue, in the order these were added. A line of people waiting to use the ATM is an example of a queue, as shown next.
The person at the front of the queue will use the ATM next, while new persons will join the queue at the back.
Queue is an interface in Java, which has several implementations. Two common implementations are ArrayDeque and LinkedList. LinkedList was covered before, when we covered lists. We will cover ArrayDeque in this example.
Consider the following example.
package demo;
import java.util.ArrayDeque;
import java.util.Queue;
public class App {
public static void main( final String[] args ) {
final Queue<String> waitingInLine = new ArrayDeque<>();
waitingInLine.add( "Jade" );
waitingInLine.add( "Aden" );
while ( false == waitingInLine.isEmpty() ) {
String next = waitingInLine.poll();
System.out.printf( "Serving %s (people remaining in the queue %d)%n", next, waitingInLine.size() );
}
System.out.println( "No one else is waiting in the queue" );
}
}
The elements within the queue are retrieved in the order these where added.
Serving Jade (people remaining in the queue 1)
Serving Aden (people remaining in the queue 0)
No one else is waiting in the queue
Priority Queue
The Java collections framework also provides a PriorityQueue, where the elements are ordered based on their priority and not based on the order these are added. Consider the following example.
package demo;
import lombok.Data;
import org.apache.commons.lang3.StringUtils;
import java.util.PriorityQueue;
import java.util.Queue;
public class App {
@Data
private static class Student implements Comparable<Student> {
private final String name;
private final int mark;
@Override
public int compareTo( final Student that ) {
return StringUtils.compare( name, that.name );
}
}
public static void main( final String[] args ) {
final Queue<Student> students = new PriorityQueue<>();
students.add( new Student( "Jade", 85 ) );
students.add( new Student( "Aden", 82 ) );
while ( false == students.isEmpty() ) {
Student next = students.poll();
System.out.printf( "Processing %s (students remaining in the queue %d)%n", next, students.size() );
}
System.out.println( "No one else is waiting in the queue" );
}
}
Elements added to the PriorityQueue needs to implement Comparable as the PriorityQueue will use the elements natural ordering to place them in the right order in the queue. The Student are ordered by their name, alphabetically.
Processing App.Student(name=Aden, mark=82) (students remaining in the queue 1)
Processing App.Student(name=Jade, mark=85) (students remaining in the queue 0)
No one else is waiting in the queue
A Comparator can be used instead to order the elements in the PriorityQueue. Consider the following example.
package demo;
import lombok.Data;
import org.apache.commons.lang3.StringUtils;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class App {
@Data
private static class Student implements Comparable<Student> {
/**/public static final Comparator<Student> BY_BEST_MARK = Comparator.comparingInt( Student::getMark ).reversed();
private final String name;
private final int mark;
@Override
public int compareTo( final Student that ) {
return StringUtils.compare( name, that.name );
}
}
public static void main( final String[] args ) {
/**/final Queue<Student> students = new PriorityQueue<>( Student.BY_BEST_MARK );
students.add( new Student( "Jade", 85 ) );
students.add( new Student( "Aden", 82 ) );
while ( false == students.isEmpty() ) {
Student next = students.poll();
System.out.printf( "Processing %s (students remaining in the queue %d)%n", next, students.size() );
}
System.out.println( "No one else is waiting in the queue" );
}
}
A Comparator is added to the Student class which compares the students by their marks. Students with the highest marks will comes first.
Processing App.Student(name=Jade, mark=85) (students remaining in the queue 1)
Processing App.Student(name=Aden, mark=82) (students remaining in the queue 0)
No one else is waiting in the queue
Comparator is provided, the elements being places in the PriorityQueue do not need to implement Comparable.The practice shown above, where a Comparator is provided by the same data class is quite common and found in many classes, such as the String class and its CASE_INSENSITIVE_ORDER static field.
Stack
A Stack is a data structure that supports the last in first out (LIFO) ordering, as shown in the following diagram.
Elements are added and retrieved from one end of the stack, the top of the stack. A stack of plates is an example of a stack, as shown next.
We can only interact with the top of the stack. We cannot retrieve the bottom plate without first retrieving all the plates above it.
Stack class as this was not well implemented.The Deque is a preferred stack implementation. This is not a pure stack as it supports both LIFO and FIFO ordering.
Consider the following example.
package demo;
import java.util.ArrayDeque;
import java.util.Deque;
public class App {
public static void main( final String[] args ) {
final Deque<String> students = new ArrayDeque<>();
students.add( "Jade" );
students.add( "Aden" );
while ( false == students.isEmpty() ) {
String next = students.pollLast();
System.out.printf( "Processing %s (students remaining in the queue %d)%n", next, students.size() );
}
System.out.println( "No one else is waiting in the queue" );
}
}
The above example uses the pollLast() method to operate the queue in a LIFO order.
Processing Aden (students remaining in the queue 1)
Processing Jade (students remaining in the queue 0)
No one else is waiting in the queue