How will you reverse a queue?

2.9K

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"); }