How will you reverse a queue?

Question:
Give an algorithm to reverse a queue. You can only use generic functions of the Queue ADT.

Input:
4, 8, 15, 16, 23, 42

Output:
42,23,16,15,8,4

To solve this question will take the help of an auxiliary stack. The steps involved will be:-

• Create an auxiliary stack S.
• Until the queue Q is not empty, push the elements of the queue, in the stack S.
• Now we have a stack in which the last element of the Queue is at the TOP.
• Until the stack is empty POP(S) and enQueue it in the empty Queue.

Here is the implementation of the above algorithm.

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

struct node
{
	int data;
	struct node * next;
};

struct queue
{
	struct node * front;
	struct node * rear;
};

struct stackNode
{
    int data;
    struct stackNode * next;
};

struct stackNode * push(struct stackNode * top, int element);
struct queue * enQueue(struct queue * q, int num);
int deQueue(struct queue ** q);
int pop(struct stackNode ** s);

int main(void)
{
	struct queue * Q = NULL;

	//adding some elements
	Q = enQueue(Q,4);
	Q = enQueue(Q,8);
	Q = enQueue(Q,15);
	Q = enQueue(Q,16);
	Q = enQueue(Q,23);
	Q = enQueue(Q,42);

	//A queue is created
	//FRONT 4 -> 8 -> 15 -> 16 -> 23 -> 42 REAR
	printer(Q);

	//creating an auxiliary stack
	struct stackNode * S = NULL;

	while(Q->front != NULL)
		S = push(S, deQueue(&Q));

	//Now our stack is created
	//TOP 42 -> 23 -> 16 -> 15 -> 8 -> 4

	//Time to re-insert the elements
	Q = NULL;
	while(S != NULL)
		Q = enQueue(Q, pop(&S));

	//Now our queue is created
	//FRONT 42 -> 23 -> 16 -> 15 -> 8 -> 4 REAR
	printer(Q);

	return 0;
}

//All the helper functions
struct stackNode * push(struct stackNode * top, int element)
{
    struct stackNode * temp = (struct stackNode *)malloc(sizeof(struct stackNode));
	if(!temp)
	{
		printf("STACK OVERFLOW");
		return top;
	}
    temp -> data = element;
    temp -> next = top;
    return temp;
}

struct queue * enQueue(struct queue * q, int num)
{
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = num;
	temp -> next = NULL;
	if(q==NULL)
	{
		q = (struct queue*)malloc(sizeof(struct queue));
		if(!q)
		{
			printf("OVERFLOW EXCEPTION");
			return NULL;
		}
		q -> front = temp;
	}
	else
		q -> rear -> next = temp;
	q -> rear = temp;
	return q;
}

int deQueue(struct queue ** q)
{
	int x = (*q)->front->data;
	struct node * temp = (*q)->front;
	(*q) -> front = (*q)->front->next;
	free(temp);
	return x;
}

int pop(struct stackNode ** s)
{
	int x = (*s)->data;
	struct stackNode * temp = *s;
	*s = (*s)->next;
	free(temp);
	return x;
}

void printer(struct queue * q)
{
	struct node * x = q->front;
	while(x != NULL)
	{
		printf("%d ",x->data);
		x = x->next;
	}
	printf("\n");
}