QUEUES:
- Queue is a Linear Data Structure that follows First in First out (FIFO) principle.
- Insertion of element is done at one end of the Queue called “Rear “end of the Queue.
- Deletion of element is done at other end of the Queue called “Front “end of the Queue.
- Example: – Waiting line in the ticket counter.
Front Pointer:-
It always points to the first element inserted in the Queue.
Rear Pointer:-
It always points to the last element inserted in the Queue.
For Empty Queue:-
Front (F) = – 1
Rear (R) = – 1
Operations on Queue
Fundamental operations performed on the queue are
- EnQueue
- DeQueue
- EnQueue operation:-
- It is the process of inserting a new element at the rear end of the Queue.
- For every EnQueue operation
- Check for Full Queue
- If the Queue is full, Insertion is not possible.
- Otherwise, increment the rear end by 1 and then insert the element in the rear end of the Queue.
- DeQueue Operation:–
- It is the process of deleting the element from the front end of the queue.
- For every DeQueue operation
- Check for Empty queue
- If the Queue is Empty, Deletion is not possible.
- Otherwise, delete the first element inserted into the queue and then increment the front by 1.
Exceptional Conditions of Queue
- Queue Overflow
- Queue Underflow
- Queue Overflow:
- An Attempt to insert an element X at the Rear end of the Queue when the Queue is full is said to be Queue overflow.
- For every Enqueue operation, we need to check this condition.
- Queue Underflow:
- An Attempt to delete an element from the Front end of the Queue when the Queue is empty is said to be Queue underflow.
- For every DeQueue operation, we need to check this condition.
Implementation of Queue
Queue can be implemented in two ways.
- Implementation using Array (Static Queue)
- Implementation using Linked List (Dynamic Queue)
Array Declaration of Queue:
#define ArraySize 5 int Q [ ArraySize];
or
int Q [ 5 ];
Initial Configuration of Queue:
Queue Empty Operation:
Initially Queue is Empty.
- With Empty Queue, Front ( F ) and Rear ( R ) points to – 1.
It is necessary to check for Empty Queue before deleting (DeQueue) an element from the Queue (Q).
Routine to check for Empty Queue
int IsEmpty ( Queue Q )
{
if( ( Front = = – 1) && ( Rear = = – 1 ) ) return ( 1 );
}
int IsEmpty ( Queue Q )
{
if( ( Front = = – 1) && ( Rear = = – 1 ) ) return ( 1 );
- Queue Full Operation
As we keep inserting the new elements at the Rear end of the Queue, the Queue becomes full.
When the Queue is Full, Rear reaches its maximum Arraysize.
For every Enqueue Operation, we need to check for full Queue condition.
Routine to check for Full Queue
int IsFull( Queue Q )
{
if ( Rear = = ArraySize – 1 ) return ( 1 );
}
- Enqueue Operation
It is the process of inserting a new element at the Rear end of the Queue.
It takes two parameters, Enqueue(X, Q). The elements X to be inserted at the Rear end of the Queue Q.
Before inserting a new Element into the Queue, check for Full Queue. If the Queue is already Full, Insertion is not possible.
Otherwise, Increment the Rear pointer by 1 and then insert the element X at the Rear end of the Queue.
If the Queue is Empty, Increment both Front and Rear pointer by 1 and then insert the element X at the Rear end of the Queue.
Routine to Insert an Element in a Queue
void EnQueue (int X , Queue Q)
{
if ( Rear = = Arraysize – 1)
print (” Full Queue !!!!. Insertion not possible”);
else if (Rear = = – 1)
{
Front = Front + 1; Rear = Rear + 1; Q [Rear] = X;
}
else
{
Rear = Rear + 1; Q [Rear] = X;
- DeQueue Operation
It is the process of deleting a element from the Front end of the Queue.
It takes one parameter, DeQueue (Q). Always front element in the Queue will be deleted. Before deleting an Element from the Queue, check for Empty Queue.
If the Queue is empty, deletion is not possible.
If the Queue has only one element, then delete the element and represent the empty queue by updating Front = – 1 and Rear = – 1.
If the Queue has many Elements, then delete the element in the Front and move the Front pointer to next element in the queue by incrementing Front pointer by 1.
ROUTINE FOR DEQUEUE
void DeQueue ( Queue Q )
{
if ( Front = = – 1)
print (” Empty Queue !. Deletion not possible ” ); else if( Front = = Rear )
{
X = Q [ Front ]; Front = – 1; Rear = – 1;
}
else
{
X = Q [ Front ]; Front = Front + 1 ;
}
}
Other courses