Reversing a Queue

There was a question in the discussion as to how to reverse a queue without a stack.

Reversing a queue using a stack is quite easy.

 private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

How to do it without a stack. I think, there may be convoluted ways. But here's a simple way using recursion:

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

Well, there's no magic happening here. Actually, we are cheating a bit here. How? We have simulated the behaviour of a stack through recursion. In fact, there's still a stack -- an actual stack -- in action which enables us to solve this problem. It's the program stack! Just that it's hidden.

Many algorithms which could be implemented using a loop and a stack could be rephrased into a simpler one with recursion, simply because recursion hides the stack within itself and allows us to reap its benefits all the same! A classical example is depth first search of trees, which can be implemented using a stack, but a simpler and elegant implementation can be created using recursion.

Here's the complete code:

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

public class Reverse {

  public static void main(String[] args) {

    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);

    System.out.println("Before reversing ...");
    printQueue(queue);
    // reverseWithoutStack(queue);
    reverseWithoutStack(queue);
    System.out.println("After reversing ...");
    printQueue(queue);
  }

  private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

  private static void printQueue(Queue<Integer> queue) {
    String s = "[ ";
    for(int i = 0; i < queue.size(); i++) {
      int n = queue.remove();
      if(i <= queue.size() - 1) {
        s += n + ", ";
      }
      else {
        s += n + " ";
      }
      queue.add(n);
    }
    s += "]";
    System.out.println(s);
  }
}