Stack Using Queue

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.
*/