Reversing a Queue

In Reversing a Queue problem we have given a queue, write an algorithm to reverse the queue.

Examples

Input
queue = 10 -> 8 -> 4 -> 23
Output
queue = 23->4->8->10

Input
queue = 11 -> 98 -> 31 -> 42 -> 73 -> 6
Output
queue = 6 -> 73 -> 42 -> 31 -> 98 -> 11

Input
queue = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Output
queue = 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Algorithm for Reversing a Queue

A queue can be reversed by using a stack,

1. Remove all the elements from the queue and push them to a stack.
2. Pop-out all the elements from the stack and push them back to the queue.
3. The queue is revered, print the elements of the queue.

Explanation for Reversing a Queue

Consider an example,
queue =10 -> 8 -> 4 -> 23

Step 1

One by one remove elements from the queue and push them into a stack.
queue =10 -> 8 -> 4 -> 23 and stack= null
Iteration 1
queue = 8 -> 4 -> 23 and stack= 10
Iteration 2
queue = 4 -> 23 and stack = 8 -> 10
Iteration 3
queue = 23 and stack= 4 -> 8 -> 23
Iteration 4
queue = null and stack = 23->4->8->23

Step 2

Pop out all the elements from the stack and push them back to the queue.
queue = null and stack = 23 -> 4 -> 8 -> 10
Iteration 1
queue = 23 and stack= 4 -> 8 -> 10
Iteration 2
queue = 23 -> 4 and stack = 8 -> 10
Iteration 3
queue = 23 -> 4 -> 8 and stack = 10
Iteration 4
queue = 23 -> 4 -> 8 -> 10 and stack = null

The queue is reversed. See the image below for clarification.

JAVA Code for Reversing a Queue

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReversingAQueue {
    private static void reverseQueue(Queue<Integer> queue) {
        int n = queue.size();

        Stack<Integer> stack = new Stack<>();
        // Remove all the elements from queue and push them to stack
        for (int i = 0; i < n; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }

        // Pop out elements from the stack and push them back to queue
        for (int i = 0; i < n; i++) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Print the reversed queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(8);
        q1.add(4);
        q1.add(23);
        reverseQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(11);
        q2.add(98);
        q2.add(31);
        q2.add(42);
        q2.add(73);
        q2.add(6);
        reverseQueue(q2);
    }
}

23 4 8 10 
6 73 42 31 98 11

C++ Code for Reversing a Queue

#include<bits/stdc++.h> 
using namespace std;

void reverseQueue(queue<int> &queue) {
    int n = queue.size();
    
    stack<int> st;
    // Remove all the elements from queue and push them to stack
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from the stack and push them back to queue
    for (int i = 0; i < n; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Print the reversed queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    int k1 = 3;
    q1.push(10);
    q1.push(8);
    q1.push(4);
    q1.push(23);
    reverseQueue(q1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(11);
    q2.push(98);
    q2.push(31);
    q2.push(42);
    q2.push(73);
    q2.push(6);
    reverseQueue(q2);
}

23 4 8 10 
6 73 42 31 98 11

Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(n) 
where n is the number of nodes in the queue.

References