C Program For Prefix Evaluation

Source Code:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define SIZE 20

typedef struct Stack
{
	int a[50];
	int top;
}Stack;

void push(Stack *s, int c)
{
	s->a[++s->top] = c;
}

int pop(Stack *s)
{
	return s->a[s->top--];
}

char* strrev(char str[])
{
	int i, j = 0;
	char o[50];
	for (i = 0; i < strlen(str) ; ++i)
	{
		o[j++] = str[strlen(str) - i - 1] ;
	}
	j = 0;
	for (i = 0; i < strlen(str); ++i)
	{
		str[i] = o[j++];
	}
	str[i] = '\0';
	return str;
}


void evalPrefix(char prefixExp[])
{
	Stack *s = (Stack*)malloc(sizeof(Stack));
	int i, l, r, res;
	s->top = -1;
	strrev(prefixExp);
	for (i = 0; prefixExp[i] != '\0'; i++) {
		if(isdigit(prefixExp[i])) {
			push(s, prefixExp[i] - '0');
		}
		else {
			l = pop(s);
			r = pop(s);
			switch(prefixExp[i]) {
				case '+': push(s, l + r); break;
	            case '-': push(s, l - r); break;
	            case '*': push(s, l * r); break;
	            case '/': push(s, l / r); break;
			}
		}
	}
	res = pop(s);
	printf("Ans: %d.\n",res);
}

int main()
{
	char prefixExp[40];
	
	printf("Enter The Prefix Expression: ");
	scanf("%s",prefixExp);

	evalPrefix(prefixExp);
	return 0;
}

 Algorithm : Checking validity of an Algebric Expression

Let us consider an algebraic expression,A,which contains operands, operators, ’(‘ , ’)’ , 
‘{‘ , ‘}’ , ‘[‘ , ‘]’.This algorithm checks the validity of the expression in algebraic sence,
 i.e for every ‘(‘ there will be a matching ‘)’, for every ‘{‘ there will be a matching ‘}’ 
and for every ‘[‘ there will be a matching ‘]’.

Valid_expression(A[1..N])
{
 
 Let us consider a stack ‘S’ which contains the symbols read from A.
 Push and Pop operation are done on the top of the stack.
 Add ‘$’ to the end of A.
 
 i=0;
 while(A[i]≠'$')                    //until the expression finishes
 {
   if(A[i]='(' or A[i]='{' or A[i]='[')
   {
    push(A[i])
   }
   else if(A[i]=')')
   {
     if(top=-1)                    //checks if the stack is empty
      {
       Print  "Expression invalid"
       exit
      }
     else
      {
       item=pop()
       if(item≠'(')            //checks if there is no matching ‘)’ 
	  {
	   Print  "Expression invalid"
	   exit
	  }
      }
   }

else if(A[i]='}')
    {
     if(top=-1)                     //checks if the stack is empty
      {
       Print  "Expression invalid"
	  exit
      }
     else
      {
       item=pop()
       if(item≠'{')            //checks if there is no matching ‘)’
	{
	 Print  "Expression invalid"
	 exit
	}
      }
    }

    

else if(A[i]=']')
    {
     if(top=-1)                     //checks if the stack is empty
     {
       Print  "Expression invalid"
       exit    
     }
     else
     {
       item=pop()
       if(item≠'[')             //checks if there is no matching ‘)’
	{
	 Print  "Expression invalid"
	 exit
	}
     }
    }
i=i+1
}
  if(top=-1)              //checks if all pairs of bracket is found
  {
   Print  "Valid expression"
  }
  else
  {
   Print  "Expression invalid"
  }
}


 C program For Validity Checking on Expression

Source Code:

 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 #include<string.h>

int top=-1;
char a[10];

void push(char item)
{
 
 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     a[top]=item;
   }
}

char pop()
{
  char item;
  if(top==-1)
   {
     printf("\nStack Underflow");
     item=-1;
   }
  else
   {
     item=a[top];
     top=top-1;
   }
  return item;
}

main()
{
char item,e[15];
int i;
 printf("\nEnter an expression:");
gets(e);
strcat(e,"$");
i=0;
while(e[i]!='$')
{
   if(e[i]=='(' || e[i]=='{' || e[i]=='[')
   {
    push(e[i]);
   }
   else if(e[i]==')')
   {
     if(top==-1)
      {
       printf("\nExpression invalid");
       exit(0);
      }
     else
      {
       item=pop();
       if(item!='(')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
       }
    }

    else if(e[i]=='}')
    {
     if(top==-1)
      {
       printf("\nExpression invalid");
	exit(0);
      }
     else
      {
       item=pop();
       if(item!='{')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
      }
    }

    else if(e[i]==']')
    {
     if(top==-1)
     {
       printf("\nExpression invalid");
       exit(0);
     }
     else
     {
       item=pop();
       if(item!='[')
	{
	 printf("\nExpression invalid");
	 exit(0);
	}
     }
    }
i=i+1;
}
  if(top==-1)
  {
   printf("\n....::.Valid expression.::....");
  }
  else
  {
   printf("\nExpression invalid");
  }
  getch();
}



 OUTPUT 1:
Enter an expression:[{a+f-(b-c}]

Expression invalid.
-----------------------------------
 OUTPUT 2:

Enter an expression:{(a+b)*(c-d)}

....::.Valid expression.::....

Algorithm:Stack using Queue

Let us consider two queue Q1 and Q2 with front f1,f2 respectively
And rear r1,r2 respectively.We have to implement stack(of size of N)
Operations in Q1 using Q2.

Initially,
	  f1=r1=f2=r2=-1;

Push(Q1[1..N],f1,r1,item)
{
  if(r1=N-1)                     //checks if the Queue is full
  {
   print "Queue full"
  }
  else
  {
    r1=r1+1
    Q[r1]=item                  //element is inserted in rear side
    if(f1=-1)                     //if f1 is -1 then f1 is initialized 
    {                                to 0
      f1=0
    }
  }
}

Pop(Q1,Q2,f1,r1,f2,r2)
{
    if(f1=0)                              //checks if Q1 is empty
     {
        print  “stack underflow”
     }
     else
     {
        while(Q1≠empty)          //until Q1 is empty an element is 
         {                         deleted from Q1 and inserted into 
            item=Qdelete(Q1)       Q2 repeatedly
            Qinsert(Q2,item)
         }
        while(Q2 contains more than 1 item)     //after that each 
         {                                        element  is deleted                                                        
            item=Qdelete(Q2)                      from Q2 and inserted        
            Qinsert(Q1,item)                      into Q1
         }
        Qdelete(Q2)                   //at last the remaining element
     }                                  in Q2 is deleted
}



C Program for Stack Using Queue

Source Code:

#include<stdio.h>
#include<stdlib.h>

int Q1[5],f1=-1,r1=-1,Q2[5],f2=-1,r2=-1;

void push(int item)
{
 if(r1==4)
 {
  printf("\nStack overflow.");
 }
 else
 {
  r1=r1+1;
  Q1[r1]=item;
  if(f1==-1)
  {
   f1=0;
  }
 }
}

void Q1insert(int item)
{
 if(r1==4)
 {
  printf("\nStack overflow.");
 }
 else
 {
  r1=r1+1;
  Q1[r1]=item;
  if(f1==-1)
  {
   f1=0;
  }
 }
}

int Q1delete()
{
 int item;
 if(f1==-1)
 {
  printf("\nStack underflow.");
 }
 else
 {
   item=Q1[f1];
  if(f1==r1)
  {
   f1=-1;
   r1=-1;
  }
  else
  {
  f1=f1+1;
  }
 }
 return item;
}

void Q2insert(int item)
{
 if(r2==4)
 {
  printf("\nStackm overflow.");
 }
 else
 {
  r2=r2+1;
  Q2[r2]=item;
  if(f2==-1)
  {
   f2=0;
  }
 }
}

int Q2delete()
{
 int item;
 if(f2==-1)
 {
  printf("\nStack underflow.");
 }
 else
 {
   item=Q2[f2];
  if(f2==r2)
  {
   f2=-1;
   r2=-1;
  }
  else
  {
  f2=f2+1;
  }
 }
 return item;
}

int pop()
{
 int b,c,item;
 if(f1==-1)
 {
   printf("\nStack underflow.");
 }
 else
 {
   while(f1!=-1)
   {
    item=Q1delete();
    Q2insert(item);
   }

   while(f2!=r2)
   {
    item=Q2delete();
    Q1insert(item);
   }
   item=Q2delete();
 }
 return item;
}

void show()
{
 int i=0;
 printf("\nThe elements of the stack are:");
 for(i=0;i<=4;i++)
 {
  if(i>=f1 && i<=r1)
  printf("\t%d",Q1[i]);
  else
  printf("  _");
 }
 printf("\n");
}

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

     case 4:
	    exit(0);

   }
 }
}

/*
 OUTPUT :
 
1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:11

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:22

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:33

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:44

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:55

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:3

The elements of the stack are:  11      22      33      44      55

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:66

Stack overflow.

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:1

Enter item:66

Stack overflow.
1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:3

The elements of the stack are:  11      22      33  _  _

  1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

1.Push  2.Pop  3.Show  4.Exit
Enter your choice:2

Stack underflow.
*/

Algorithm : Queue using Stack

Let us consider two stacks S1 and S2 with tops t1 and t2 respectively.
N is the size of S1 and S2.We have to implement Queue operations in stack
S1 using the stack S2.

Initially,
          t1=t2=-1.
Insert(S1,t1,item)
{                                //checks if S1 becomes full
if(t1=N)                                                      
	print "Queue Full"
else
	{
	t1=t1+1;
	S1[t1]=item
	}
}

Delete(S1,t1)
{

if(t1=-1)                         //checks if S1 is empty
	{
	print "Queue Empty"
	}
else
	{
	t2=-1;
	while(t1≠-1)                 //until S1 becomes empty
		{
		t2=t2+1                //pop an item from S1
		S2[t2]=S1[t1]          //push that item on S2
		t1=t2-1
		}
	t2=t2-1                     //pop an item from S2

	while(t2≠-1)                //until S2 becomes empty
		{
		t1=t2+1                //pop an item from S2
		S1[t1]=S2[t2]          //push it to S1
		t2=t2-1
		}
	}

}


                               
   
C Program For Queue Using Stack

Source Code:

#include<stdio.h>
#include<stdlib.h>

int t1=-1,t2=-1,s1[10],s2[10];
void insert(int item)
{
 if(t1==9)
   {
     printf("\nQueue full");
   }
 else
   {
     t1=t1+1;
     s1[t1]=item;
   }
}

int delete()
{
  int item;
  if(t1==-1)
   {
     printf("\nQueue empty");
     item=-1;
   }
  else
   {
    t2=-1;
     while(t1!=-1)
     {
      t2=t2+1;
      s2[t2]=s1[t1];
      t1=t1-1;
     }
    t2=t2-1;
    while(t2!=-1)
    {
     t1=t1+1;
     s1[t1]=s2[t2];
     t2=t2-1;
    }
   }
  return item;
}

void show()
{
  int i;
  if(t1==-1)
   {
     printf("\nQueue is empty");
   }
  else
   {
     i=0;
     while(i<=t1)
      {
	printf("  %d",s1[i]);
	i=i+1;
      }
   }
}

main()
{
 int item,ch;
 while(1)
  {
    printf("\nperform queue operation using stack..");
    printf("\n1.Insert  2.Delete  3.Show  4.Exit");
    printf("\nEnter your choice:");
    scanf("%d",&ch);
     switch(ch)
      {
	 case 1:
		printf("\nEnter an item:");
		scanf("%d",&item);
		insert(item);
		break;
	 case 2:
		item=delete();
		printf("\nThe popped item is :%d",item);
		 break;
	 case 3:
		show();
		break;
	 case 4:
		exit(0);
       }
    }
}



 OUTPUT :
 
perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:1

Enter an item:11

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:1

Enter an item:22

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:1

Enter an item:33

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:1

Enter an item:44

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:1

Enter an item:55

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:3
  11  22  33  44  55

1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:3
  33  44  55
perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

perform queue operation using stack..
1.Insert  2.Delete  3.Show  4.Exit
Enter your choice:2

Queue empty

 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.

  

Algorithm : Priority  Queue  Operations

Let us consider a queue structure,”PQ” of size N,with front and rear called Priority  Queue
which has two part-i)element part and ii)priority part.Here,each element in the queue is
assigned a value called priority of that element,and an element can be inserted not only
the ends but at any position of that queue maintaining the priority.
This algorithm helps to perform Priority Queue operations.

PQinsert(PQ)
{
 if(rear=N)           //checks if rear reaches to the last position
 {
  Printf  "Queue full"
 }
 else
 {
  rear=rear+1                    //rear is incremented by 1
  Q[rear].element=PQ.element
  Q[rear].pr=PQ.pr
  if(front=-1)         //if no elements in PQ is inserted then front
  {                      and rear both are initialized to 0
   front=rear=0
  }
 }
                       Sort elements of “PQ” in descending order of their priority.
}

PQdelete(PQ)
{
 if(front=-1)              //checks if there is no element in PQ
 {
  Printf  "Queue empty"
 }
 else
 {
   PQ.element=Q[front].element
   PQ.pr=Q[front].pr
  if(front=rear)       //if there is only 1 element in PQ then front
  {                      and rear both are initialized to -1
   front=rear=-1
  }
  else
  {
   front=front+1           //front is incremented by 1
  }
 }
 return PQ
}

C Program For priority queue

Source Code:


#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct queue
{
 int element;
 int pr;
};

struct queue Q[5];

int f=-1,r=-1;

void PQinsert(struct queue PQ)
{
 int i,j,x,y;
 if(r==4)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=r+1;
  Q[r].element=PQ.element;
  Q[r].pr=PQ.pr;
  if(f==-1)
  {
   f=0;
   r=0;
  }
 }
  for(i=f;i<=r-1;i++)
  {
   for(j=i+1;j<=r;j++)
   {
       if(Q[i].pr>Q[j].pr)
       {
	  x=Q[i].element;
	  y=Q[i].pr;
	  Q[i].element=Q[j].element;
	  Q[i].pr=Q[j].pr;
	  Q[j].element=x;
	  Q[j].pr=y;
       }
    }
  }
}

struct queue PQdelete()
{
 int k,i,j,s,m;
 struct queue PQ;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   PQ.element=Q[f].element;
   PQ.pr=Q[f].pr;
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
   f=f+1;
  }
 }
 return PQ;
}

void show()
{
 int i=0;
 if(f==-1)
 {
   printf("\nQueue empty.");
 }
 else
 {
 printf("\nThe elements of the Queue are:");
  for(i=0;i<=4;i++)
  {
   if(i>=f && i<=r)
     printf("  %d(p->%d)",Q[i].element,Q[i].pr);
   else
     printf("  _");
  }
  printf("\n");
 }
}

void main()
{
 int ch;
 struct queue PQ;
 while(1)
 {
   printf("\n1.PQinsert  2.PQdelete  3.Show  4.Exit");
   printf("\nEnter your choice:");
   scanf("%d",&ch);
   switch(ch)
   {
     case 1:
	    printf("\nEnter element and priority:");
	    scanf("%d,%d",&PQ.element,&PQ.pr);
	    PQinsert(PQ);
	    break;
     case 2:
	    PQ=PQdelete();
	    if(f!=-1)
	    {
	    printf("\nThe popped item is->  %d(p->%d)\n",PQ.element,PQ.pr);
	    }
	    break;
     case 3:
	    show();
	    break;
    
     case 4:
	    exit(0);

   }
 }
}



 OUTPUT :
 1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:22,4

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:12,1

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  22(p->4)  _  _  _

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:45,3

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:67,2

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  67(p->2)  45(p->3)  22(p->4)  _

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:66,5

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  12(p->1)  67(p->2)  45(p->3)  22(p->4)  66(p->5)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:1

Enter element and priority:99,6

Queue full.

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  12(p->1)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  67(p->2)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  _  _  45(p->3)  22(p->4)  66(p->5)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  45(p->3)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is->  22(p->4)

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

1.PQinsert  2.PQdelete  3.Show  4.Exit
Enter your choice:2

Queue empty.

Algorithm:Linear Queue Operations

Let us consider a linear queue,Q with front side and rear side.
Element will be inserted in rear side and will be deleted from
front side.This algorithm helps us to perform insertion and
deletion operation in the queue,Q.

Initially,
	  front=rear=-1;

Qinsert(Q[1..N),front,rear,item)
{
  if(rear=N-1)                     //checks if the Queue is full
  {
   print "Queue full"
  }
  else
  {
    rear=rear+1                   //rear is incremented by 1
    Q[rear]=item                  //element is inserted in rear side
    if(front=-1)
    {
      front=0
    }
  }
}

Qdelete(Q[1..N),front,rear)
{
 if(front=-1  and  rear=-1)         //checks if the Queue is empty
 {
  print "Queue empty"
 }
 else
 {
   item=Q[front]                  
   if(front=rear)              //if front and rear is equal then they 
   {                             both are initialized to -1
     front=-1
     rear=-1
   }
   else
   {
     front=front+1              //front is incremented and the element 
   }                              in front is deleted
 }
 return item
}



show(Q[1..N),front,rear)
{
  if(front=-1  and  rear=-1)       //checks if the Queue is empty
  {
    print "Queue empty"
  }
  else
  {
    for(i=front  to  rear)
    {
      print "Q[i]"              //elements are printed one by one from 
    }                             front to rear
  }
}




C Program For Linear Queue

Source Code:

#include<tdio.h>
#include<stdlib.h>

int Q[5],f=-1,r=-1;
void Qinsert(int item)
{
 if(f==4)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=r+1;
  Q[r]=item;
  if(f==-1)
  {
   f=0;
  }
 }
}

int Qdelete()
{
 int item;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   item=Q[f];
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
  f=f+1;
  }
 }
 return item;
}

void show()
{
 int i=0;
 printf("\nThe elements of the Queue are:");
 for(i=0;i<=4;i++)
 {
  if(i>=f && i<=r)
  printf("\t%d",Q[i]);
  else
  printf("\t_");
 }
 printf("\n");
}

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:
	    printf("\nEnter item:");
	    scanf("%d",&item);
	    Qinsert(item);
	    break;
     case 2:
	    item=Qdelete();
	    printf("\nThe popped item is-> %d",item);
	    break;
     case 3:
	    show();
	    break;
     
     case 4:
	    exit(0);

   }
 }
}


 OUTPUT:

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

Enter item:11

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

Enter item:22

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

Enter item:33

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

Enter item:44

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

The elements of the Queue are:  11      22      33      44      _
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 11
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 22
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  _       _       33      44      _
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 33
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 44
1.Qinsert  2.Qdelete  3.Show  4.Exit
Enter your choice:2

Queue empty.

Algorithm : Deque

Let us consider a double ended Queue,DQ with front and rear.
Insert in the front,delete from the front,insert in the rear,
delete from the rear all these operations are done in DQ.This
algorithm helps us to perform these operations.

Initially,

	  front=-1,rear=-1

Insertrear(DQ[1..N],front,rear,item)
{
  if(front=(rear+1)%N)               //checks if the dequeue is full
  {
    print "Queue frontull."
  }
  else
  {
    rear=(rear+1)%N;
    DQ[rear]=item                   //element is inserted in rear side
    if(front=-1)         //if front is -1 then front is initialized to 0
    {
      front=0
    }
  }
}

Deletefront(DQ[1..N],front,rear)
{
   if(front=-1)                              //checks if dequeue is empty
   {
      print "Queue empty."
   }
   else
   {
      item=DQ[front]
      if(front=rear)            //if front and rear is equal then they
      {                            both are initialized to -1
         front=-1
         rear=-1
      }
      else
      {
         front=(front+1)%N       //front is incremented and the element
      }                             in front deleted
   }
 return item
}




Insertfront(DQ[1..N],front,rear,item)
{
   if(front=0)                  
   {
      next=N-1
      front=next
      DQ[front]=item
   }
   else if(front=-1)               //checks if dequeue is empty
   {
      next=0
      front=next
      DQ[front]=item             //item is inserted in the 1st position
   }
   else
   {
      next=front-1
      if(next=rear)                //checks if next reachs rear
      {
         print " Deque full."
      }
      else
      {
         front=next
         DQ[front]=item
      }
   }
}

Deleterear(DQ[1..N],front,rear)
{
 if(front=-1)                      //checks if the deque is empty
 {
   print " DEQUE empty."
 }
 else
 {
   item=DQ[r]
   if(front=rear)             //checks if there is only 1 element 
   {                            present in the deque
     front=rear=-1      //then front and rear both are initialized to -1 
   }
   else if(rear=0)
     rear=N-1
   else
     rear=rear-1
 }
 return item
}


C Program For Double-ended-queue

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int DQ[5],f=-1,r=-1;

void insertrear(int item)
{
 if(f==(r+1)%5)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=(r+1)%5;
  DQ[r]=item;
  if(f==-1)
  {
   f=0;
  }
 }
}

int deletefront()
{
 int item;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   item=DQ[f];
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
  f=(f+1)%5;
  }
 }
 return item;
}

void insertfront(int item)
{
  int next;
  if(f==0)
  {
   next=4;
   f=next;
   DQ[f]=item;
  }
  else if(f==-1)
  {
    next=0;
    f=next;
    DQ[f]=item;
  }
  else
  {
    next=f-1;
    if(next==r)
    {
     printf("\nDeque full.");
    }
    else
    {
      f=next;
      DQ[f]=item;
    }
  }
}

int deleterear()
{
 int item;
 if(f==-1)
 {
   printf("\nDEQUE empty.");
 }
 else
 {
   item=DQ[r];
   if(f==r)
   {
     f=-1;
     r=-1;
   }
   else if(r==0)
   {
     r=4;
   }
   else
   {
     r=r-1;
   }
 }
 return item;
}

void show()
{
 int i=0;
 if(f==-1 || f==(r+1)%5)
 {
   printf("\nQueue empty.");
 }
 else
 {
 printf("\nThe elements of the Queue are:");
  if(f=f && i<=r)
     printf("\t%d",DQ[i]);
   else
     printf("\t_");
  }
 }
 else if(f==r)
 {
  for(i=0;i<=4;i++)
  {
   if(i==f)
     printf("\t%d",DQ[i]);
   else
     printf("\t_");
   }
  }
 else
 {
 for(i=0;i<=4;i++)
 {
  if(i<=r)
    printf("\t%d",DQ[i]);
  else if(i>r && i %d",item);
	    }
	    break;
     case 3:
	    printf("\nEnter item:");
	    scanf("%d",&item);
	    insertfront(item);
	    break;
     case 4:
	    item=deleterear();
	    if(f!=-1)
	    {
	    printf("\nThe popped item is-> %d",item);
	    }
	    break;
     case 5:
	    show();
	    break;

     case 6:
	    exit(0);

   }
 }
}


 OUTPUT :
 
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:1

Enter item:11

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:1

Enter item:22

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:3

Enter item:55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:3

Enter item:44

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      22      _       44      55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

The popped item is-> 44
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      22      _       _       55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:4

The popped item is-> 22
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      _       _       _       55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:4

The popped item is-> 11
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

Queue empty.

  


Algorithm:Circular Queue Operations


Let us consider a circular queue,CQ with front side and rear side.
Element will be inserted in rear side and will be deleted from front side.
If  rear is in the last position and front is in the middle position and 
there is any space in CQ then the item wlii be inserted in the 1st
position.This algorithm helps us to perform insertion and deletion operation
in the queue,CQ.

Initially,
	  front=rear=-1;

Qinsert(CQ[1..N),front,rear,item)
{
  if(front=(rear+1)%N)                     //checks if the Queue is full
  {
   print "Queue full"
  }
  else
  {
    rear=(rear+1)%N
    CQ[rear]=item                  //element is inserted in rear side
    if(front=-1)                    //if front is -1 then front is 
    {                                 initialized to 0
      front=0
    }
  }
}
	
Qdelete(CQ[1..N),front,rear)
{
 if(front=-1 and rear=-1)         //checks if the Queue is empty
 {
  print "Queue empty"
 }
 else
 {
   item=CQ[front]                  
   if(front=rear)              //if front and rear is equal then they 
   {                             both are initialized to -1
     front=-1
     rear=-1
   }
   else
   {
     front=(front+1)%N          //front is incremented and the element 
   }                              in front deleted
 }
 return item
}



show(CQ[1..N),front,rear)
{
  if(front=-1  and  rear=-1)       //checks if the Queue is empty
  {
    print "Queue empty"
  }
  else
  {
    for(i=front  to  rear)
    {
      print "CQ[i]"              //elements are printed one by one from front to rear
    }
  }
}


C Program For Circular Queue

Source Code:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int Q[5],f=-1,r=-1;
void CQinsert(int item)
{
 if(f==(r+1)%5)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=(r+1)%5;
  Q[r]=item;
  if(f==-1)
  {
   f=0;
  }
 }
}

int CQdelete()
{
 int item;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   item=Q[f];
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
  f=(f+1)%5;
  }
 }
 return item;
}

