Home » Technical Interview Questions » Queue Interview Questions » Reversing a Queue

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

READ  Implementation of Deque using circular array

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

Reversing a Queue

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.

READ  Priority Queue

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup