Circular Queues

Today I'm going to talk about circular queues on what I've learned.

In the last post we discussed about queues .

There is a small issue with circular queues.

Let's say that we have a queue with a size of 5 elements. Queue array has 5 memory allocations for us to use.

Let's assume a random number (34) was inserted to our queue as first element now. At this moment, the queue array's front and rear values are both zero. One memory location is taken. Four to go.

Now let's insert 4 random number elements to make it full. The memory allocation should look like below.

Now let's delete one element. The front element which is 34 gets deleted. And notice the front shifts one up to the second element which is correct and now front is 1.

See the rear's value. The rear takes its largest number which is 4.

Now we need to insert one more element to our queue.
Let's recall the insert method from the queues post.

It checks if the rear is in its maximum size first; If it is not, allow to insert to queue.

But why do we need to insert an element to a queue which is full ?
Is it full ? No it is not because we deleted one element right ?

Yes, but the queue implementation does not allow us to use the free memory allocations even if there are some free slots available in it. It happens once the rear becomes its maximum value.

We cannot insert more elements to queue but can delete from it.

This is the issue with the queue implementation. The solution is circular queue.

A circular queue is a queue which is a special queue with reusable memory locations. So if there are free slots available we can use them to insert values.

Therefore, we need to modify our insert and delete methods of our queue to support this functionality.

insert method

public void insert(int x) {
   if (items == size) {
      System.out.println("Queue already full!");
   }
   else {
      if(rear == size - 1) {
         rear = -1;
      }
      rear++;
      queue[rear] = x;
      items++;
      System.out.println(x + " Inserted to queue");
   }
}

// first checks if queue is full not by checking the 
// the rear's maximum value, but by comparing
// if items count is the size of queue array's length.
// if it is we do not allow insertion, or else
// we checks if rear is in its max and if so
// adjust the rear's value to adopt circular queue behavior
// by pointing it to rear's initial value which is (-1).

delete method

public void delete() {
   if (items == 0) {
      System.out.println(“Queue is Empty!”);
   }
   else {
      int frontItem = queue[front];
      front++;
      if (front == size) {
         front = 0;
      }
      items--;
      System.out.println(frontItem + " Deleted from queue");
   }
}

// first we check whether queue is empty
// if it is we do not allow to delete from the queue
// else we take the first item to a variable called 
// frontItem and then shifts up front by one.
// if front's value is the maximum then assign
// front's value to 0 which is the initial value 
// of front thus adopting circular queue behavior.

The circular queue code sample explained above uses integers as its element type.
Source code is available in following url.

https://github.com/lizardkingLK/CircularQueues