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.
Let’s examine then, a couple of situations.
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 must stand in a queue.
So, what are 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). This is what we call in Computer Science as the FIFO (First in, first out) principle.
But there are situations where someone can go to the front of the queue. Let’s say a pregnant woman arrives in a queue, she should be allowed to go first. You are right. We also have in programming a way to model that: a Priority Queue.
In this case, we add elements to the queue according to their priority. But we add the elements at the end of their priority. In other words, if a pregnant woman arrives in the queue, she is positioned after the last pregnant woman in the queue.
Let’s see what common queue operations are available.
The Queue Abstract Data Type
The standard basic operations we can do with a queue, without regard to the programming language you use to implement the Abstract Data Type (ADT) are:
- 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 some problems and the solutions using queues.
Example 1
A secretary has a list of files that she needs to attend to. Files have an id and other information related to customers’ requests. Usually, there are more than 100 files on a desk. And they are ordered according to the date they were received. The secretary must process the files in the same order they were received. The first one to arrive is the first one that needs to be attended to. 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 in which every file must be processed. 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.
For the search, we need to do the search and make sure the files are stored 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.
So, first, we create the queue and add some files to it, so we can test our solution.
namespace QueueUsageExample
{
class Program
{
static void Main(string[] args)
{
SecretaryFile file1 = new SecretaryFile("1", "info");
SecretaryFile file2 = new SecretaryFile("2", "info");
SecretaryFile file3 = new SecretaryFile("4", "info");
SecretaryFile file4 = new SecretaryFile("3", "info");
Queue<SecretaryFile> queue = new Queue<SecretaryFile>();
queue.enqueue(file1);
queue.enqueue(file2);
queue.enqueue(file3);
queue.enqueue(file4);
}
}
class SecretaryFile
{
private String id;
private String info;
public SecretaryFile(String id, String info)
{
this.id = id;
this.info = info;
}
public String ID
{
get => id;
}
}
}
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.
SecretaryFile temp;
Queue<SecretaryFile> aux = new Queue<SecretaryFile>();
String id = "3";
bool found = false;
while (!queue.isEmpty())
{
temp = queue.dequeue();
aux.enqueue(temp);
if (temp.ID.Equals(id))
{
found = true;
break;
}
}
while (!aux.isEmpty())
{
queue.enqueue(aux.dequeue());
}
if (found)
{
Console.WriteLine("The file is on the queue");
}
else
{
Console.WriteLine("The file is not on the queue");
}
From the code above 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. However, 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. 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.
Example 2: Implement the method IndexOf(int x, Queue<int> q):int. This method must return the index of the last occurrence of x, or -1 if the element is not in the stack.
An important point to take note of is that is the last occurrence, not the first one. So, we need to go through all the elements in the queue. Remember, that we can temporarily modify the queue. But in the end, the original queue must be in its original state. For that, we need to have an auxiliary variable (another queue in this case) to store the elements we are removing from the queue, so later we can add them back to the original queue.
Find the code below.
public static int IndexOf(int x, Queue<int> queue)
{
int position = -1;
int elemNumber = 0;
Queue<int> aux = new Queue<int>();
while (!queue.isEmpty())
{
elemNumber += 1;
if (queue.front()==x)
{
position = elemNumber;
}
aux.enqueue(queue.dequeue());
}
while (!aux.isEmpty())
{
queue.enqueue(aux.dequeue());
}
return position;
}
You can test this method with the following console application.
Queue<int> q = new Queue<int>();
q.enqueue(1);
q.enqueue(2);
q.enqueue(1);
q.enqueue(3);
Console.WriteLine(IndexOf(1, q));
Remember if your target is .NET less than 6, you should have a class name and a method Main as the entry point to the console application.
Example 3: Implement the method Average(Queue<int> q):float. This method must return the average of the elements in the queue.
To calculate the average, we are going to use the basic algorithm for summing, and then we divide by the number of elements.
As usual, we need to have the original queue in its original state before we return the result.
Can you see the pattern?
public static float Average(Queue<int> q) {
float total = 0;
int elemNumber = 0;
Queue<int> aux = new Queue<int>();
while (!q.isEmpty())
{
elemNumber += 1;
total += q.front();
aux.enqueue(q.dequeue());
}
while (!aux.isEmpty())
{
q.enqueue(aux.dequeue());
}
return total/elemNumber;
}
Example 4: Implement the method LessThan(int x, Queue<int> q):int. This method must return how many elements less than x are in the queue.
In this case, we should use the basic algorithm for counting as the foundation to solve this problem.
See the code below.
public static int LesThan(int x, Queue<int> q)
{
int c = 0;
Queue<int> aux = new Queue<int>();
while (!q.isEmpty())
{
if (q.front() < x)
c++;
aux.enqueue(q.dequeue());
}
while (!aux.isEmpty())
{
q.enqueue(aux.dequeue());
}
return c;
}
You can test the last three examples together with the following code.
Queue<int> q = new Queue<int>();
q.enqueue(1);
q.enqueue(2);
q.enqueue(1);
q.enqueue(3);
Console.WriteLine("The last occurrence of the element {0} is in the position {1}", 1, IndexOf(1, q));
Console.WriteLine("The average of the elements in the queue is {0}", Average(q));
Console.WriteLine("There are {0} elements less than '{1}' in the queue", LesThan(2, q), 2);
After the execution of the code above, you will see the following result.
H@ppy coding!
Related topics:
- Stack data structure implementation in C# (using linked lists)
- Using the Stack data structure in C# (with examples)
- Using the Graph Data Structure to solve real-world problems in C#
- Using the List data structure in C#
- Command-line arguments in a C# console application
- General Tree Data Structure implementation in C# (with examples)