Queue Reversal

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Reverse a queue using a stack. Push all elements to stack, then pop back to queue.

Algorithm

1Dequeue all into stack. Then pop from stack back into queue.

Common Pitfalls

•Stack reverses order. Alternative: recursive approach using call stack.

Queue Reversal.java

Java

// Approach: Use a stack: dequeue all to stack, enqueue all back from stack.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public void reverseQueue(Queue<Integer> q) {
        Stack<Integer> st = new Stack<>();

        while (q.size() > 0)
            st.push(q.remove());

        while (st.size() > 0)
            q.add(st.pop());
    }
}

Was this solution helpful?