Reversing a Queue

Last Updated : 05 Dec, 2022

Give an algorithm for reversing a queue Q. Only the following standard operations are allowed on queue.

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

The task is to reverse the queue.

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]

Recommended PracticeQueue ReversalTry It!

Reversing a Queue using stack:

For reversing the queue one approach could be to store the elements of the queue in a temporary data structure in a manner such that if we re-insert the elements in the queue they would get inserted in reverse order. So now our task is to choose such a data structure that can serve the purpose. According to the approach, the data structure should have 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.

Follow the below steps to implement the idea:

Pop the elements from the queue and insert into the stack now topmost element of the stack is the last element of the queue.
Pop the elements of the stack to insert back into the queue the last element is the first one to be inserted into the queue.

Below is the implementation of above approach:

C++

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

Java

// Java program to reverse a Queue
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 
// Java program to reverse a queue
public class Queue_reverse {
 
    static Queue<Integer> queue;
 
    // Utility 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();
        }
    }
 
    // Driver code
    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();
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 program to reverse a queue
from collections import deque
 
# Function to reverse the queue
 
 
def reversequeue(queue):
    Stack = []
 
    while (queue):
        Stack.append(queue[0])
        queue.popleft()
 
    while (len(Stack) != 0):
        queue.append(Stack[-1])
        Stack.pop()
 
 
# Driver code
if __name__ == '__main__':
    queue = deque([10, 20, 30, 40, 50, 60, 70, 80, 90, 100])
 
    reversequeue(queue)
    print(queue)
 
# This code is contributed by PranchalK

C#

// c# program to reverse a Queue
using System;
using System.Collections.Generic;
 
public class GFG {
 
    public static LinkedList<int> queue;
 
    // Utility function to print the queue
    public static void Print()
    {
        while (queue.Count > 0) {
            Console.Write(queue.First.Value + ", ");
            queue.RemoveFirst();
        }
    }
 
