Friday, 25 July 2014

Queue Implementation In One way Link list

Queue:

queue data structure

A queue is a linear list of element in which
è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out


Algorithm to Insertion in Queue :


Insertion in queue always take place at rear

1:-create a new node (=temp ) and assign data to it
2:-rear->link=temp and temp->link=NULL
3:-rear=rear->link
4:-Exit

Algorithm to Deletion from Queue :


Deletion from queue always take place at front .

1:- create a pointer of type struct node (let temp)
2:-temp=front
3:-front=front->link
4:-free temp
5:-Exit 

Queue implementation Using one way link list :


  1. // Queue implementation in one way link List
  2. //http://beginer2cs.blogspot.com
  3. #include<stdio.h>
  4. #include<malloc.h>
  5. #include<stdlib.h>
  6. struct node{ //structure of a single node
  7.         int data;
  8.         struct node *link;
  9. }*front,*rear;
  10. typedef struct node node; //typedef
  11. void add(){
  12.         int d;
  13.         node *temp; //var of type node(i.e struct node)
  14.         printf("\nEnter data to add :");
  15.         scanf("%d",&d);
  16.        
  17.         // Alocate sapce for new node
  18.         temp=(node *)malloc(sizeof(node));
  19.         if(temp==NULL){
  20.                 printf("Overflow condition ?? ");
  21.         }
  22.         temp->data=d; //add data to node
  23.         temp->link=NULL;
  24.        
  25.         //if queue is empty
  26.         if(front==NULL ){
  27.                 front=temp;
  28.                 rear=temp;
  29.         }
  30.         else{
  31.                 //if Queue is not empty
  32.                 rear->link=temp;
  33.                 rear=temp;
  34.         }
  35.        
  36. }
  37. void del(){
  38.          //deletion is always from front
  39.          if(front == NULL){
  40.                 printf("\nUnderflow condition .. Queue is empty\n");
  41.          }
  42.          else{
  43.          
  44.          node *temp;
  45.          temp=front; //point to first node
  46.          front=front->link; //now front point 2 second node
  47.          free(temp); //deallocate space of first node
  48.     }
  49. }
  50. void display(){
  51.         node *ptr;
  52.         printf("\n");
  53.         if(front==NULL){
  54.                 printf("\nQUeue is empty\n");
  55.         }
  56.         else{
  57.         ptr=front;
  58.         while(ptr!=NULL){
  59.                 printf(" %d ",ptr->data);
  60.                 ptr=ptr->link;
  61.         }
  62.         printf("\n");
  63.     }
  64. }
  65. main(){
  66.        
  67.         int ch;
  68.        
  69.         front=NULL; //Initiate queue
  70.         rear=NULL;
  71.         while(1){
  72.                 printf(" 1: add data \n 2: delete \n 3 : exit \n  Enter your choice :");
  73.                 scanf("%d",&ch);
  74.                 switch(ch){ //select opearation to done on queue
  75.                         case 1:
  76.                                 add();
  77.                                 display();
  78.                                 break;
  79.                         case 2:
  80.                                 del();
  81.                                 display();
  82.                                 break;
  83.                         case 3:
  84.                                 exit(0);
  85.                                 break;
  86.                         default:
  87.                                 printf("Wrong Choice !! try again");
  88.                                 break;
  89.                 }
  90.         }       
  91. }

Output :
queue implementation in one way link list c Program

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets