Queue Using Stack

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