入隊列表方法

有沒有辦法更快地入隊此方法？我試圖給這個方法添加性能測試，並想知道是否有替代方案。入隊列表方法

import java.util.ArrayList; 
    import java.util.List; 
    import java.util.NoSuchElementException; 

    public class ImmutableQueueImpl<E> implements ImmutableQueue<E> { 
     private  List<E> queue; 
     public ImmutableQueueImpl() { 
     queue = new ArrayList<E>(); 
     } 

     private ImmutableQueueImpl(List<E> queue) { 
     this.queue = queue; } 

     @Override 
     public ImmutableQueue<E> enqueue(E e) { 
     if (e == null) { 
     throw new IllegalArgumentException(); 
     } 
     List<E> clone = new ArrayList<E>(queue); clone.add(e); 
     return new ImmutableQueueImpl<E>(clone); 
     } 

     @Override 
     public ImmutableQueue<E> dequeue() { 
     if (queue.isEmpty()) { 
      throw new NoSuchElementException(); 
     } 
     List<E> clone = new ArrayList<E>(queue); 
     clone.remove(0); 
     return new ImmutableQueueImpl<E>(clone); 
     } 

     @Override 
     public E peek() { 
     if (queue.isEmpty()) { 
      throw new NoSuchElementException(); 
     } 
     return queue.get(0); 
     } 

    @Override 
    public int size() { 
     return queue.size(); 
    } 
    }

編輯我已經添加了參考的全部代碼。希望有所幫助

來源

2013-03-19 Siddharthan Asokan

什麼是'ImmutableQueueImpl'？ – 2013-03-19 15:47:30

表示對象的不可變先進先出（FIFO）隊列的隊列類。 – 2013-03-19 15:48:07

是的，我知道隊列是什麼。但是，如果你沒有確切地告訴我們'ImmutableQueueImpl'類是什麼，我們如何才能知道是否有更快的選擇來展示你所展示的？例如，它是否創建*另一個*副本？你能改變它的代碼嗎？ – 2013-03-19 15:52:26

在內部使用2個不可變列表可以在不可變隊列中獲得O（1）的入隊/出隊操作。

下面是從Scala book借來代碼：

class Queue[T](
    private val leading: List[T], 
    private val trailing: List[T] 
) { 
    private def mirror = 
    if (leading.isEmpty) new Queue(trailing.reverse, Nil) 
    else this 

    def head = mirror.leading.head 

    def tail = { 
    val q = mirror 
    new Queue(q.leading.tail, q.trailing) 
    } 

    def append(x: T) = new Queue(leading, x :: trailing) 
}

來源

2013-03-21 15:20:25

入隊列表方法

回答

相關問題