Implement Queue using Stacks

enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.

CODE

struct queue
{
  struct sNode *stack1;
};

/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
   push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x; 
  
   /* If both stacks are empty then error */
   if(q->stack1 == NULL && q->stack2 == NULL)
   {
      printf("Q is empty");
      getchar();
      exit(0);
   }
 
   /* Move elements from satck1 to stack 2 only if stack2 is empty */
   if(q->stack2 == NULL)
   {
     while(q->stack1 != NULL)
     {
        x = pop(&q->stack1);
        push(&q->stack2, x);
     }
   } 
 
   x = pop(&q->stack2);
   return x;
}

Queue can also be implemented using one user stack and one Function Call Stack (Recursion).
enQueue(x)
1) Push x to stack1.

deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item in a variable res,  push the res back to stack1 and return res

struct queue
{
  struct sNode *stack1;
};

void enQueue(struct queue *q, int x)
{
  push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x, res; 
  
   if(q->stack1 == NULL)
   {
     printf("Q is empty");
     getchar();
     exit(0);
   }
   else if(q->stack1->next == NULL)
   {
      return pop(&q->stack1);
   }
   else
   {
      /* pop an item from the stack1 */
      x = pop(&q->stack1);
  
      /* store the last dequeued item */
      res = deQueue(q);
  
      /* push everything back to stack1 */
      push(&q->stack1, x);
  
      return res;
   }
}