Question

Describe in pseudo-code a linear-time algorithm for reversing a queue Q. To access the queue, you are only allowed to use the methods of a queue ADT. Hint: Consider using an auxiliary data structure.

Answer 1

PSEUDOCODE/ALGORITHM

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 code:

// CPP program to reverse a Queue
#include <bits/stdc++.h>
using namespace std;

// Utility function to print the queue
void Print(queue<int>& Queue)
{
   while (!Queue.empty()) {
       cout << Queue.front() << " ";
       Queue.pop();
   }
}

// Function to reverse the queue
void reverseQueue(queue<int>& Queue)
{
   stack<int> Stack;
   while (!Queue.empty()) {
       Stack.push(Queue.front());
       Queue.pop();
   }
   while (!Stack.empty()) {
       Queue.push(Stack.top());
       Stack.pop();
   }
}

// Driver code
int main()
{
   queue<int> Queue;
   Queue.push(10);
   Queue.push(20);
   Queue.push(30);
   Queue.push(40);
   Queue.push(50);
   Queue.push(60);
   Queue.push(70);
   Queue.push(80);
   Queue.push(90);
   Queue.push(100);

   reverseQueue(Queue);
   Print(Queue);
}

Time complexity: O(n) where n is the number of elements in the queue