how can I create a recursive algorithm that reverses the order of the values stored in the queue?-CodePudding

how can I create a recursive algorithm called reverse(Q) that reverses the order of the values stored in the queue while only using enqueue, dequeue, isEmpty? these are the only operations I use to manipulate the queue. I can’t use any type of loop, and without creating any additional data structure?

Q: 2 4 6 8 10 12 -------> reversed queue: 12 10 8 6 4 2

how would I do that?

CodePudding user response：

If you use Dequeue class from Java Library then you can proceed like below:

private static void reverse(Deque<Integer> q)
    {
        if(!q.isEmpty()) {
            System.out.print(q.pollLast() " ");
            reverse(q);
        }
        
    }

CodePudding user response：

You'll want your recursive function to first pop the front element out of the queue and call itself again before re-inserting the element. This way the first recursive call that actually gets to re-insert its newly popped element back is the last one.

import java.util.concurrent.ArrayBlockingQueue;
import java.util.Queue;

class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new ArrayBlockingQueue<>(100); // 100 is the queue's capacity
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        Main.reverse(q);
        while (q.peek() != null) {
            System.out.println(q.remove());
        }
    }
    
    public static <T> void reverse(Queue<T> q) {
        if (q.peek() == null) {
            return;
        }
        T val = q.remove();
        reverse(q);
        q.add(val);
    }
}

Output