Circular Queue of Integers Using a Simple Array

Q#2. Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue. Make it thread safe.

Ans.

Analysis:

A queue is a First in First Out (FIFO) type Data Structure. The element which is added first is removed first. In order to implement a circular queue, we will have to keep track of the queue start index, queue end index and a variable to track the number of elements in queue.

Representation of circular array:

A circular array with six elements, Total queue capacity 8 elements:

Start Index = 0		End Index = 5		No of Elements = 6
1	2	3	4	5	6

After dequeing 2 elements

Start Index = 2		End Index = 5		No of Elements = 4
		3	4	5	6

After enqueing 3 elements

Start Index = 2		End Index = 0		No of Elements = 7
9		3	4	5	6	7	8

Approach:

As required we have to define three methods Initialize, Enqueue and Dequeue. Where Initialize will initialize/reset the Queue Array, Enqueue will add elements and Dequeue will remove elements from the queue. Further, we will implement locks on Array and variables to make this implementation thread safe.

Pseudo Code:

DECLARE QueueStart=0, NoofElements=0, QueueArray                                // Declare Queue Variables

FUNCTION Initialize(INT ArraySize) :

QueueStart=0, NoofElements=0, QueueArray  = NEW INT[ArraySize] // Initiate Queue Variables

FUNCTION Enqueue(INT NewElement) :

QueueArray[NewPosition] =   NewElement                        // NewPosition method returns new Index

NoofElements +=1

FUNCTION Dequeue() :

RETURN QueueTopElement                                                        // Return element from top of Queue

NoofElements -=1

QueueStart = NewQueueStart                                                  // QueueStart is set to new Start Index

C# Code:

 public class CircularQueue  
 {  
      // Variable Declaration  
      private int _noofElements = 0;  
      private int _queueStart = 0;  
      private int[] _queueArray;  
      private object _lock;  
      public int Length  
      {  
           get  
           {  
                return _noofElements;  
           }  
      }  
      //Function to get Next Index in circular array  
      public int NextIndex()  
      {  
           int extendedSize = _queueStart + _noofElements;  
           // Restart new index from start of array if end of array is reached  
           return extendedSize >= _queueArray.Length ? extendedSize - _queueArray.Length : extendedSize;  
      }  
      //Function to Initialize Queue Array and Reset Variables  
      public void Initialize(int Size)  
      {  
           // Initialize Circular Queue Array        
           lock(_lock)  
           {  
                _queueArray = new int[Size];  
                _queueStart = 0;  
                _noofElements = 0;  
           }  
      }  
      public void Enqueue(int NewMember)  
      {  
           if(_queueArray.Length == _noofElements)  
                throw new Exception("Queue is Full");  
           // Set member at new circular index  
           lock(_lock)  
           {  
                _queueArray[NextIndex()] = NewMember;  
                _noofElements++; // Increment element counter  
           }  
      }  
      public int Dequeue()  
      {  
           if(_noofElements == 0)  
                throw new Exception("Queue is Empty");  
           int temp = _queueArray[_queueStart]; // Store position value in temp variable  
           lock(_lock)  
           {  
                _queueArray[_queueStart] = 0; // Reset position value  
                _queueStart = (_queueStart == _queueArray.Length - 1) ? 0 : _queueStart + 1; // Get new start position  
                _noofElements--; // Decrement element counter  
           }  
           return temp;  
      }  
      public void Print()  
      {  
           foreach(int i in _queueArray)  
           {  
                Console.Write("{0:D2} | ", i);  
           }  
           Console.WriteLine();  
      }  
 }