void show()
{
 int i=0;
 if(f==-1)
 {
   printf("\nQueue empty.");
 }
 else
 {
 printf("\nThe elements of the Queue are:");
  if(f=f && i<=r)
     printf("\t%d",Q[i]);
   else
     printf("\t_");
  }
 }
 else if(f==r)
 {
  for(i=0;i<=4;i++)
  {
   if(i==f)
     printf("\t%d",Q[i]);
   else
     printf("\t_");
   }
  }
 else
 {
 for(i=0;i<=4;i++)
 {
  if(i<=r)
    printf("\t%d",Q[i]);
  else if(i>r && i %d",item);
	    }
	    break;
     case 3:
	    show();
	    break;
     case 4:
	    exit(0);

   }
 }
}


 OUTPUT:
 1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:11

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:22

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:33

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:44

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:55

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  11      22      33      44      55

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:66

Queue full.
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 11
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 22
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 33
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:1

Enter item:77

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:3

The elements of the Queue are:  77      _       _       44      55
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 44
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

The popped item is-> 55
1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:2

1.CQinsert  2.CQdelete  3.Show  4.Exit
Enter your choice:3

Queue empty.

Algorithm : Postfix Evaluation
 
Postfix_Evaluation(P[1,2,...,N],S[1,2,...,N],top)
{
  Let us consider a postfix expression 'P'. We have to evaluate the 
  value of P using a stack,’S’ with top ‘t’ and capable of holding N 
  elements.Push and Pop operation is done on the top of ‘S’.

1. Insert a symbol '$' at the end of P.
2. x=Read a symbol from P
3. while(x≠'$')                       //until it reaches the end of P
   {
   if(x=operand)
	push(x)
   else
	{
	A=pop()                        //2nd operand is popped
	B=pop()                        //1st operand is popped       
	C=B(op)A                       //operation is done b/w A and B      	
        push(C)                        //resultant value is stored into ‘S’
	}
   x=Read a symbol from P
   }
4. Value=pop()
5. print “Value”
6. End
}


C Program For Postfix Evaluation

Source Code:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h%>

float s[10];
int top=-1;



void push(float item)
{

 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     s[top]=(float)item;
   }
}


float pop()
{
  float item=-1;
  if(top==-1)
   {
     printf("\nStack Underflow");

   }
  else
   {
     item=s[top];
     top=top-1;
   }
  return item;
}

void show()
{
int i;
printf("\nStack");
for(i=0;i<=top;i++)
printf("\t%g",s[i]);

}
int isop(char y)
{
  switch(y)
   {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '^':
	      return 1;
	      break;
     case '{':
     case '[':
     case '(':
     case ')':
     case '}':
     case ']':
	      return 2;
	      break;
     default:
	     return 0;
	     break;
   }
}


int pre(char op)
{
  switch(op)
   {
     case '+':
     case '-':
	      return 1;
	      break;
     case '*':
     case '/':
     case '%':
	      return 2;
	      break;
     case '^':
	      return 3;
	      break;
     default:
	     return 0;
	     break;
   }
}

float operation(float b,float a,char z)
{
  switch(z)
   {
     case '+':
	      return b+a;
	      break;
     case '-':
	      return b-a;
	      break;
     case '*':
	      return b*a;
	      break;
     case '/':
	      return (b/a);
	      break;
     case '%':
	      return ((int )b%(int )a);
	      break;
     case '^':
	      return pow(b,a);
	      break;
    }
}

float posteva(char p[10])
{
 int i;
  float val,a,b,c;
 char d[10],y;
 strcpy(d,p);
 strcat(d,"$");
 i=0;
 while(d[i]!='$')
 {
   y=d[i];
   
   if(isop(y)==0)
   {
    push((float)y-'0');
   }
   else
   {
    a=pop();
    b=pop();
    c=operation(b,a,y);
    push(c);
   }
   show();
   i++;
  }
  val=pop();
  return val;
}

void main()
{
  int j,k=0,l,i,w;
  char e[15],p[15],x,y,m;
  float r;
 
  printf("\nEnter an infix expression: ");
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  push(m);
  i=0;
  while(top!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
	 p[k]=x;
	 k=k+1;
       }

      else if(x=='(')
       {
	 push(x);
       }

      else if(x==')')
       {
	 y=pop();
	 while(y!='(')
	  {
	    p[k]=y;
	    k=k+1;
	    y=pop();
	  }
       }

      else if(isop(x)==1)
       {
	 y=pop();
	 while(isop(y)==1 && pre(y)>=pre(x))
	  {
	    p[k]=y;
	    k=k+1;
	    y=pop();
	  }
	 push(y);
	 push(x);
       }
     i++;
   }
  p[k]='\0';
  printf("\nThe postfix expression is :  ");
  puts(p);
  printf("\nDo you want to get its value ?");
  printf("\n 1.Yes  2.No ");
  printf("\nEnter your choice:");
  scanf("%d",&w);
  switch(w)
  {
   case 1:
	 r=posteva(p);
	 printf("\nvalue=%g",r);
	 break;
   case 2:
	  break;
  }

}


 OUTPUT 1:
