Circular Queue

When we dequeue an element from queue using array,front is incremented by 1.

Now suppose we declare a queue of size 5.We enqueue 5 elements and then dequeue one.Now when you try to enqueue an element it would be a queue overflow case as rear is at last position.But the actual elements in queue are 4 and queue has a size 5.Weird.By circular queue you can utilize the empty positions from where you dequeue elements.

Scenario 





Using circular queue

    

                  front              rear  
            _____________________________
                 |  2  |  3  |  4  |  5  |______
            _____|_____|_____|____ |_____|      |
             /|\                                |
              |_________________________________|

Enqueue

            rear  front  
            _____________________________
              6  |  2  |  3  |  4  |  5  |______
            _____|_____|_____|____ |_____|      |
             /|\                                |
              |_________________________________|

front keeps track of front element in queue.
rear keeps track of last element in queue.

Lets see how we can implement circular queue using an array.

Declaring the queue structure

typedef struct
{
    int front,rear,arr[SIZE];
}queue;

Initialize 

front = rear = -1

Check empty queue

front == -1 

              OR

rear == -1

Check full queue

front == (rear + 1) % SIZE

              front                    rear
              _____________________________
                1  |  2  |  3  |  4  |  5  |_____            suppose SIZE = 5
              _____|_____|_____|____ |_____|     |
               /|\                               |
                |________________________________|

Enqueue

rear = (rear + 1) % SIZE

If queue is empty we need to increment front.

void enqueue()
{
    int element;

    do
    {
        if(isFull())
        {
            printf("\nCircular queue overflow");
            break;
        }

        printf("\nEnter element to be enqueued ");
        scanf("%d",&element);

        if(isEmpty())
            q.front++;

        q.rear = (q.rear+1)%SIZE;
        q.arr[q.rear] = element;

        printf("\nEnqueue more elements ? ");

        fflush(stdin);

    }while(getchar()=='y');
}

Dequeue

front = (front + 1) % SIZE

If last element is left in queue,then initialize the queue.

            rear             front 
           _____________________________
             6  |     |     |  4  |  5  |______
           _____|_____|_____|____ |_____|     |
            /|\                               |
             |________________________________|


Dequeue


            rear                   front
           _____________________________
             6  |     |     |     |  5  |______
           _____|_____|_____|____ |_____|     |
           /|\                                |
            |_________________________________|

Dequeue

           front,rear
           __________________________________
               6     |     |     |     |     |______
           __________|_____|_____|____ |_____|     |
              /|\                                  |
               |___________________________________|


Dequeue
           Initialize queue (front = rear = -1)

int dequeue()
{
    int element = q.arr[q.front];

    if(isEmpty())
    {
        printf("\nQueue underflow.");
        return -1;
    }
    else 
    {
        if(q.front == q.rear)
            init();
        else
            q.front = (q.front+1)%SIZE;
        return element;
    }
}

Display

void display()
{
    int i;

    if(isEmpty())
    {
        printf("\nQueue is Empty");
        return;
    }

    printf("\n");

    for(i=q.front;i!=q.rear;i=(i+1)%SIZE)
        printf("%d ",q.arr[i]);

    printf("%d",q.arr[i]);              //print rear element
}

Complete Code with output