In this module, I will be introducing the Queue data structure which, different to a stack uses a First In, First Out (FIFO) order of adding and removing data. We will also see how enqueue and dequeue operations work. Along with various implementation methods we will also look at a specialisation to the queue called priority queue.

A queue is a collection that returns items in the order in which they are added. Think of a queue at the supermarket, customers line up and are served in the order in which they arrive.

Enqueue & Dequeue

Now that we have an understanding of what a queue is, let’s take a look at what it means to add and remove items from the queue. It all starts with creating the queue…

Queue queue = new LinkedList();

Next, we add(or enqueue) an item, this is like a shopper entering the queue. We will enqueue the integer value 1 to the queue.

queue.add(1);

1 is now at the head of the queue. We can continue to enqueue items to the queue…

queue.add(2);
queue.add(3);

And so on… Just like in a stack, we can peek at the item that is at the front of the queue…

queue.peek();

If we were to dequeue an item from this queue, which item would be removed? If you answered 1, you are correct. The head of the queue is always removed first. Let’s take a look at some code… I'll start in my main method by adding a queue. So, I'm going to do a queue of type integer and I'm going to use LinkedList. I'm going to add the numbers one to ten to my list. So again I'm just going to use a for loop…

public class QueueExample {
public static void main(String[] args) {
Queue queue = new LinkedList();
for(int i = 1;i {
queue.add(i);
}
}
}

From here, let’s expand the program to do a few things:
    1. Print out the elements in the queue.
    2. Dequeue & print the item removed.
    3. Print the item at the front of the queue.

public class QueueExample {
public static void main(String[] args) {
Queue queue = new LinkedList();
for(int i = 1;i {
queue.add(i);
}
System.out.println("Element in the queue: "+queue);
int removed = queue.remove();
System.out.println(removed + " was removed");

int top = queue.peek();
System.out.println("top element is: "+top);
}
}
Output:
Element in the queue: 1 2 3 4 5 6 7 8 9 10
1 was removed
top element is: 2

So, that was an example of how we can use a queue to allow us to add elements. And when you think of a queue, think of, you know, getting in line at a grocery store. The first person in line, is the first person to check out.

Priority queue

Queues show up in software design very frequently, think When you print jobs on your computer, they go into a print queue, and they wait for their printer to be available, and then they execute it in the order in which they were received. The methods for a print queue include add, which is used to add elements to the end of the list. Peek, which returns a copy of the first element. Remove removes the first or top element, and returns an error if it's empty. And poll is a new method that removes from the top, but this one returns null if the queue is empty instead of an error.

Sometimes a queue is in the form of a special implementation called a priority queue. Priority queues differ in that they are not First In, First Out, the highest priority items are dequeued first, regardless in the order in which they were added. A good analogy might be when boarding a plane, the airline asks business and first class passengers first, followed by elderly & disabled people, then maybe families with young children then the remainder of the passengers. This process is still a queue but is taking into account a predefined selection criteria first.