#include<conio.h>
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}node;
typedef struct Q
{
node *R,*F;
}Q;
void initialise(Q *);
int empty(Q *);
int full(Q *);
void enqueueR(Q *,int);//insert at the rear end
void enqueueF(Q *,int);//insert at the front end
int dequeueF(Q *);//Delete the front element
int dequeueR(Q *);//Delete the rear element
void print(Q *);
void main()
{
Q q;
int x,i,op;
initialise(&q);
clrscr();
do
{
printf("\n\n1)Insert(Rear)\n2)Insert(Front)");
printf("\n3)Delete(Front)\n4)Delete(Rear)\n5)Print\n6)Quit");
printf("\nEnter Your Choice:");
scanf("%d",&op);
switch(op)
{
case 1: printf("\n Enter a value:");
scanf("%d",&x);
enqueueR(&q,x);
break;
case 2: printf("\n Enter a value:");
scanf("%d",&x);
enqueueF(&q,x);
break;
case 3: if(!empty(&q))
{
x=dequeueF(&q);
printf("\Deleted Data=%d",x);
}
else
printf("\nQueue is empty !!!!");
break;
case 4: if(!empty(&q))
{
x=dequeueR(&q);
printf("\Deleted Data=%d",x);
}
else
printf("\nQueue is empty !!!!");
break;
case 5: print(&q);break;
}
}while(op!=6);
}
void initialise(Q *qp)
{
qp->R=NULL;
qp->F=NULL;
}
void enqueueR(Q *qp,int x)
{
node *p;
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(empty(qp))
{
qp->R=p;
qp->F=p;
}
else
{
qp->R->next=p;
qp->R=p;
}
}
void enqueueF(Q *qp,int x)
{
node *p;
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(empty(qp))
{
qp->R=p;
qp->F=p;
}
else
{
p->next=qp->F;
qp->F=p;
}
}
int dequeueF(Q *qp)
{
int x;
node *p;
p=qp->F;
x=p->data;
if(qp->F==qp->R) //deleting the last element
initialise(qp);
else
qp->F=p->next;
free(p);
return(x);
}
int dequeueR(Q *qp)
{
int x;
node *p,*q;
p=qp->R;
x=p->data;
if(qp->F==qp->R) //deleting the last element
initialise(qp);
else
{ //locate the predecessor of rear node
q=qp->F;
while(q->next != qp->R)
q=q->next;
q->next=NULL;
qp->R=q;
}
free(p);
return(x);
}
void print(Q *qp)
{
int i;
node *p;
p=qp->F;
printf("\n");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
int empty(Q *qp)
{
if(qp->R==NULL)
return 1;
return 0;
}
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}node;
typedef struct Q
{
node *R,*F;
}Q;
void initialise(Q *);
int empty(Q *);
int full(Q *);
void enqueueR(Q *,int);//insert at the rear end
void enqueueF(Q *,int);//insert at the front end
int dequeueF(Q *);//Delete the front element
int dequeueR(Q *);//Delete the rear element
void print(Q *);
void main()
{
Q q;
int x,i,op;
initialise(&q);
clrscr();
do
{
printf("\n\n1)Insert(Rear)\n2)Insert(Front)");
printf("\n3)Delete(Front)\n4)Delete(Rear)\n5)Print\n6)Quit");
printf("\nEnter Your Choice:");
scanf("%d",&op);
switch(op)
{
case 1: printf("\n Enter a value:");
scanf("%d",&x);
enqueueR(&q,x);
break;
case 2: printf("\n Enter a value:");
scanf("%d",&x);
enqueueF(&q,x);
break;
case 3: if(!empty(&q))
{
x=dequeueF(&q);
printf("\Deleted Data=%d",x);
}
else
printf("\nQueue is empty !!!!");
break;
case 4: if(!empty(&q))
{
x=dequeueR(&q);
printf("\Deleted Data=%d",x);
}
else
printf("\nQueue is empty !!!!");
break;
case 5: print(&q);break;
}
}while(op!=6);
}
void initialise(Q *qp)
{
qp->R=NULL;
qp->F=NULL;
}
void enqueueR(Q *qp,int x)
{
node *p;
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(empty(qp))
{
qp->R=p;
qp->F=p;
}
else
{
qp->R->next=p;
qp->R=p;
}
}
void enqueueF(Q *qp,int x)
{
node *p;
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(empty(qp))
{
qp->R=p;
qp->F=p;
}
else
{
p->next=qp->F;
qp->F=p;
}
}
int dequeueF(Q *qp)
{
int x;
node *p;
p=qp->F;
x=p->data;
if(qp->F==qp->R) //deleting the last element
initialise(qp);
else
qp->F=p->next;
free(p);
return(x);
}
int dequeueR(Q *qp)
{
int x;
node *p,*q;
p=qp->R;
x=p->data;
if(qp->F==qp->R) //deleting the last element
initialise(qp);
else
{ //locate the predecessor of rear node
q=qp->F;
while(q->next != qp->R)
q=q->next;
q->next=NULL;
qp->R=q;
}
free(p);
return(x);
}
void print(Q *qp)
{
int i;
node *p;
p=qp->F;
printf("\n");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
int empty(Q *qp)
{
if(qp->R==NULL)
return 1;
return 0;
}
3 Comments
Q q;
ReplyDeleteinitialise(&q);
how to do this in class....
thank you so much!! this is the best code i have found so far :D
ReplyDeleteThese are technically incorrect since you violate the contract of the interface. This gives performance in linear time for dequeueRear. It should be O(1).
ReplyDelete