Skip to main content

Circular queue implementation in C

In my previous posts, we have seen what is queue data structure and how to implement it using linked list and array

Is this queue full?
But we have seen that the array implementation had some problem - it would say "Queue is full" even when the queue was not full.










In the image above, there are 3 slots free in the begining of the array. But as back (rear) is equal to size of array -1, the program will say - queue is full.

One way of overcoming this is to implement a circular queue. That is once end of array is reached, go back to beginning of array and insert elements there. Like this.
Image courtesy:maxtudor.com
 As can be seen in this diagram, once we reach end of array, next element 11 is inserted at the beginning of array. Then we continue from there.

We can say that

index = rear % MAX
array[index] = new_element

Similarly when dequeuing, we can say that

index = front % MAX
temp = array[index]

That way, when front and rear exceed MAX, they continue from 0.

Is the queue full or is it empty?

But the problem arises here. How do we determine whether the queue is full? Or the queue is empty?

In case of earlier implementation, rear=front would have meant that queue is empty.

But in the case of circular queue, front = rear may mean queue is empty or it may mean queue is full.

One way of solving this is to use one extra variable, num_ele - number of elements. Enqueue would increment num_ele and dequeue would decrement num_ele. num_ele is 0 - indicates queue is empty. num_ele is MAX indicates queue is full.

Few changes I have made to this implementation are
  1. Store array, rear, front and num_ele in a structure
  2. Initialize rear and front to -1 and initialize num_ele to 0
  3. When enqueing or adding an element
    1. If queue is not full
      1. Increment rear
      2. Add the new element at array[rear%MAX] (Max is size)
  4.  When dequeing or removing an element
    1. If queue is not empty
      1. save array[front%MAX] in temp
      2. Increment front
      3. return temp
  5. To find if the queue is empty
    1. If num_ele is 0 queue is empty
  6. To find if the queue is full
    1. If num_ele = MAX , queue is full
 Let us write code for enqueue now.


    void enqueue(struct queue *qp,int num)
    {
    if(is_full(qp))
    {
    printf("The queue is full. Can not add elements...");
    }
    else
    {
    (qp->rear)++;
    int index = qp->rear % MAX;
    qp->arr[index] = num;

    (qp->num_ele)++;
    if(qp->front==-1)
    qp->front = 0;
    }

    }


    So we increment rear. (qp->rear because we need a pointer to structure queue as we are modifying queue). But if rear exceeds MAX, we need to start from 0. So index = rear%MAX and then we add arr[index] = num.

    But what is the last if statement in the function. You remember that front and rear are initialized with -1. So when first element is added, front should point to that element. That is why front is incremented.

    Next let us write dequeue function.


    int dequeue(struct queue *qp)
    {
    int temp = -1;
    if(is_empty(qp))
    {
    printf("Queue is empty");
    }
    else
    {
    int index = qp->front %MAX;
    temp = qp->arr[index];
    (qp->front)++;
    (qp->num_ele)--;
    }
    return temp;
    }

    Here we are saving arr[front] in temp and then incrementing front. The function returns the value removed from the queue - temp. To take care of wrapping back, we again use % operator. index = front%MAX.

    Next we should write print function which will iterate over all the elements of the queue.


    void print_queue(struct queue *qp)
    {
    int i;
    printf("Queue is ");
    for(i = qp->front;i<=qp->rear;i++)
    printf("%d---",qp->arr[i%MAX]);
    printf("\n");
    }

    We start from front element of array and go till rear element. And as i may be more than size of array, we use i%MAX here too.

    Here is the complete program.


    #include<stdio.h>
    #define MAX 5

    struct queue
    {
    int arr[MAX];
    int front,rear;
    int num_ele;
    };

    void init(struct queue *qp)
    {
    qp->front = qp->rear = -1;
    qp->num_ele = 0;
    }

    int is_empty(struct queue *qp)
    {
    return qp->num_ele==0;
    }

    int is_full(struct queue *qp)
    {
    return qp->num_ele==MAX;
    }

    void enqueue(struct queue *qp,int num)
    {
    if(is_full(qp))
    {
    printf("The queue is full. Can not add elements...");
    }
    else
    {
    (qp->rear)++;
    int index = qp->rear % MAX;
    qp->arr[index] = num;

    (qp->num_ele)++;
    if(qp->front==-1)
    qp->front = 0;
    }
    }

    int dequeue(struct queue *qp)
    {
    int temp = -1;
    if(is_empty(qp))
    {
    printf("Queue is empty");
    }
    else
    {
    int index = qp->front %MAX;
    temp = qp->arr[index];
    (qp->front)++;
    (qp->num_ele)--;
    }
    return temp;
    }

    void print_queue(struct queue *qp)
    {
    int i;
    printf("Queue is ");
    for(i = qp->front;i<=qp->rear;i++)
    printf("%d---",qp->arr[i%MAX]);
    printf("\n");
    }


    int main()
    {
    struct queue q1;
    init(&q1);

    while(1)
    {
    printf("Enter 1 - enqueue 2 - dequeue 3 - exit");
    int opt;
    scanf("%d",&opt);
    if(opt==1)
    {
    int n;
    printf("Enter a number:");
    scanf("%d",&n);
    enqueue(&q1,n);
    print_queue(&q1);

    }
    else if(opt==2)
    {

    int n;
    n = dequeue(&q1);
    if (n!=-1){
    printf("Value dequed is %d\n",n);
    print_queue(&q1);
    }
    }
    else
    break;

    }
    return 0;
    }



    You can download the program from here.

    Comments

    Popular posts from this blog

    Josephus problem

    Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...

    Lowest common ancestor of binary search tree

    Question : Write a function to print the lowest common ancestor of two nodes in a binary search tree.  Lowest common ancestor of two nodes x and y in a binary tree is the lowest node that has both x and y as descendants. Here lowest common ancestor of 1 and 7 is 3. LCA of 13 and 7 is root - 8. And LCA of 6 and 7 is 6 itself. The program to find gets complicated for an ordinary binary tree. But for a binary search tree, it is quite simple. As we see from the diagram above, the paths to 1 and 4 are common till the node 3. And at 3 they branch in different directions. So 3 is our LCA. That is lowest common ancestor is the node where the paths to x and y from root deviate. As long as they branch in same direction, we continue to traverse. When they branch in different directions, that is the lowest common ancestor. So let us write a simple algorithm, set temp=root if temp->val >x and temp->val>y temp = temp->left else if temp->val<x and ...

    In order traversal of nodes in the range x to y

    Question : Write a function for in-order traversal of nodes in the range x to y from a binary search tree. This is quite a simple function. As a first solution we can just traverse our binary search tree in inorder and display only the nodes which are in the range x to y. But if the current node has a value less than x, do we have to traverse its left subtree? No. Because all the nodes in left subtree will be smaller than x. Similarly if the current node has a key value more than y, we need not visit its right subtree. Now we are ready to write our algorithm.     if nd is NOT NULL  if nd->val >=x then visit all the nodes of left subtree of nd recursively display nd->val if nd->val <y then visit all the nodes of right subtree of nd recursively  That's all. We have our function ready. void in_order_middle (NODEPTR nd, int x, int y) { if (nd) { if (nd -> val >= x) in_order_middle(nd...