Что является более эффективным способом реализации enqueue в Java

Question

Итак, у меня есть этот простой код в java. Он вставляет (добавляет) и элемент в конец очереди (реализуется ArrayList) без изменения исходной очереди. Код:

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); 
} 

идея заключается в том, чтобы поставить в очередь быстрее и эффективнее, и снова, как вы заметили, не изменяя значение исходной очереди.

ОБНОВЛЕНИЕ Ради завершения идеи.

1- Это задание, так что университет, предоставленный скелет не должен быть изменен, задача состоит в том, чтобы сделать функцию в очереди быстрее (я понимаю, что я копирую дважды, а это медленная часть).

2- Что касается вспомогательных функций, они просты:

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

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

Любые идеи? спасибо

Answer 1

Очередь - это базовая структура данных, и трудно сделать ее лучше, чем специалисты, работающие над ней. Самая простая и быстрая реализация общего назначения - это, вероятно, ArrayDeque, и вряд ли что-то улучшить.

Что вы делаете странно, в лучшем случае:

• Вместо добавления элемента, необходимо скопировать все содержимое. Зачем?
• Вы вставляете новый элемент с самым высоким индексом, почему? Таким образом, ваш опрос (dequeue, remove, whatever) должен удалить индекс в элементе 0, который медленный для ArrayList.

На самом деле, я понятия не имею, как может выглядеть ваш poll. В любом случае ваша очередь не выполняет то, что я ожидаю от метода, названного так.

Answer 2

Используйте LinkedList вместо ArrayList. Вы не нуждаетесь в индексированном доступе в очереди, но вам нужна быстрая установка очереди/dequeue. Если вам нужен индексированный доступ. Это совсем не очередь. И просто используйте метод add(), не создавайте целую новую очередь каждый раз. Метод enqueue() должен возвращать «this» или void. И не позволяйте вызывающему абоненту поставлять список: создайте свой собственный.