Limitation of Linear Queue
Look at the following queue.
You cannot insert a new value now, because the queue is completely full. Consider the following case: two consecutive deletions are made.
Even though there is enough space to hold a new element, the overflow condition still occurs since the condition rear = MAX – 1 is still valid. This non-usable empty space is a major drawback of a linear queue. A solution to this problem is to make the queue circular.
A circular queue is a special type of queue where the last element is connected back to the first element thus forming a circle. In the circular queue, the first index comes right after the last index.
We start insertion from the beginning of the queue if we reach the end of the queue.
Circular Queue Operations
Every queue includes two pointers,
REAR, which indicate the position where deletion and insertion can be performed. Initially, values of FRONT and REAR is set to -1.
The circular queue is full if any of the following condition is met,
FRONT = 0 and REAR = Max – 1
FRONT = REAR + 1
Inserting a new element in the position pointed by REAR is called the enqueue operation.
- Print overflow and exit if the queue is full.
- For adding first element make
FRONT = 0.
- Increment REAR by 1.
- Insert new element in the position pointed by REAR.
Step 1: IF FRONT = and Rear = MAX-1 Write OVERFLOW Goto step 4 [End OF IF] Step 2: IF FRONT=-1 and REAR=-1 SET FRONT = REAR = 0 ELSE IF REAR = MAX-1 and FRONT != 0 SET REAR = 0 ELSE SET REAR = REAR + 1 [END OF IF] Step 3: SET QUEUE[REAR] = ITEM Step 4: EXIT
Deleting an element in the position pointed by FRONT is called the dequeue operation. We must check if the queue is empty before deletion.
- Print underflow and exit if the queue is empty.
- Return the value pointed by FRONT.
- Increment FRONT by 1 circularly.
FRONT = REAR = -1for the last element.
Step 1: IF FRONT = -1 Write UNDERFLOW Goto Step 4 [END of IF] Step 2: SET VAL = QUEUE[FRONT] Step 3: IF FRONT = REAR SET FRONT = REAR = -1 ELSE IF FRONT = MAX -1 SET FRONT = 0 ELSE SET FRONT = FRONT + 1 [END of IF] [END OF IF] Step 4: EXIT
Enqueue and dequeue operations on a circular queue is illustrated below.