Queue Using linked list

 Algorithm : Stack Using Linked-List

Let us consider a linked-list pointed by header node.We have to
Implement Queue operations(Qinsert and Qdelete)using this linked-list.

Qinsert(header,item)
{
 t=getnode()      //getnode() is a function which creates a new node
 t->data=item       and returns the address of the node
 if(header->link=NULL)        //checks if the list is empty
  header->link=t
 else
 {
  t->link=header->link      //t points to the 1st node of the list
  header->link=t            //header points to t,hence t becomes the
 }                            1st node of the list
}

Qdelete(header)
{
 if(header->link=NULL)
   Print  "Queue  empty"
 else
 {
   ptr=header->link
   if(ptr->link=NULL)          //checks if there is only 1 element
     header->link=NULL           in the list
   else
   {
     trav=ptr->link            //trav points to the 1st node
     while(trav->link≠NULL)    until the list becomes empty
     {
      ptr=trav                 //ptr points to trav
      trav=trav->link          //trav moves to next node
     }
     ptr->link=NULL
   }
   return trav->data
 }
}

void show()
{
 trav=header->link
 if(trav=NULL)
   printf  "Queue empty"
 else
 { 
  while(trav≠NULL)                //until the list becomes empty
  {
   Printf  “trav->data”
   trav=trav->link                //trav moves to next node
  }
 }
}


Queue Using linked list

Source Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node *link;
};
struct node *header;

struct node * getnode()
{
 struct node *t;
 int item;
 t=(struct node *)malloc(sizeof(struct node));
 printf("\nEnter your data:");
 scanf("%d",&item);
 t->data=item;
 t->link=NULL;
 return t;
}

void show()
{
 struct node *trav;
 trav=header->link;
 if(trav==NULL)
   printf("\nQueue empty.");
 else
 {
 printf("\nQUEUE elements are:\n\n");
 while(trav!=NULL)
 {
  printf("  %d",trav->data);
  trav=trav->link;
 }
 }
 printf("\n");
}

void Qinsert()
{
 struct node *t;
 t=getnode();
 if(header->link==NULL)
 {
  header->link=t;
 }
 else
 {
  t->link=header->link;
  header->link=t;
 }
}


int Qdelete()
{
 struct node *trav,*ptr;
 if(header->link==NULL)
 {
   printf("\nQueue  empty.\n");
 }
 else
 {
   ptr=header->link;
   if(ptr->link==NULL)
   {
     header->link=NULL;
   }
   else
   {
     trav=ptr->link;
     while(trav->link!=NULL)
     {
      ptr=trav;
      trav=trav->link;
     }
     ptr->link=NULL;
   }
   return trav->data;
 }
}

void main()
{
 int ch,item;
 while(1)
 {
   printf("\n1.Qinsert  2.Qdelete  3.Show  4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch);
   switch(ch)
   {
     case 1:
	    Qinsert();
	    break;
     case 2:
	    item=Qdelete();
	    break;
     case 3:
	    show();
	    break;

     case 4:
	    exit(0);

   }
 }
}


 OUTPUT :
 
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:1

Enter your data:11

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:1

Enter your data:22

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:1

Enter your data:33

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:1

Enter your data:44

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:3

QUEUE elements are:

  44  33  22  11

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:3

QUEUE elements are:

  44

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

Queue  empty.