Circular Queue Data Structure
A circular queue is the extended version of a regular queue where the last
element is connected to the first element. Thus forming a circle-like
structure.
Circular queue representation
The circular queue solves the major limitation of the normal queue. In a
normal queue, after a bit of insertion and deletion, there will be non-usable
empty space.
Limitation of the regular Queue
Here, indexes 0 and 1 can only be used after resetting the queue (deletion
of all elements). This reduces the actual size of the queue.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try
to increment the pointer and we reach the end of the queue, we start from
the beginning of the queue.
Here, the circular increment is performed by modulo division with the queue
size. That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Circular Queue Operations
The circular queue work as follows:
two pointers FRONT and REAR
FRONT track the first element of the queue
REAR track the last elements of the queue
initially, set value of FRONT and REAR to -1
1. Enqueue Operation
check if the queue is full
for the first element, set value of FRONT to 0
circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next
it would be at the start of the queue)
add the new element in the position pointed to by REAR
2. Dequeue Operation
check if the queue is empty
return the value pointed by FRONT
circularly increase the FRONT index by 1
for the last element, reset the values of FRONT and REAR to -1
However, the check for full queue has a new additional case:
Case 1: FRONT = 0 && REAR == SIZE - 1
Case 2: FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular
increment and when its value is just 1 less than FRONT , the queue is full.
Operations
Applications of Circular Queue
CPU scheduling
Memory management
Traffic Management
Deque Data Structure
Deque or Double Ended Queue is a type of queue in which insertion and
removal of elements can either be performed from the front or the rear.
Thus, it does not follow FIFO rule (First In First Out).
Representation of Deque
Types of Deque
Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both
the ends.
Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both
the ends.
Operations on a Deque
Below is the circular array implementation of deque. In a circular array, if the
array is full, we start from the beginning.
But in a linear array implementation, if the array is full, no more elements
can be inserted. In each of the operations below, if the array is full,
"overflow message" is thrown.
Before performing the following operations, these steps are followed.
1. Take an array (deque) of size n .
2. Set two pointers at the first position and set front = -1 and rear = 0 .
Initialize an array and pointers for
deque
1. Insert at the Front
This operation adds an element at the front.
1. Check the position of front.
Check the position of front
2. If front < 1 , reinitialize front = n-1 (last index).
Shift front to the end
3. Else, decrease front by 1.
4. Add the new key 5 into array[front] .
Insert the element at Front
2. Insert at the Rear
This operation adds an element to the rear.
1. Check if the array is full.
Check if deque is full
2. If the deque is full, reinitialize rear = 0 .
3. Else, increase rear by 1.
Increase the rear
4. Add the new key 5 into array[rear] .
Insert the element at rear
3. Delete from the Front
The operation deletes an element from the front
.
1. Check if the deque is empty. Check if deque is empty
2. If the deque is empty (i.e. front = -1 ), deletion cannot be performed
(underflow condition).
3. If the deque has only one element (i.e. front = rear ), set front = -
1 and rear = -1 .
4. Else if front is at the end (i.e. front = n - 1 ), set go to the front front = 0 .
5. Else, front = front + 1 .
Increase the front
4. Delete from the Rear
This operation deletes an element from the rear.
1. Check if the deque is empty.
Check if deque is empty
2. If the deque is empty (i.e. front = -1 ), deletion cannot be performed
(underflow condition).
3. If the deque has only one element (i.e. front = rear ), set front = -
1 and rear = -1 , else follow the steps below.
4. If rear is at the front (i.e. rear = 0 ), set go to the front rear = n - 1 .
5. Else, rear = rear - 1 .
Decrease the rear
5. Check Empty
This operation checks if the deque is empty. If front = -1 , the deque is
empty.
6. Check Full
This operation checks if the deque is full. If front = 0 and rear = n -
1 OR front = rear + 1 , the deque is full.
Applications of Deque Data Structure
1. In undo operations on software.
2. To store history in browsers.
3. For implementing both stacks and queues.
