Reversing a Queue

Problem Statement: Given a queue with several elements, Your task is to reverse the queue.

Operations allowed on queue data-structure

  1. empty() : Checks if a queue is empty or not.
  2. enqueue(x) : Add an item x to rear of queue.
  3. dequeue() : Remove an item from front of queue.

Examples:

Example 1:
Input: Q = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output: Q = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Explanation: Printing the reverse of the queue.

Example 2:
Input: Q = [10, 20, 30, 40, 50]
Output: Q = [50, 40, 30, 20, 10]
Explanation: Printing the reverse of the queue.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: Our task is to choose such a data structure that can store the data of the queue temporarily Because in this approach we are going to re-insert the elements in the queue so that they would get inserted in reverse order.

We will be requiring the data structure that will support a “LIFO” Principle (i.e Last In First Out).

Using a stack data structure will be a perfect choice according to the above approach

So our approach will be as follows:

  1. Remove all the elements from the queue and push them to a stack data structure.
  2. Pop out all the elements from the stack and push them back to the queue.
  3. The queue is revered.
  4. Print the queue.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

//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();
  }
}

int main() {
  queue < int > Queue;
  Queue.push(1);
  Queue.push(2);
  Queue.push(3);
  Queue.push(4);
  Queue.push(5);
  Queue.push(6);
  Queue.push(7);
  Queue.push(8);
  Queue.push(9);
  Queue.push(10);

  reverseQueue(Queue);
  Print(Queue);
}

Output: 10 9 8 7 6 5 4 3 2 1

Time Complexity: O(N)

Space Complexity (Auxiliary Space): O(N)

Reason: Use of the stack to store the value for reversing

Java Code

import java.util.*;

// Java program to reverse a queue
public class TUF {

  static Queue < Integer > queue;

  //function to print the queue
  static void Print() {
    while (!queue.isEmpty()) {
      System.out.print(queue.peek() + " ");
      queue.remove();
    }
  }

  // Function to reverse the queue
  static void reversequeue() {
    Stack < Integer > stack = new Stack < > ();
    while (!queue.isEmpty()) {
      stack.add(queue.peek());
      queue.remove();
    }
    while (!stack.isEmpty()) {
      queue.add(stack.peek());
      stack.pop();
    }
  }

  public static void main(String args[]) {
    queue = new LinkedList < Integer > ();
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    queue.add(5);
    queue.add(6);
    queue.add(7);
    queue.add(8);
    queue.add(9);
    queue.add(10);

    reversequeue();
    Print();
  }
}

Output: 10 9 8 7 6 5 4 3 2 1

Time Complexity: O(N)

Space Complexity (Auxiliary Space): O(N)

Reason: Use of the stack to store the value for reversing

Special thanks to Abhishek Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article