Let Q be a nonempty queue and let S be an empty stack Using

Let Q be a non-empty queue, and let S be an empty stack. Using only fc Stack and queue ADT functions and a single element variable X. write as algorithm to reverse the order of the elements in Q.

Solution

Hi,

Stack and queues are the most used datastructures. The abstruct data type functions of queue are DEQUEUE and ENQUEUE where we will insert and delete the elements of queue same as a Stack will be having PUSH and POP methods

so a queue is FCFS and a stack is a LCFS,to reverse a queue we can just enqueue all the elements of a queue push into a stack there the elements will be coming in reverse order while we pop from stack. we will just pop all the elements from the temporary stack and we will enque them again to our original queue

Here\'s the algorithm for the same, ADT style

QUEUE *reverseQueue (QUEUE *Q) {
//intialize a stack and node x
STACK *S;
QUEUE_NODE *X;

//Check for empty queue
if(emptyQueue(Q))
return NULL;

//Check for single node queue
if(queueCount(Q) == 1)
return Q;

S = createStack();   
//Dequeue all the elements from queue and push to the temporary stack
while(!emptyQueue(Q))
{ dequeue(Q, &X);
   S.push(X);
}
//pop elements from S and enQueue again Q
while (!S.isEmpty( ))
{
enqueue(Q, S.top());
S.pop();
}
//finally print queue elements in reverse order
destroyStack(S);
return Q;
}