CODEWITHSUNDEEP
javaperformancearraylistqueue
MandM
MandM

Reputation: 1

what is a more efficient way to implement enqueue in Java

So I have this simple code in java. It enqueue (adds) and element to the end of the queue (implemented by an ArrayList) without changing the original queue. The code:

public class MyQueue<T>{
private List<T> body;

// some constructors and helper functions.

//copy constructor
public Queue(List<T> list){
this.body = list;
}

//this is the function
public MyQueue<T> enqueue(T obj){
List<T> temp = new ArrayList<T>(body);
temp.add(obj);
return new Queue<T>(temp);
}

The whole Idea is to make enqueue faster and more efficient, and again, as you notice, without changing the value of the original queue.

UPDATE For the sake of completing the idea.

1- This is an assignment so university, the skeleton provided is not to be changed, the task is to make the function enqueue faster (i do realize i am copying twice and thats the slow part).

2- As for the helper functions, they are simple:

public T peek(){
if(body.isEmpty()){
   thrown new NoSuchElementException();
}
return body.get(0);
}

public int size(){
return body.size();
}

Any ideas? thanks

Upvotes: 0

Views: 763

Answers (2)

user207421
user207421

Reputation: 311001

Use a LinkedList instead of an ArrayList. You don't need indexed access in a queue, but you do need fast enqueue/dequeue. If you need indexed access. It isn't really a queue at all. And just use the add() method, don't create a whole new queue every time. Your enqueue() method should return 'this', or void. And don't allow the caller to supply the list: create your own.

Upvotes: 0

maaartinus
maaartinus

Reputation: 46472

A queue is a basic data structure and it's hard to make it better than the experts having worked on it. The simplest and fastest general purpose implementation is probably the ArrayDeque and there's hardly anything to improve.

What you're doing is strange at best:

  • Instead of appending an element, you copy the whole content. Why?
  • You insert the new element at the highest index, why? This way your poll (dequeue, remove, whatever) must remove the index at element 0, which is slow for ArrayList.

Actually, I have no idea how your poll may look like. In any case, your enqueue doesn't do what I'd expect from a method called like this.

Upvotes: 1

Related Questions