    // Function to reverse the queue
    public static void reversequeue()
    {
        Stack<int> stack = new Stack<int>();
        while (queue.Count > 0) {
            stack.Push(queue.First.Value);
            queue.RemoveFirst();
        }
        while (stack.Count > 0) {
            queue.AddLast(stack.Peek());
            stack.Pop();
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        queue = new LinkedList<int>();
        queue.AddLast(10);
        queue.AddLast(20);
        queue.AddLast(30);
        queue.AddLast(40);
        queue.AddLast(50);
        queue.AddLast(60);
        queue.AddLast(70);
        queue.AddLast(80);
        queue.AddLast(90);
        queue.AddLast(100);
 
        reversequeue();
        Print();
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // Javascript program to reverse a Queue
     
    let queue = [];
   
    // Utility function to print the queue
    function Print()
    {
        while (queue.length > 0) {
            document.write( queue[0] + ", ");
            queue.shift();
        }
    }
   
    // Function to reverse the queue
    function reversequeue()
    {
        let stack = [];
        while (queue.length > 0) {
            stack.push(queue[0]);
            queue.shift();
        }
        while (stack.length > 0) {
            queue.push(stack[stack.length - 1]);
            stack.pop();
        }
    }
     
    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();
    Print();
     
</script>

Output

100 90 80 70 60 50 40 30 20 10

Time Complexity: O(N), As we need to insert all the elements in the stack and later to the queue.
Auxiliary Space: O(N), Use of stack to store values.

Reversing a Queue using recursion:

Instead of explicitly using stack goal can be achieved using recursion (recursion at backend will itself maintain stack).

Follow the below steps to implement the idea:

Recursively perform the following steps:
- If the queue size is 0 return.
- Else pop and store the front element and recur for remaining queue.
- push the current element in the queue.

Thank you Nakshatra Chhillar for suggesting this approach and contributing the code

Below is the implementation of above approach:

C++

// 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>& q)
{
    // base case
    if (q.size() == 0)
        return;
    // storing front(first element) of queue
    int fr = q.front();
 
    // removing front
    q.pop();
 
    // asking recursion to reverse the
    // leftover queue
    reverseQueue(q);
 
    // placing first element
    // at its correct position
    q.push(fr);
}
 
// 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);
}
// This code is contributed by Nakshatra Chhillar

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
class GFG {
 
  // Utility function to print the queue
  public static void Print(Queue<Integer> Queue)
  {
    while (Queue.size() > 0) {
      System.out.print(Queue.peek() + " ");
      Queue.remove();
    }
  }
 
  // Function to reverse the queue
  public static void reverseQueue(Queue<Integer> q)
  {
    // base case
    if (q.size() == 0)
      return;
    // storing front(first element) of queue
    int fr = q.peek();
 
    // removing front
    q.remove();
 
    // asking recursion to reverse the
    // leftover queue
    reverseQueue(q);
 
    // placing first element
    // at its correct position
    q.add(fr);
  }
 
  public static void main(String[] args)
  {
    Queue<Integer> Queue = new LinkedList<>();
 
    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(Queue);
    Print(Queue);
  }
}
 
// This code is contributed by akashish__

Python3

# Python3 program to reverse a Queue
 
# Utility function to print the queue
def Print(Queue):
    while (len(Queue) > 0):
        print(Queue[0],end = " ")
        Queue.pop(0)
 
# Function to reverse the queue
def reverseQueue(q):
   
    # base case
    if (len(q) == 0):
        return
    # storing front(first element) of queue
    fr = q[0]
 
    # removing front
    q.pop(0)
 
    # asking recursion to reverse the
    # leftover queue
    reverseQueue(q)
 
    # placing first element
    # at its correct position
    q.append(fr)
 
# Driver code
Queue = []
Queue.append(10)
Queue.append(20)
Queue.append(30)
Queue.append(40)
Queue.append(50)
Queue.append(60)
Queue.append(70)
Queue.append(80)
Queue.append(90)
Queue.append(100)
 
reverseQueue(Queue)
Print(Queue)
 
# This code is contributed by akashish__

C#

// CPP program to reverse a Queue
using System;
using System.Collections;
 
public class GFG {
 
    // Utility function to print the queue
    public static void Print(Queue Queue)
    {
        while (Queue.Count > 0) {
            Console.Write(Queue.Peek());
            Console.Write(" ");
            Queue.Dequeue();
        }
    }
 
    // Function to reverse the queue
    public static void reverseQueue(Queue q)
    {
        // base case
        if (q.Count == 0)
            return;
        // storing front(first element) of queue
        int fr = (int)q.Peek();
 
        // removing front
        q.Dequeue();
 
        // asking recursion to reverse the
        // leftover queue
        reverseQueue(q);
 
        // placing first element
        // at its correct position
        q.Enqueue(fr);
    }
 
    // Driver code
    static public void Main()
    {
 
        Queue Queue = new Queue();
        Queue.Enqueue(10);
        Queue.Enqueue(20);
        Queue.Enqueue(30);
        Queue.Enqueue(40);
        Queue.Enqueue(50);
        Queue.Enqueue(60);
        Queue.Enqueue(70);
        Queue.Enqueue(80);
        Queue.Enqueue(90);
        Queue.Enqueue(100);
 
        reverseQueue(Queue);
        Print(Queue);
    }
}

Javascript

// JS program to reverse a Queue
 
// Utility function to print the queue
function Print(Queue) {
    while (Queue.length != 0) {
        console.log(Queue[0]);
        Queue.shift();
    }
}
 
// Function to reverse the queue
function reverseQueue(q) {
    // base case
    if (q.length == 0)
        return;
    // storing front(first element) of queue
    let fr = q[0];
 
    // removing front
    q.shift();
 
    // asking recursion to reverse the
    // leftover queue
    reverseQueue(q);
 
    // placing first element
    // at its correct position
    q.push(fr);
}
 
// Driver code
let 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);
 
 
// This code is contributed by adityamaharshi21.

Output

100 90 80 70 60 50 40 30 20 10

Time Complexity: O(N).
Auxiliary Space: O(N). The recursion stack contains all elements of queue at a moment.

GeeksforGeeks

Improve

Previous Article

How to Reverse a String using Stack

How to create mergeable stack?

Similar Reads

Reversing a Queue using another Queue

Given a queue. The task is to reverse the queue using another empty queue. Examples: Input: queue[] = {1, 2, 3, 4, 5} Output: 5 4 3 2 1 Input: queue[] = {10, 20, 30, 40} Output: 40 30 20 10 Approach: Given a queue and an empty queue.The last element of the queue should be the first element of the new queue.To get the last element there is a need to

Should we declare as Queue or Priority Queue while using Priority Queue in Java?

Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

Reversing a queue using recursion

Given a queue, write a recursive function to reverse it. Standard operations allowed : enqueue(x) : Add an item x to rear of queue. dequeue() : Remove an item from front of queue. empty() : Checks if a queue is empty or not. Examples : Input : Q = [5, 24, 9, 6, 8, 4, 1, 8, 3, 6] Output : Q = [6, 3, 8, 1, 4, 8, 6, 9, 24, 5] Explanation : Output queu

Reversing the first K elements of a Queue

Given an integer k and a queue of integers, The task is to reverse the order of the first k elements of the queue, leaving the other elements in the same relative order. Only following standard operations are allowed on queue. enqueue(x) : Add an item x to rear of queuedequeue() : Remove an item from front of queuesize() : Returns number of element

What is Priority Queue | Introduction to Priority Queue

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values. In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its

Stack and Queue in Python using queue Module

A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.

Check if a queue can be sorted into another queue using a stack

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp

Advantages of circular queue over linear queue

Linear Queue: A Linear Queue is generally referred to as Queue. It is a linear data structure that follows the FIFO (First In First Out) order. A real-life example of a queue is any queue of customers waiting to buy a product from a shop where the customer that came first is served first. In Queue all deletions (dequeue) are made at the front and a

Difference between Queue and Deque (Queue vs. Deque)

Queue: The queue is an abstract data type or linear data structure from which elements can be inserted at the rear(back) of the queue and elements can be deleted from the front(head) of the queue. The operations allowed in the queue are:insert an element at the reardelete element from the frontget the last elementget the first elementcheck the size

Why can't a Priority Queue wrap around like an ordinary Queue?

Priority Queue: A priority queue is a special type of queue in which each element is assigned a priority value. And elements are served based on their priority. This means that elements with higher priority are served first. However, if elements with the same priority occur, they will be served in the order in which they were queued. A priority que

Article Tags :

Practice Tags :