The Queue data structure is used in the solution of many different problems. In this article, I’ll explain what a queue is, what are the methods available for you to use and, one example of how we can use it to solve problems.
As you should remember, in programming, especially in Object-Oriented Programming, we aim to model real-world situations. For that, we start from a problem or a certain situation, and then we create the computational model.
Table of Contents
Queues in the real-world
Queues are present in many different situations in the real world.
When you go to a shop, you probably must stand in a queue.
If you want to buy medicine in a pharmacy, there is also a queue.
Sometimes you go to an ATM to withdraw money. If there are more people there when you arrive, you have to stand in a queue.
So, what is the underlying principles in queues?
It is simple, the first one to go in the queue, is the first one to go out of the queue (at least that is how it should be if people have social discipline). We know this in Computer Science as the FIFO (First in, first out) principle.
But there are situations that someone can go to the front of the queue. Let’s say a pregnant woman arrives at a queue, she should go first. You are right. We also have in programming a way to model that. We can use a Priority Queue.
In this case, we add elements to the queue according to their priority. Also, the elements are added at the end of their priority. In other words, if a pregnant woman arrives at the queue, she will be after the last pregnant woman in the queue.
Let’s see what common queue operations are available.
The Queue Abstract Data Type
There are basic operations that are considered standard with disregard of the programming language the Abstract Data Type (ADT) is implemented.
The common operations for the ADT Queue are the following:
- enqueue: adds an element to the end
- dequeue: retrieve and removes the element at the front of the queue
- front: retrieve the element at the front of the queue
- isEmpty: return true if the queue is empty, otherwise it returns false.
With these four basic operations, you should be able to use a queue data structure to solve real-life problems.
Queue data structure examples
Let’s examine one problem and its solutions using queues.
Problem 1: File processing
A secretary has a list of files that she needs to attend. Files have an id and other information related to customers requests. Usually, there are more than 100 files on a desk. The files are ordered according to the date they were received.
The secretary must process the files in the same order she received them. The first one to arrive is the first one that she will process. The boss wants to know if there is a file with a certain id on the desk.
Now the secretary must search through the files and she must keep the same order because that is the order that she must process every file. How can we provide a computational solution to this problem?
The first thing is that we can see the files follows the FIFO principle. The first one coming in, is the first one going out. So, we can store the files in a queue.
Notice that we need to do the search and make sure we store the files in the same order at the end of the search. Also, notice we don’t have access to the internal implementation of the queue. We just must use the operations defined in the ADT Queue.
If you still don’t not how to search in a collection of elements, you can read about it in the post about the 5 basic algorithms.
So, first, we create the queue and add some files to it, so we can test our solution.
class SecretaryFile {
private String id;
private String info;
public SecretaryFile(String id, String info) {
this.id = id;
this.info = info;
}
public String getId() {
return id;
}
}
We need, for this implementation, the method compareTo.
We are going to use a Java implementation of a queue that requires the elements implements the interface Comparable. If you use an implementation of the ADT Queue that is not a priority queue, then you won’t need this method.
public class QueueSecretaryExample {
public static void main(String[] args) {
SecretaryFile file1 = new SecretaryFile("1", "info");
SecretaryFile file2 = new SecretaryFile("2", "info");
SecretaryFile file3 = new SecretaryFile("3", "info");
SecretaryFile file4 = new SecretaryFile("4", "info");
Queue<SecretaryFile> queue = new Queue<>();
queue.enqueue(file1);
queue.enqueue(file2);
queue.enqueue(file3);
queue.enqueue(file4);
}
}
Now, let’s implement a basic algorithm for searching an element. Notice in this case we don’t have an operation that returns the element at a certain position. We can only have access to the element at the front of the queue. Also, to access the second element, we must remove the first one from the queue.
public class QueueSecretaryExample {
public static void main(String[] args) {
SecretaryFile file1 = new SecretaryFile("1", "info");
SecretaryFile file2 = new SecretaryFile("2", "info");
SecretaryFile file3 = new SecretaryFile("3", "info");
SecretaryFile file4 = new SecretaryFile("4", "info");
Queue<SecretaryFile> queue = new Queue<>();
queue.enqueue(file1);
queue.enqueue(file2);
queue.enqueue(file3);
queue.enqueue(file4);
SecretaryFile temp;
Queue<SecretaryFile> aux = new Queue<>();
String id = "3";
boolean found = false;
while (!queue.isEmpty()){
temp = queue.dequeue();
aux.enqueue(temp);
if (temp.getId().equals(id)){
found = true;
break;
}
}
while (!aux.isEmpty()){
temp = aux.dequeue();
queue.enqueue(temp);
}
if (found){
System.out.println("The file is in the queue");
}
else{
System.out.println("The file is not in the queue");
}
}
}
From the code below note the following:
- To go throw all the elements in a queue, we must use an auxiliary variable to keep all the elements. In this case, we use another queue to keep the elements in the same order, but we can also use another data structure.
- We use a while loop to empty the queue. The stop condition is when the queue is empty, so inside the loop we must remove the elements of the queue. Otherwise, we will have an infinite loop.
- Before the program finishes the execution, make sure the original queue is in the same state that at the beginning, so you don’t lose any information in the process.
H@ppy coding!
