Home Misc How will you reverse a queue?

# How will you reverse a queue?

0 comment

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;

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


#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More