Today’s lecture is about circular queue. The problem with making a queue in an array is the right shifting of the data whenever we pop an element. One way to fix that problem is to run a for loop that shifts the elements one step back in the array after every pop.

Another way to fix this problem is to treat the array as a circular queue. In that case, The array gives the illusion of continuing in a circular way. What we actually do is that, we start using the old locations in the stack that had been popped. This brings us to the important task of finding out the conditions when the queue will be full, which is defined by the isFull() function.

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

According to this code, there are two conditions by which a queue can be full.

1. head is greater than tail by one place. This means that the user started popping values and while doing so, as we increment head, after popping the last value, the head becomes greater than tail.

2. The second condition becomes true if head was at the zero location and the tail was at the last place possible in the array.

If any of these two conditions are met, the queue is considered to be full.

In case of pushing, we need to check first if the array is full or not. Then we push to the appropriate place:

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

If you look at the code, after checking if the Queue is Full, we check if tail was either at the final position or -1. It then increments tail and puts the element to the appropriate spot. It also checks if the head was -1 or not and increments it if it was.

Otherwise, it just increments tail and puts the element at the appropriate place.

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}

For popping, it first checks if both head and tail are -1, this tells the user that queue is empty. Otherwise, it first checks if the array has the last value, then if the head was at the last value of the array and if these conditions are not met, it simply increments head and puts the data at the appropriate place. The complete code for the circular queue is as following:

class CircularQueue

{

private:

int head;

int tail;

int maxSize;

char* data;

public:

CircularQueue(int);

~CircularQueue();

bool isFull();

void push(char);

void pop();

};

CircularQueue::CircularQueue(int num)

{

head = tail = -1;

maxSize = num;

data = new char[num];

}

CircularQueue::~CircularQueue()

{

delete[] data;

}

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}