Python,C,C++ and JAVA programs for CBSE, ISC, B.Tech and I.T Computer Science and MCA students

The Programming Project: March 2013

Friday, March 29, 2013

C Program #19


/* 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;
            }