Program to implement Queues using two stacks

Lets learn the concept of Queues and Stacks first.

Stack : Stack uses LIFO principle that is the element which entered stack last will pop first.

Queue : Queue uses FIFO principle that is the element which is added first will get out first.

Now the logic for the above program is very simple.You can understand it by thinking about two stacks we are using togather.

 We going to try to apply FIFO principle to the elements we are entering in stacks.But we know that the element which entered in first will pop at last in stacks.So how we going to do it ??

Its Simple !!!

Just take one stack lets say Stack1 put all the elements in it.And now take other stack which we will be calling as stack2 and pop each element from stack1 and push that element in stack2.Repeat this process untill the stack1 is empty.

Now the next step is to just pop each element from stack2.Thus you can see that the element which entered first gets out first which is nothing but FIFO principle used in Queue.Thus we implemented Queue.

Now algorithm for the above program will be :

Enqueue(Q,x)

Push x in stack1 untill you reach the top of the stack1.

Dequeue(Q)

If both stacks are empty then return.
If stack2 is empty
while stack1 is not empty push everything from stack1 to stack2.
Pop the element from stack2 and return it.

Program :

Struct node
{
int data;
node *next;
};
struct queue
{
node *stack1;
node *stack2;
};
void push(node **node_top,int value)
{
struct node *node1=(struct node*)malloc(sizeof(node));
if(node1==NULL)
{
printf("Stack Overflow");
}
node1->data=value;
node1->next=*node_top;
*node_top=node1;
}
void pop(node *node_top)
{
int result;
node *t;

if(node1==NULL)
{
printf("Stack Overflow");
}
else
{
t=node_top;
result=t->data;
*node_top=t->next;
free(t);
return result;
}

}
void enqueue(queue *q,int x)
{
push(&q->next,x);
}
int dequeue(queue *q)
{
int x;
if(q->stack1==NULL && q->stack2==NULL)
printf("Queue is empty");
if(q->stack2==NULL)
{
while(q->stack1!=NULL)
{
x=pop(&q->stack1);
push(&q->stack2,x);
}
x=pop(&q->stack2);
return x;
}

}