6

This is not a HW or assignment. This is something i'm practicing myself.

Given a queue, write a Reverse method reverses elements of a queue. MyQueue remains unchanged.

Signature:

public Queue<T> reverse(Queue<T> myQueue) {

Note: It is unknown if the Queue is made using nodes or array.

The queue has methods already implemented, that we can use:

void enqueue(T element)
T dequeue();
boolean isFull();
boolean isEmpty();
int size();
4
  • can you please write some code that you already wrote? May 31, 2013 at 12:28
  • @user503413 thats the point, you just get names of the methods you can use: May 31, 2013 at 12:30
  • Hack: Use a java.util.ArrayList as a buffer. May 31, 2013 at 12:32
  • You mean this is not the JDK's Queue implementation?
    – fge
    May 31, 2013 at 12:34

4 Answers 4

8

You can reverse a queue by using a stack.

Here's how in Java:

public void reverse(Queue q)
{
    Stack s = new Stack();  //create a stack

    //while the queue is not empty
    while(!q.isEmpty())
    {  //add the elements of the queue onto a stack
       s.push(q.serve());
    } 

    //while the stack is not empty
    while(!s.isEmpty())
    { //add the elements in the stack back to the queue
      q.append(s.pop());
    }

}

The append and serve methods of the queue are to add and remove elements of that queue.

Here's an example:

A queue has elements:

1 2 3 4

When the elements get added to a stack, the number 1 will be at the bottom of the list and 4 at the top:

1 2 3 4 <- top

Now pop the stack and put the elements back in the queue:

4 3 2 1

I hope this helped.

5
  1. dequeue the elements of the input queue onto a stack
  2. pop the elements off the stack, enqueueing each into the output queue.
2
  • Thanks bro, thats what i actually did but i wanted to see if there was a better solution? May 31, 2013 at 12:38
  • Not with the interface you provided. There is a data structure called double-ended queue, that allows you to add and remove elements at both ends. Reversing such a data structure can be done without any temporary buffer.
    – Oswald
    May 31, 2013 at 12:41
4

You can do this without any other arrays or lists, just by recursion:

public static <T> Queue<T> flip(Queue<T> q) {
    Queue<T> ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

private static <T> void recursiveFlip(Queue<T> src, Queue<T> dest) {
    T buffer = src.dequeue();
    if(!src.isEmpty()) {
        recursiveFlip(src, dest);
    }
    dest.enqueue(buffer);
}

First elements will be stacked in "shallow" part of the stack, while last elements in "deeper" part, and when recursion reaches the end, the "deeper" values will be added first and "shallow" last.

But note that each one element means one step deeper into recursion, so stack overflow error will occur if the queue is too big.

Also, the original queue will not "survive" the flip.

1

I've used two different approaches that don't depend on your queue size. The first one uses Stack and second one - Java 8 Stream API (the fastest).

The most effective solution for reversing queue in my tests is:

private Queue<Integer> reverse(Queue<Integer> queue) {
        List<Integer> collect = queue.stream()
                .collect(Collectors.toList());
        Collections.reverse(collect);
        return new LinkedList<>(collect);
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.