queue using circular linked list

queue using circular linked list

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int info;
    struct node *link;
}*rear=NULL;

void insert(int item);
int del();
void display();
int isEmpty();
int peek();

main()
{
    int choice,item;
    while(1)
    {
        printf("1.Insert\n");
        printf("2.Delete\n");
        printf("3.Peek\n");
        printf("4.Display\n");
        printf("5.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);

        switch(choice)
        {
         case 1:
            printf("Enter the element for insertion : ");
            scanf("%d",&item);
            insert(item);
            break;
         case 2:
            printf("Deleted element is %d\n",del());   
            break;
         case 3:
            printf("Item at the front of queue is %d\n",peek());
            break;
         case 4:
            display();
            break;
         case 5:
            exit(1);
         default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

void insert(int item)
{
    struct node *tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->info=item;
    if(tmp==NULL)
    {
        printf("Memory not available\n");
        return;
    }
   
    if( isEmpty() ) /*If queue is empty */
    {
        rear=tmp;
        tmp->link=rear;
    }
    else
    {
        tmp->link=rear->link;
        rear->link=tmp;
        rear=tmp;
    }
}/*End of insert()*/

del()
{
    int item;
    struct node *tmp;
    if( isEmpty() )
    {
        printf("Queue underflow\n");
        exit(1);
    }
    if(rear->link==rear)  /*If only one element*/
    {
        tmp=rear;
        rear=NULL;
    }
    else
    {
        tmp=rear->link;
        rear->link=rear->link->link;
    }
    item=tmp->info;
    free(tmp);
    return item;
}/*End of del()*/

int peek()
{
    if( isEmpty() )
    {
        printf("Queue underflow\n");
        exit(1);
    }
    return rear->link->info;
}/* End of peek() */

int isEmpty()
{
    if( rear == NULL )
        return 1;
    else
        return 0;
}/*End of isEmpty()*/


void display()
{
    struct node *p;
    if(isEmpty())
    {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue is :\n");
    p=rear->link;
    do
    {
        printf("%d ",p->info);
        p=p->link;
    }while(p!=rear->link);
    printf("\n");
}

Circular Queue

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.

Algorithm for Insertion:-Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:

1. if the "front" points where "rear" is pointing and the queue holds a not NULL value for it, then its a "queue overflow" state, so quit; else go to step-4.2
2. insert the new value for the queue position pointed by the "rear"

Algorithm for deletion:-
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one