Error reversing queue in recursive Java method

Question

I am trying to write a recursive method to reverse all elements in a queue.

In an abstract class myQueue which implements Queue< T > interface is my reverse method:

public void reverse() {
  T temp = dequeue();
  Queue<T> bufferQueue = new Queue<T>();

  if(!(temp == null)){
    bufferQueue.enqueue(temp);
  }

  if(!(isEmpty())) {
    reverse();
  }else{
    while(!(bufferQueue.isEmpty())){
       Queue.enqueue(bufferQueue.dequeue);
    }
  }

}

The interface Queue< T > has the following methods which are complete(and implicitly do as defined):

public boolean isEmpty();
public int size();
public void enqueue(T e);
public T dequeue();
public T front();

My goal:

In my reverse method, I am aiming to constantly dequeue (remove first element) from my Original Queue recursively till my queue is empty. Every time I dequeue I will place that object in a temporary Queue. When my queue is empty, than I do enqueue from my temp queue back in to my original Queue.

My first problem is defining a new temporary queue, in my case bufferQueue. I get the following:

1. ERROR at solution.java (at line 12)
Queue<T> bufferQueue = new Queue<T>();
                           ^^^^^
Cannot instantiate the type Queue<T>

Queue is an interface you need to instantiate a concrete implementation of Queue — Ramanlfc
– Ramanlfc, Commented Feb 28, 2016 at 14:48

pczeus · Accepted Answer · 2016-02-28 15:30:00Z

4

Queue is an interface. You can't create an instance of an interface. Check the JavaDoc for Queue and choose a Class that implements Queue instead:

https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

What you are trying to accomplish is surprisingly simple and doesn't require recursion at all, just the available methods on a concrete class, like ArrayDeque + your custom reverse method. Also, you don't need the intermediate bufferQueue. This should work nicely:

public class MyQueue<T> extends ArrayDeque<T>{
    public void reverse() {
      T[] contents = toArray(T[]);
      clear();

      if(contents != null){
        for(int i = contents.length-1; i >= 0; i--){
            add(contents[i]);
        }
      }
  }
}

edited Feb 28, 2016 at 15:30

answered Feb 28, 2016 at 14:47

pczeus

7,8864 gold badges38 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Zimbabaluba Over a year ago

You are right. Am I heading in the right direction as to which my recursion is defined?

pczeus Over a year ago

I think you are better off extending a concrete Queue class so you can simply add the reverse() method, instead of having to implement the multiple abstract methods in the Queue interface

pczeus Over a year ago

Also, call the poll() method instead of dequeue(). Not sure where the dequeue() method comes from. Is that a custom method?

Henning Luther · Accepted Answer · 2016-02-28 14:45:31Z

-2

You need to have a concrete type there not T, T is not possible when isntantiating.

answered Feb 28, 2016 at 14:45

Henning Luther

2,07517 silver badges23 bronze badges

1 Comment

f1sh Over a year ago

Yes it is. T the generic type in this case. In the line before the T temp = dequeue(); is working.

Collectives™ on Stack Overflow

Error reversing queue in recursive Java method

My goal:

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

My goal:

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related