/* Dynamic Implementation
of queue and few basic operations!*/
#include<stdio.h>
#include<stdlib.h>
#define
MAXSIZE 100
#define
TRUE 1
#define
FALSE 0
struct
queue{
int
items;
struct
queue *next;
};
typedef
struct queue node;
struct
stack{
int top;
int items[MAXSIZE];
};
struct
stack stk;
struct
queue p,q,temp;
int
pop(struct stack *);
int
remove(node **);
int
Isempty(node *);
void
push(struct stack *,int);
int
isempty_st(struct stack *);
void
insert(node *,int);
void
reverse_queue(node **);
void
display_front_rear(node **);
void
display_rear_front(node **);
void
append(node *,node *);
void
replace(node**,int,int,node **);
void
display_front_rear_unchanged(node **,node **);
void
display_rear_front_unchanged(node **,node **);
int
Isequal(node **,node**,node**,node**);
int
main()
{
int choice,x,ins,e;
stk.top=-1;
node *rootp,*rootq,*tqueue,*rqueue;
rootp=(node *)malloc(sizeof(node));
rootp->next=NULL;
rootq=(node *)malloc(sizeof(node));
rootq->next=NULL;
tqueue=(node *)malloc(sizeof(node));
tqueue->next=NULL;
rqueue=(node *)malloc(sizeof(node));
rqueue->next=NULL;
do
{
printf("\n Press 1
to add elements in Queue:");
printf("\n Press 2
to remove elements from Queue:");
printf("\n Press 3
to append queue Q at the end of queue P:");
printf("\n Press 4
to print elements of queue P from front to end with P becoming empty:");
printf("\n Press 5
to print elements of queue P from rear to front with P becoming empty:");
printf("\n Press 6
to print elements of queue P from front to end with P remaining same:");
printf("\n Press 7
to print elements of queue P from rear to front with P remaining same:");
printf("\n Press 8
to reverse the queue P:");
printf("\n Press 9
to replace a specific element of a queue:");
printf("\n Press 10 to check whether
the queues P and Q are equal or not:");
printf("\n Type 11
to exit:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n
Enter 1 to insert in queue P, 2 to insert in queue Q:");
scanf("%d",&x);
switch(x)
{
case
1:
printf("\n
Enter the element to be inserted:");
scanf("%d",&ins);
insert(rootp,ins);
break;
case
2:
printf("\n
Enter the element to be inserted:");
scanf("%d",&ins);
insert(rootq,ins);
break;
}
break;
case 2:
printf("\n
Enter 1 to remove in queue P, 2 to remove in queue Q:");
scanf("%d",&x);
switch(x)
{
case
1:
e=remove(&rootp);
//if(e=-9999)
// {}
// else
printf("\n
Element removed is:%d\n",e);
break;
case
2:
e=remove(&rootq);
//if(e=-9999)
// {}
//else
printf("\n
Element removed is: %d\n",e);
break;
}
break;
case 3:
append(rootp,rootq);
break;
case 4:
display_front_rear(&rootp);
break;
case 5:
display_rear_front(&rootp);
break;
case 6:
display_front_rear_unchanged(&rootp,&tqueue);
break;
case 7:
case 8:
reverse_queue(&rootp);
break;
display_rear_front_unchanged(&rootp,&tqueue);
break;
case 9:
printf("\n
Enter the element to be replaced:");
scanf("%d",&e);
printf("\n
Enter the element to be placed:");
scanf("%d",&x);
replace(&rootp,e,x,&tqueue);
break;
case 10:
if(Isequal(&rootp,&rootq,&tqueue,&rqueue))
printf("\n
Queues are equal:\n");
else
printf("\n
Queues are not equal:\n");
break;
}
}while(choice>=1
&& choice<=10);
return
0;
}
int
Isequal(node **qp,node **qq,node **t1,node **t2)
{
int FLAG=TRUE,s1=0,s2=0,x,y;
if((Isempty(*qp) &&
!Isempty(*qq)) ||(!Isempty(*qp) && Isempty(*qq)))
return (FALSE);
else if(Isempty(*qp) &&
Isempty(*qq))
return (TRUE);
else
{
while(!Isempty(*qp))
{insert(*t1,remove(qp));
s1++;}
while(!Isempty(*qq))
{insert(*t2,remove(qq));
s2++;}
if(s1!=s2)
return
(FALSE);
else
{
while(!Isempty(*t1))
{
x=remove(t1);
y=remove(t2);
if(x!=y)
FLAG=FALSE;
insert(*qp,x);
insert(*qq,y);
}
}
if(FLAG==TRUE)
return
(TRUE);
else
return
(FALSE);
}
}
void
replace(node**qp,int e,int x,node **qq)
{
int y;
node *tmp;
tmp=*qp;
printf("\n Elements of the
queue:");
while(!Isempty(*qp))
insert(*qq,remove(qp));
while(!Isempty(*qq))
{
y=remove(qq);
if(y==e)
{
printf("%d
",x);
insert(tmp,x);
}
else
{
insert(tmp,y);
printf("%d
",y);
}
}
printf("\n");
}
void
display_rear_front_unchanged(node **qp,node **qq)
{
int x;
printf("\n Elements of the
queue:");
while(!Isempty(*qp))
{
x=remove(qp);
push(&stk,x);
insert(*qq,x);
}
while(!isempty_st(&stk))
{
printf("%d
",pop(&stk));
insert(*qq,remove(qq));
}
printf("\n");
}
void
display_front_rear_unchanged(node **qp,node **qq)
{
int x;
node *tmp;
tmp=*qp;
printf("\n Elements of the
queue:");
while(!Isempty(*qp))
insert(*qq,remove(qp));
while(!Isempty(*qq))
{
x=remove(qq);
printf("%d
",x);
insert(tmp,x);
}
printf("\n");
}
void
reverse_queue(node **use)
{
node *curr,*prev;
prev=(node *)malloc(sizeof(node));
prev->next=NULL;
curr=*use;
while((*use)->next!=NULL)
{
curr=*use;
*use=(*use)->next;
curr->next=prev;
prev=curr;
}
*use=curr;
}
void
display_rear_front(node **use)
{
printf("\n Elements of the
queue:");
while(!Isempty(*use))
push(&stk,remove(use));
while(!isempty_st(&stk))
printf("%d
",pop(&stk));
printf("\n");
}
void
display_front_rear(node **use)
{
printf("\n Elements of the
queue:");
while(!Isempty(*use))
printf("%d
",remove(use));
printf("\n");
}
void
append(node *p,node *q)
{
while(p->next->next!=NULL)
p=p->next;
p->next=q;
}
int
Isempty(node *use)
{
return ((use->next==NULL)? TRUE :
FALSE);
}
int
remove(node **use)
{
if(Isempty(*use))
{printf("\n Queue
is empty:\n");
return (-9999);}
else{
node *temp,*tp;
temp=*use;
tp=temp;
temp=temp->next;
*use=temp;
return(tp->items);
free(tp);}
}
void
insert(node *use,int x)
{
node *p;
while(use->next!=NULL)
use=use->next;
use->items=x;
p=(node *)malloc(sizeof(node));
use->next=p;
p->next=NULL;
}
int
isempty_st(struct stack *stk)
{
return((stk->top==-1)?TRUE:FALSE);
}
int
pop(struct stack *stk)
{
return(stk->items[(stk->top)--]);
}
void
push(struct stack *stk,int x)
{
stk->items[++stk->top]=x;
}
No comments:
Post a Comment