Reversing a Queue

Given a queue q[], reverse the queue so that the front element becomes the rear and the rear element becomes the front, while preserving the order of the remaining elements accordingly.

Examples: 

Input: q[] = [5, 10, 15, 20, 25]
Output: [25, 20, 15, 10, 5]
Explanation: The original front 5 moves to the rear, and the rear 25 becomes the new front. All other elements follow the reversed order.

Input: q[] = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: The queue is reversed completely: 1 goes to the rear, and 5 moves to the front, with all intermediate elements rearranged accordingly.

[Approach 1] Using Stack - O(n) Time and O(n) Space

To reverse the queue, we can use a stack data structure that follows the LIFO (Last In, First Out) principle. By storing the elements in stack, we can ensure that when the elements are re-inserted into the queue, they will appear in reverse order.

Working:

• 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.

In JavaScript, there’s no built-in queue, so we use arrays. Removing elements with q.shift() takes O(n) time due to re-indexing, which makes repeated operations lead to an overall O(n²) time complexity.

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

void reverseQueue(queue<int>& q) {
    stack<int> st;
    
    // Transfer all elements from queue to stack
    while (!q.empty()) {
        st.push(q.front());
        q.pop();
    }
    
    // Transfer all elements back from stack to queue
    // This reverses the order
    while (!st.empty()) {
        q.push(st.top());
        st.pop();
    }
}

int main() {
    queue<int> q;
    q.push(5);
    q.push(10);
    q.push(15);
    q.push(20);
    q.push(25);
   
    reverseQueue(q);
    
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
}

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

class GfG {
    static void reverseQueue(Queue<Integer> q) {
        Stack<Integer> st = new Stack<>();
        
        // Transfer all elements from queue to stack
        while (!q.isEmpty()) {
            st.push(q.peek());
            q.remove();
        }
        
        // Transfer all elements back from stack to queue
        // This reverses the order
        while (!st.isEmpty()) {
            q.add(st.pop());
        }
    }
    
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.add(5);
        q.add(10);
        q.add(15);
        q.add(20);
        q.add(25);
        
        reverseQueue(q);
        
        while (!q.isEmpty()) {
            System.out.print(q.peek() + " ");
            q.remove();
        }
    }
}

from collections import deque

def reverseQueue(q):
    st = []
    
    # Transfer all elements from queue to stack
    while q:
        st.append(q[0])
        q.popleft()
    
    # Transfer all elements back from stack to queue
    # This reverses the order
    while st:
        q.append(st.pop())

if __name__ == "__main__":
    q = deque([5, 10, 15, 20, 25])
    
    reverseQueue(q)
    
    while q:
        print(q.popleft(), end=' ')

using System;
using System.Collections.Generic;

class GfG {
    static void reverseQueue(Queue<int> q) {
        Stack<int> st = new Stack<int>();
        
        // Transfer all elements from queue to stack
        while (q.Count > 0) {
            st.Push(q.Peek());
            q.Dequeue();
        }
        
        // Transfer all elements back from stack to queue
        // This reverses the order
        while (st.Count > 0) {
            q.Enqueue(st.Pop());
        }
    }
    
    public static void Main() {
        Queue<int> q = new Queue<int>();
        q.Enqueue(5);
        q.Enqueue(10);
        q.Enqueue(15);
        q.Enqueue(20);
        q.Enqueue(25);
        
        reverseQueue(q);
        
        while (q.Count > 0)
        {
            Console.Write(q.Dequeue() + " ");
        }
    }
}

function reverseQueue(q) {
    let st = [];
    
    // Transfer all elements from queue to stack
    while (q.length > 0) {
        st.push(q[0]);
        q.shift();
    }
    
    // Transfer all elements back from stack to queue
    // This reverses the order
    while (st.length > 0) {
        q.push(st.pop());
    }
}

// Driver Code
let q = [5, 10, 15, 20, 25];

reverseQueue(q);

let res = [];
while (q.length > 0) {
    res.push(q.shift());
}
console.log(res.join(' '));

25 20 15 10 5 

[Approach 2] Using Recursion

A queue follows FIFO order (first in, first out). To reverse it, we need the front element to move to the rear, and repeat this process for all elements.

Here’s how to use recursion:

• Remove the front element of the queue.
• Recursively reverse the remaining queue.
• Insert the removed element at the rear.

Recursion uses the call stack to remember removed elements. When the recursive calls return, those elements are added back in reverse order.

In JavaScript, there’s no built-in queue, so we use arrays. Removing elements with q.shift() takes O(n) time due to re-indexing, which makes repeated operations lead to an overall O(n²) time complexity.

#include <iostream>
#include <queue>
using namespace std;

void reverseQueue(queue<int>& q) {

    if (q.empty()) return;

    // remove front element
    int front = q.front();
    q.pop();

    // reverse remaining queue
    reverseQueue(q);

    // insert removed element at the rear
    q.push(front);
}

int main() {
    queue<int> q;
    q.push(5);
    q.push(10);
    q.push(15);
    q.push(20);
    q.push(25);

    reverseQueue(q);

    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

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

class GfG {
    static void reverseQueue(Queue<Integer> q) {
        if (q.isEmpty()) return;

        // remove front element
        int front = q.peek();
        q.poll();

        // reverse remaining queue
        reverseQueue(q);

        // insert removed element at the rear
        q.add(front);
    }

    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.add(5);
        q.add(10);
        q.add(15);
        q.add(20);
        q.add(25);

        reverseQueue(q);

        while (!q.isEmpty()) {
            System.out.print(q.peek() + " ");
            q.poll();
        }
    }
}

from collections import deque

def reverseQueue(q):
    if not q:
        return

    # remove front element
    front = q.popleft()

    # reverse remaining queue
    reverseQueue(q)

    # insert removed element at the rear
    q.append(front)

if __name__ == '__main__':
    q = deque([5, 10, 15, 20, 25])
    reverseQueue(q)
    while q:
        print(q.popleft(), end=' ')

using System;
using System.Collections.Generic;

class GfG {
    static void reverseQueue(Queue<int> q) {
        if (q.Count == 0) return;

        // remove front element
        int front = q.Dequeue();

        // reverse remaining queue
        reverseQueue(q);

        // insert removed element at the rear
        q.Enqueue(front);
    }

    public static void Main() {
        Queue<int> q = new Queue<int>();
        q.Enqueue(5);
        q.Enqueue(10);
        q.Enqueue(15);
        q.Enqueue(20);
        q.Enqueue(25);

        reverseQueue(q);

        while (q.Count > 0) {
            Console.Write(q.Dequeue() + " ");
        }
    }
}

function reverseQueue(q) {
    if (q.length === 0) return;

    // remove front element
    let front = q.shift();

    // reverse remaining queue
    reverseQueue(q);

    // insert removed element at the rear
    q.push(front);
}

// Driver Code
let q = [5, 10, 15, 20, 25];
reverseQueue(q);

let res = [];

while (q.length > 0) {
    res.push(q.shift());
}
console.log(res.join(' '));

25 20 15 10 5 

Time Complexity: O(n)
Auxiliary Space: O(n), due to recursion stack