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();
}
}
