We have seen the Linked list and Stack in our previous article. Let us see another interesting and commonly used Data Structure, Queue which is similar to stack.
What is a Queue in Data structure?
Queue Data Structure is a First In First Out type of Data Structure. Here the data that gets inserted into this structure first will be coming out first. The meaning of the Queue as the name says it is very much relatable to the real-world, In our life at least once we would have waited in a Queue at Super Markets, Shops, etc. So a person at the front of the Queue is served first. In Computer Programming also Queue is one of the common data structures used to solve many problems. It is common in data structures interview questions. In this article, we will discuss the implementation of a queue in C#.
The below image helps to visualize the queue data structures. Let us assume that we have a queue data structure with an integer as the data type. The queue is having two ends front & rear side as shown in the figure. The data inserted to the queue from the rear side & taken out from the front side. The names front & rear is just for illustration purpose only.
A Basic Queue data structure will have operations like enqueue, dequeue & peek operations.
Implementation of Queue in C#
Let’s start Queue implementation in c#. We can implement this data structure using many different ways, In this tutorial, we are using a singly linked list. Below is the sample linked list Node having two fields of data & next. If you are not familiar with the linked list data structure you can check our linked list tutorial.
public class LinkedListNode
{
public int data;
public LinkedListNode next;
public LinkedListNode(int data)
{
this.data = data;
this.next = null;
}
}To implement a queue in c#, we will create a class Queue with two properties front & rear of the type LinkedListNode. We will also have a constructor to initialize these properties to null.
We have created a simple method to create a linked list node for us with data property set to the value that we pass in to this function.So we don’t have to worry about the creation of Node.
public class Queue
{
LinkedListNode front;
LinkedListNode rear;
public Queue()
{
front = null;
rear = null;
}
public LinkedListNode GetNode(int data)
{
LinkedListNode node = new LinkedListNode(data);
return node;
}
}In the next section of this article, we will discuss the individual operations of the queue in detail.
Inserting to a queue in C# or Enqueue
Inserting the data to a queue is commonly known as enqueue operations. Here the data will be added from the rear side of the queue (from the above example). Below is the code which does this operation.
public void Enqueue(int data)
{
LinkedListNode newNode = GetNode(data);
if (front == null)
{
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
In this method, we are getting a new node & checking if the front is null which indicates the queue is null. If it is null we are creating a new node & pointing it to both front and rear. If the queue is not empty, then we are making the rear to point the new node & making the new node as rear.
Deleting from queue in C# or Dequeue
Removing the data from the queue is known as dequeue operation. We will be doing a dequeue operation from the front of the queue.
public int DeQueue()
{
int peek = -1;
if (front != null)
{
peek = front.data;
front = front.next;
}
return peek;
}Here we will be checking if the queue is empty or not.If the queue is empty meaning we don’t have any data to dequeue from queue & we will return -1 from the queue,otherwise we simply making the front to point next element.
Peek Operation
Peek Operation is just similar to what we have seen in our stack data structure tutorial. We will check if the queue is empty or not accordingly we will return the peek element.
public int GetPeek()
{
if (front != null)
{
return front.data;
}
return -1;
}Is Queue Empty
Below is the code for IsEmpty, which checks if the queue has any elements or not. If the queue doesn’t have any elements front will be null. In the below code we will be checking the front & returning boolean based on the value.
public bool IsEmpty()
{
if(front==null)
{
return true;
}
return false;
}Simple Example
As we have seen the main methods of queue such as Enqueue, Dequeue, etc. Below is the simple queue in c#. This example is a demonstration purpose only.
We are inserting some example values and removing those in a while loop.
public static void Main(string[] args)
{
Queue queue = new Queue();
queue.Enqueue(10);
queue.Enqueue(15);
queue.Enqueue(20);
while (!queue.IsEmpty())
{
Console.WriteLine(queue.DeQueue());
}
}Queue<T> in C#
.NET namespace System.Collections.Generic provides the built in generic queue in c#.We can specify the type while declaring the queue and don’t have t worry about type safety.Let us see generic c# queue example.
using System;
using System.Collections.Generic;
namespace LearnQueue
{
class Practice
{
public static void Main(string[] args)
{
Queue<int> queue = new Queue<int>();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(40);
queue.Enqueue(60);
while(queue.Count!=0)
{
Console.WriteLine(queue.Dequeue());
}
}
}
}
As you can see from the example we are creating a Generic Queue of type integer. We are queuing some random integers, when we execute this code we can see that the output is printed in the order in which we inserted those integers to the queue. In this example, 10 20 40 60. Here we are checking whether the Queue is empty or not by getting the number of elements in the queue by queue.Count
Thread Safe Queue in C#
.NET also has provides us the thread-safe implementation of Queue. The namespace System.Collections.Concurrent has the thread-safe version of the Queue, here we don’t have to worry about the concurrent access of this object by multiple threads. The below example shows the thread-safe version example.
using System;
using System.Collections.Concurrent;
using System.Threading;
namespace LearnQueueMultithreaded
{
class Practice
{
public static void Main(string[] args)
{
ConcurrentQueue<int> queue = new ConcurrentQueue<int>();
Thread thread1 = new Thread(() =>
{
queue.Enqueue(10);
queue.Enqueue(20);
});
Thread thread2 = new Thread(() =>
{
queue.Enqueue(40);
queue.Enqueue(60);
});
thread1.Start();
thread2.Start();
thread1.Join();
thread2.Join();
while (queue.Count != 0)
{
if (queue.TryDequeue(out int x))
{
Console.WriteLine(x); ;
}
}
}
}
}So we have covered the basic implementation of Queue in C#. This data structure used to solve many real-world problems. However, if you want to deep dive into the time complexity and practice problems related to queue you can check here.
