Hot Topics
Data Structure
Circular Queue
A circular queue is a special kind of queue in which the last element is attached/connected to the first element of queue.A circular queue can be thought as a ring.The main advantage of using a circular queue is that if we have some space before the space to which front pointer is pointing we can utilize that space by reassigning the rear to the empty space and enter new element.
Operations on Circular Queue
getFront() – Get the element pointed by front pointer
getRear() – Get the element pointed by rear pointer
push() – To insert element in the circular queue from the rear position and there can be two cases
We can’t enter when the queue is full i.e the front pointer is at 0 and the rear is at size-1
We can enter when the queue has atleast one empty place in it i.e rear is at the last position in queue and the front is not at the starting index of queue
pop() – To remove element from queue we need to see 3 parameters
Check if front pointer is pointing to -1 then the queue is empty
If front and rear pointers are pointing to same place means there is only 1 element in queue so remove it and set both front and rear to -1 and if front is at the last position of queue then set front to 0 and return element.
Applications
Circular queue is used in replacing pages when the page in front of queue will be chosen
It is used in CPU scheduling
Algorithm
Initialize an array and its size also initialize two pointers front and rear
isEmpty() – When the front and rear pointers are pointing to -1 that means queue is empty as -1 is not an index of array
isFull() – If the front pointer is pointing to 0 and the rear is pointing to the last index of the array
push() – To insert element in the circular queue from the rear position and there can be four cases
We can’t enter when the queue is full i.e the front pointer is at 0 and the rear is at size-1
If the queue is empty we have to reassign the front and rear pointer from -1 to 0 as 0 is the starting index of queue
If the front pointer is pointing to an index which is not the first index of queue and the rear is pointing to the last index of queue that means we have some empty space before the front pointer so we will be setting the rear pointer to 0 index and enter element in that place.
Normal case where we enter at the index pointed by the rear pointer and increase it.
pop() – To remove element from queue we need to see 3 parameters
Check if front pointer is pointing to -1 then the queue is empty
If front and rear pointers are pointing to same place means there is only 1 element in queue so remove it and set both front and rear to -1 and if front is at the last position of queue then set front to 0 and return element.
display() – To display elements in queue we have two main cases
If the queue is empty we don’t have elements to display
If the queue is not empty then we have to cases
Case 1:
When the rear pointer is pointing to a greater index than the front pointer then we’ll be displaying elements from front index to rear index
Case 2:
Since it is a circular queue there might be a case where front pointer is pointing to an index which is greater than the index pointed by rear pointer.In that case we have to first print all the elements from index pointed by the front pointer till the last index and then again start printing from the 0th index till the index pointed by rear pointer.
For example,we have a circular queue of length 5 and the front pointer of queue is pointing to index 3 and rear to index 2.Then we first print all the elements from index 3 to index 4 which is the last index of the circular queue of length 5 and then start printing from the index 0 of queue to the index 2 of queue which is pointed by rear pointer.
getFront() – Get the element pointed by front pointer
getRear() – Get the element pointed by rear pointer
#include
class CircularQueue
{
int *arr;
int front;
int rear;
int size;
public:
// constructor function
CircularQueue(int n)
{
size = n;
arr = new int[size];
front = -1;
rear = -1;
} // end of constructor
// function to check if queue is empty
bool isEmpty()
{
if (front == -1)
return true;
else
return false;
} // end of isEmpty()
// function to check if the queue is full
bool isFull()
{
if (front == 0 && rear == size - 1)
{
return true;
}
if (front == rear + 1)
{
return true;
} // end of isFull()
return false;
}
// function to push elements into queue
void push(int x)
{
// checking if queue is full then we cannot insert anything
if (isFull())
{
std::cout << "Queue is full" << std::endl;
return;
}
// queue is empty we are changing the index of front and rear to 0 and
// inserting element at the index pointed by rear pointer
else if (isEmpty())
{
front = rear = 0;
arr[rear] = x;
}
// when there is some vacant space before the index pointed by the
// front pointer
else if (rear == size - 1 && front != 0)
{
rear = 0;
arr[rear] = x;
}
// normal case
else
{
rear++;
arr[rear] = x;
}
std::cout << x << " is inserted in queue" << std::endl;
} // end of push function
// function to remove element from queue
void pop()
{
int element;
// nothing can be removed if queue is empty
if (isEmpty())
std::cout << "Queue is empty" << std::endl;
// there is element in queue
else
{
element = arr[front];
std::cout << element << " is popped out of queue" << std::endl;
// there is only a single element
if (front == rear)
{
front = rear = -1;
}
// removing the last element in queue
else
{
if (front == size - 1)
front = 0;
front++;
}
}
} // end of pop function
// function to display elements of queue
void display()
{
// queue is empty nothing to print
if (isEmpty())
{
std::cout << "Queue is empty" < front)
{
for (int i = front; i <= rear; i++)
{
std::cout << arr[i] << " ";
}
}
else
{
for (int i = front; i <= size - 1; i++)
{
std::cout << arr[i] << " ";
}
for (int i = 0; i <= rear; i++)
{
std::cout << arr[i] << " ";
}
}
std::cout << std::endl;
}
} // end of display function
// function to get the front element of queue denoted by the front pointer
void getFront()
{
if (isEmpty())
{
std::cout << "Queue is empty" << std::endl;
}
std::cout << "The front element of the queue is:" << arr[front] << std::endl;
} // end of getFront function
// function to get the rear element of queue denoted by the rear pointer
void getRear()
{
if (isEmpty())
{
std::cout << "Queue is empty" << std::endl;
}
std::cout << "The rear element of the queue is:" << arr[rear] << std::endl;
} // end of getRear function
};
int main()
{
CircularQueue cq(5);
cq.push(10);
cq.push(20);
cq.push(30);
cq.push(40);
cq.push(50);
cq.push(60);
cq.display();
cq.getFront();
cq.getRear();
cq.pop();
cq.push(60);
cq.display();
cq.pop();
cq.display();
return 0;
}
Output
10 is inserted in queue
20 is inserted in queue
30 is inserted in queue
40 is inserted in queue
50 is inserted in queue
Queue is full
10 20 30 40 50
The front element of the queue is:10
The rear element of the queue is:50
10 is popped out of queue
60 is inserted in queue
20 30 40 50 60
20 is popped out of queue
30 40 50 60
Automata Fixing