Reverse a Queue using recursion

The problem, simply

You get a queue, a waiting line. You may only take the front item out, add an item at the back, look at the front, and check if the line is empty. Reverse the line, so the back becomes the front. Use recursion: a function that calls itself.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a stack, a pile where the last one on comes off first. Pour the whole line onto the pile, then pour the pile back into the line.

1. While the queue is not empty, take the front and push it on the stack.
2. While the stack is not empty, pop the top and add it at the back of the queue.

import java.util.*;

class Solution {
    public void reverse(Queue<Integer> q) {
        Deque<Integer> stack = new ArrayDeque<>();
        while (!q.isEmpty()) stack.push(q.poll());     // the front goes to the bottom of the pile
        while (!stack.isEmpty()) q.offer(stack.pop()); // the last one in comes out first
    }
}

How long it takes: every item moves twice, O(n). Extra room: the stack holds all n items, O(n).

Way 2: the clever way

Do the same thing without writing a stack. Every function call that is still waiting sits on the call stack, so the computer keeps the pile for you.

1. If the queue is empty, stop. That is the base case.
2. Take the front item and hold it in a local variable.
3. Call reverse on the rest of the queue.
4. When that call returns, the rest is reversed. Add the held item at the back.

import java.util.*;

class Solution {
    public void reverse(Queue<Integer> q) {
        if (q.isEmpty()) return;     // an empty line is already reversed
        int front = q.poll();        // hold the front item
        reverse(q);                  // a helper reverses the rest
        q.offer(front);              // the held item joins at the back
    }
}

How long it takes: one call per item and O(1) work in each, O(n). Extra room: n calls wait on the call stack at the deepest point, O(n). It is the same cost as Way 1; the pile just moved from your code into the call stack.

Watch out for

• Adding the held item back before the recursive call. Then the queue never gets shorter, the calls never reach the base case, and the program overflows the call stack.
• Forgetting the base case. The function would call poll() on an empty queue, get null, and crash when unboxing to int.
• Making a new queue instead of changing the given one. The task is to reverse the queue in place.

What interviewers ask next

• Reverse only the first k items. Recurse k times instead of until empty, then move the other n - k items from the front to the back.
• Reverse a stack using recursion. Harder, because a stack only opens at the top. You need a second helper that inserts an item at the bottom, and it costs O(n^2).
• Can you reverse a queue in place with O(1) extra room and only queue moves? No. A queue only rotates, and rotating never changes the circular order of the items, so something must hold items aside.
• Reverse a linked list with recursion. The same "fix the rest, then fix me" idea, with arrows instead of a line.

Remember this

Grown-up words: the waiting line is a queue, the kids who stepped out are frames on the call stack, the empty line is the base case, and the helper doing the rest is the recursive call.