Reversing a Queue

Problem Statement:

We have to reverse a queue by using only standard operations:-

  • enqueue(element): Add an element to the rear end of the queue.
  • dequeue(): Delete an element from the front end of the queue.
  • empty(): Return true if the queue is empty else false.

What is a queue?

Queue follows the principle of FIFO (First in First out) i.e. element which is inserted first will be removed first. The operation for insertion of elements is known as enqueue operation and the operation for deletion of elements is known as dequeue operation. Like Stack, Queue is also a linear data structure.

Examples:

Input 1: Queue = [11, 22, 33, 44, 55]
Output 1: Queue = [55, 44, 33, 22, 11]

Input 2: Queue = [12, 24, 36, 48]
Output 2: Queue = [48, 36, 24, 12]

Approach 1

Using Stack

For reversing the queue one approach will be to store the elements of the queue in a stack so that if we re-insert the elements in the queue then they would get inserted in reverse order. We use stack because it has the property of ‘LIFO’ as the last element to be inserted in the data structure should actually be the first element of the reversed queue. We use stack for solving this problem. It will be two step process:

  1. Pop element from the front end of the queue and push it into the stack. (Top element of the stack will be the last element of the queue)
  2. Pop element from the top of the stack and push it into the rear end of the queue. (The last element of the stack will be the first element of the queue to be inserted)
#include <bits/stdc++.h>
using namespace std;

void Print(queue<int>& Queue)
{
  while (!Queue.empty()) {
    cout << Queue.front() << " ";
    Queue.pop();
  }
}

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(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);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Queue_reverse {

  static Queue<Integer> queue;

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

  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(10);
    queue.add(20);
    queue.add(30);
    queue.add(40);
    queue.add(50);
    queue.add(60);
    queue.add(70);
    queue.add(80);
    queue.add(90);
    queue.add(100);

    reversequeue();
    Print();
  }
}
from queue import Queue
def Print(queue):
  while (not queue.empty()):
    print(queue.queue[0], end=", ")
    queue.get()



def reversequeue(queue):
  Stack = []
  while (not queue.empty()):
    Stack.append(queue.queue[0])
    queue.get()
  while (len(Stack) != 0):
    queue.put(Stack[-1])
    Stack.pop()


if __name__ == '__main__':
  queue = Queue()
  queue.put(10)
  queue.put(20)
  queue.put(30)
  queue.put(40)
  queue.put(50)
  queue.put(60)
  queue.put(70)
  queue.put(80)
  queue.put(90)
  queue.put(100)

  reversequeue(queue)
  Print(queue)

Complexity Analysis

Time Complexity: The time complexity of this approach is O(n) as we need to insert all the elements in the stack and after that to the queue.
Space Complexity: The space complexity of this approach is O(n) as we use the stack to store all the elements of the queue.

Approach 2

Using Recursion

For reversing the queue, we will use the concept of recursion. The approach will firstly remove the front element from the queue and recursively call the reverse function for the remaining queue. By following this, we are dividing the larger problem into smaller sub-problems.

Recursive Algorithm

  1. Pop an element from the queue if the queue has elements otherwise return an empty queue.
  2. Call the revQueue function for the remaining queue.
  3. At last, Push the popped element in the resultant reversed queue.

Pseudo Code:

queue revQueue(queue)
{
    if (queue is empty)
       return queue;
    else {
       data = queue.front()
       queue.pop()
       queue = revQueue(queue);
       q.push(data);
       return queue;
    }
}
#include 
using namespace std;

void printQueue(queue Queue)
{
  while (!Queue.empty()) {
    cout << Queue.front() << " ";
    Queue.pop();
  }
}

void revQueue(queue& q)
{
  if (q.empty())
    return;

  long long int data = q.front();
  q.pop();

  revQueue(q);

  q.push(data);
}

int main()
{
  queue Queue;
  Queue.push(1);
  Queue.push(2);
  Queue.push(3);
  Queue.push(4);
  Queue.push(5);
  revQueue(Queue);
  printQueue(Queue);
}
// Java program to reverse a Queue by recursion
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// Java program to reverse a queue recursively
 class Queue_reverse {

  static Queue queue;

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

// Recurrsive function to reverse the queue
static Queue revQueue(Queue q)
{
  // Base case
  if (q.isEmpty())
    return q;

  // Dequeue current item (from front)
  int data = q.peek();
  q.remove();

  // Reverse remaining queue
  q = revQueue(q);

  // Enqueue current item (to rear)
  q.add(data);
    
  return q;
}

// Driver code
public static void main(String args[])
{
  queue = new LinkedList();
  queue.add(1);
  queue.add(2);
  queue.add(3);
  queue.add(4);
  queue.add(5);
  queue = revQueue(queue);
  Print();
}
}
from queue import Queue


def revQueue(queue: Queue):
  
  if queue.empty():
    return

  item = queue.queue[0]
  queue.get()

  revQueue(queue)

  queue.put(item)


def print_queue(queue: Queue):
  while not queue.empty():
    print(queue.queue[0], end=" ")
    queue.get()
  print()


if __name__ == "__main__":
  q = Queue()
  q.put(1)
  q.put(2)
  q.put(3)
  q.put(4)
  q.put(5)

  revQueue(q)
  print_queue(q)

Complexity Analysis

Time Complexity: The time complexity of reversing a queue using a recursive function is O(n).
Space Complexity: The auxiliary space for reversing a queue using a recursive function will be O(n), as recursive function uses stack internally.

This article tried to discuss the concept of Reversing a Queue. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *