Question

Give an algorithm for reversing a queue Q. Only following standard operations are allowed on queue. 1. enqueue(x) : Add an item x to rear of queue. 2. dequeue() : Remove an item from front of queue. 3. empty() : Checks if a queue is empty or not.. (Hint: you can use LinkedList, Stacks, and Queues from the java data collection)

OUTPUT Examples: Input : Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] Output :Q = [100, 90, 80, 70, 60, 50, 40, 30, 20, 10] Input :[1, 2, 3, 4, 5] Output :[5, 4, 3, 2, 1]

Answer 1

The algorithm for Reversing a queue Q is as follows:

// function to reverse

function reverse_queue (queue)
while queue is not empty
stack.push( front element of queue)
queue.pop()
while stack is not empty
queue.push( stack top element)
stack.pop()

function Print(queue)
while ( queue is not empty)
print queue.front()
queue.pop

// The above two functions can be used to do the following tasks.

Implementation example using C++ language.

void reverse_Queue(queue<int>& Q)
{
stack<int> Stack;
while (!Q.empty()) {
Stack.push(Q.front());
Q.pop();
}
while (!Stack.empty()) {
Q.push(Stack.top());
Stack.pop();
}
}   
void Print(queue<int>& Q)
{
while (!Q.empty()) {
cout << Q.front() << " ";
Q.pop();
}
}
int main()
{
queue<int> Q;
Q.push(10);
Q.push(20);
Q.push(30);
Q.push(40);
Q.push(50);
Q.push(60);
Q.push(70);
Q.push(80);
Q.push(90);
Q.push(100);
reverse_Queue(Q);
Print(Q);
}

Code for JAVA language

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
// you can also use java.util.*; for all imports directly
  
public class Queue_Reverse {
static Queue<Integer> que;
// Function to reverse
static void reverse_queue()
{
Stack<Integer> stack = new Stack<>();
while (!que.isEmpty()) {
stack.add(que.peek());
que.remove();
}
while (!stack.isEmpty()) {
que.add(stack.peek());
stack.pop();
}
}
// Function to print
static void Print()
{
while (!que.isEmpty()) {
System.out.print( que.peek() + ", ");
que.remove();
}
}
//main Function
public static void main(String args[])
{
que = new LinkedList<Integer>();
que.add(10);
que.add(20);
que.add(30);
que.add(40);
que.add(50);
que.add(60);
que.add(70);
que.add(80);
que.add(90);
que.add(100);
reverse_queue();
Print();
}
}

NOTE : It will generate you the same Output as Above shown.

100 90 80 70 60 50 40 30 20 10 ... Program finished with exit code o Press ENTER to exit console.