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

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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