Enter an infix expression: (4+7)-(5*9)/3

The postfix expression is :  47+59*3/-

Do you want to get its value ?
 1.Yes  2.No
Enter your choice:1

Stack   4
Stack   4       7
Stack   11
Stack   11      5
Stack   11      5       9
Stack   11      45
Stack   11      45      3
Stack   11      15
Stack   -4
value=-4
----------------------------------------

 OUTPUT 2:
The postfix expression is :  65/4-37*+

Do you want to get its value ?
 1.Yes  2.No
Enter your choice:1

Stack   6
Stack   6       5
Stack   1.2
Stack   1.2     4
Stack   -2.8
Stack   -2.8    3
Stack   -2.8    3       7
Stack   -2.8    21
Stack   18.2
value=18.2

Algorithm : Infix to Postfix


Infix_to_Postfix(P[1,2,...,N],S[1,2,...,N],E[1,2,..,N],top)
{
  Let us also consider a infix expression 'E'. We have to convert this
  expression 'E' into postfix expression 'P'.
  A stack 'S' with top ‘t’ of capacity of holding N elements is used to  
  perform the Operation.Push and Pop operation is done on top.

1. Insert a symbol ')' at the end of E.
2. Push the symbol '(' into stack S.
3. while(S≠empty)                        //until S becomes empty 
   {                                                       
   item=read a symbol from E.
   if(item=operand)
 add item at the end of P
   else if(item='(')
 push(item)
   else if(item=')')
 {
 x=pop()
 while(x≠'(')
  {
  add x at the end of P
  x=pop()
  }
 }
   else if(item=operator)
 {
 x=pop()
 while(isop(x)=1 and pre(x)≥pre(item))
  {       
  add x at the end of P
  x=pop()
  }
 push(x)
 push(item)
 }
   }
4. print P
5. End
}


//Here isop() is a function which returns 1 if it gets an operator as argument, else
it returns 0.

//pre() is also a function which returns the precedence value or priority
value of an operator.




C Program For Infix to postfix

Source Code:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

char a[10];
int top=-1;


void push(char item)
{

 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     a[top]=item;
   }
}

char pop()
{
  char item;
  if(top==-1)
   {
     printf("\nStack Underflow");

   }
  else
   {
     item=a[top];
     top=top-1;
   }
  return item;
}

int isop(char y)
{
  switch(y)
   {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '^':
       return 1;
       break;
     case '{':
     case '[':
     case '(':
     case ')':
     case '}':
     case ']':
       return 2;
       break;
     default:
      return 0;
      break;
   }
}

int pre(char op)
{
  switch(op)
   {
     case '+':
     case '-':
       return 1;
       break;
     case '*':
     case '/':
     case '%':
       return 2;
       break;
     case '^':
       return 3;
       break;
     default:
      return 0;
      break;
   }
}

main()
{
  int j,k=0,l,i;
  char e[15],p[15],x,y,m;
  clrscr();
  printf("\nEnter an infix expression: ");
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  push(m);
  i=0;
  while(top!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
  p[k]=x;
  k=k+1;
       }

      else if(x=='(')
       {
  push(x);
       }

      else if(x==')')
       {
  y=pop();
  while(y!='(')
   {
     p[k]=y;
     k=k+1;
     y=pop();
   }
       }

      else if(isop(x)==1)
       {
  y=pop();
  while(isop(y)==1 && pre(y)>=pre(x))
   {
     p[k]=y;
     k=k+1;
     y=pop();
   }
  push(y);
  push(x);
       }
     i++;
   }
  p[k]='\0';
  printf("\nThe postfix expression is :  ");
  puts(p);
  getch();
}




OUTPUT:

Enter an infix expression: (a+b^d)/(e-f)+g

The postfix expression is :  abd^+ef-/g+