Generic Queue Implementation in C# Using Linked List

What are the characteristics of a queue?

  • The queue is A linear data structure with two points of access: front and back.
  • Items can only be added to the back (enqueue) and retrieved from the front (retrieve) (dequeue)
  • The First-In, First-Out rule (FIFO)

Formally, the queue abstract data type defines a collection that keeps objects in a sequence, with element access and deletion restricted to the first element in the sequence, referred to as the queue’s front. Element insertion is limited to the sequence’s tail, also known as the back of the queue. This restriction enforces the FIFO rule.

Queue Implementation

There are many possible ways to implement the queue ADT:

  • An array
  • A singly linked list with front
    In this article, I will show you how to implement the queue using LinkedList.$ads={1}
void Main()
{
	LinkedListQueue<int> list = new LinkedListQueue<int>();
	list.Enqueue(2);
	list.Enqueue(4);
	Console.WriteLine(list);
	Console.WriteLine(list.Dequeue());
}


public class LinkedListQueue<TOuter>
{

	// the node class
	private class Node<Tinner>
	{
		public Tinner Element {get;set;}
		public Node<Tinner> Next  {get;set;}

		public Node(Tinner e)
		{
			Element = e;
			Next=null;
		}

		
	}

	private Node<TOuter> _front; 
	private Node<TOuter> _rear;
	private int _count;    

	public LinkedListQueue()
	{
		_front = null;
		_rear = null;
		_count = 0;
	}

	// returns whether the queue is empty
	public Boolean IsEmpty
	{
		get
		{
			return (_count == 0);
		}
	}

	// returns the number of elements in the queue
	public int Count
	{
		get
		{
			return _count;
		}
	}

	// Return element at the front of the queue
	public TOuter Front
	{
		get
		{
			if (IsEmpty)
			{
				Console.WriteLine("Queue is empty!!");
				return default(TOuter);
			}
			return _front.Element;
		}
	}

	// Inserts 
	public void Enqueue(TOuter element)
	{
		Node<TOuter> v = new Node<TOuter>(element);
		if (_count == 0) _front = v;
		else _rear.Next = v;
		_rear = v;
		_count++;
	}

	// Removes 
	public TOuter Dequeue()
	{
		if (IsEmpty)
		{
			Console.WriteLine("Queue is empty.");
			return default(TOuter);
		}
		TOuter element = _front.Element;
		_front = _front.Next;
		_count--;
		if (_count == 0) _rear = null;
		return element;
	}
	
	public override String ToString()
	{
		String s;
		Node<TOuter> ptr = _front;
		s = "[";
		while (ptr != null)
		{
			s += ptr.Element + " ";
			ptr = ptr.Next;
		}
		return s + "]";
	}

}

Please do not post any spam link in the comment box😊

Post a Comment (0)
Previous Post Next Post