The Queue data structure is studied in most Computer Science courses on Data Structure and Algorithms. In this post, you will learn the two main implementations of this important data structure.
What is a Queue
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first object going into the queue is the first one going out of the queue.
Because of this principle, the operations on a queue are limited. So, however you use a Queue data structure, the FIFO principle is enforced through the implemented operations.
Operations of a Queue
A queue data structure has only 4 operations. Some programming languages have implementations with more operations. However, if you use them, you probably are violating the FIFO principle.
The operations are the following:
- enqueue: add an element to the queue. There is no need to specify the position of the new element because it will be added to the end of the queue.
- dequeue: removes an element from the queue. There is no need to specify what element you want to remove. The first element is the one that will always be removed.
- front: this operation will return the first element in the queue.
- isEmpty: returns true if the queue is empty, otherwise, it returns false.
You need only the operations above to use the Queue data structure to solve problems. Extra operations like size, usually don’t make sense in this data structure.
To implement the Queue data structure, we can use arrays or linked lists.
I won’t show here the implementation with arrays because it has a fixed number of elements.
Queue data structure implementation in C# using linked lists
When you study data structures, the first data structure you implement is the list data structure.
A list can be implemented using arrays or linked lists.
Here we are going to use a linked list implementation provided by the .NET framework.
public class Queue<T>{
LinkedList<T> info;
public Queue(){
info = new LinkedList<T>();
}
public void enqueue(T e){
info.AddLast(e);
}
public T dequeue(){
if (info.First != null){
T e = info.First.Value;
info.RemoveFirst();
return e;
}
else
throw new Exception("The queue is empty");
}
public T front() {
if (info.First != null)
return info.First.Value;
else
throw new Exception("The queue is empty");
}
public bool isEmpty() {
return info.Count == 0;
}
}
In this case, we are reusing the operations implemented in a linked list. Doing that, we are following one of the principles of Object-Oriented Programming: reusability. You can read more about OOP principles in this post.
Anytime you want to use the Queue data structure to solve a certain problem, you can do it by using only the four methods implemented above. Let’s see an example.
Example of usage of the Queue data structure
The usual way to use the Queue data structure is by using a while loop and the operation isEmpty.
Search operations are not common in a queue, but you can implement them using an auxiliary queue as in the example below.
Queue<int> queue = new Queue<int>();
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
//Print all the elements in the queue and
//the queue must keep its initial state
Queue<int> aux = new Queue<int>();
int e;
while (!queue.isEmpty())
{
e = queue.dequeue();
Console.WriteLine(e);
// Add the element to an auxiliary queue
aux.enqueue(e);
}
// Put back the elements into the original queue
// using the auxiliary queue
while (!aux.isEmpty())
{
queue.enqueue(aux.dequeue());
}
Notice that from .Net 6, you don’t need to create a class with a method “main” as part of the console application.
Summary
You can use the Queue data structure to model situations that follow the FIFO principle.
To solve problems using queues you only need four operations: enqueue, dequeue, front and isEmpty.
For you to practice what you learned in this post, you can create the following C# console applications:
- Create a C# console menu application that give the user choices to test how a queue works. The choices in the menu can be the four operations available in the queue class implemented above.
H@ppy coding!
Related posts: