如何提升自定义队列效率
代码如下，如何提高enqueue和dequeue的效率
package jp.co.wap.exam;

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

public class PersistentQueue<E> {
private List<E> queue;
public PersistentQueue(){
//modify this constructor if neccessary, but do not remove it
queue = new ArrayList<E>();
}
private PersistentQueue(List<E> queue){
//modify or remove this constructor if necessary
this.queue = queue;
}
//add other constructor if necessary
/**
 *  Returns the queue that adds an item into the tail of this queue without modifying this queue
 * @param e
 * @return
 * @throws IllegalArgumentException
 */
public PersistentQueue<E> enqueue( E e){
//TODO: make this method faster
if (e == null){
throw new IllegalArgumentException();
}
List<E> clone = new ArrayList<E>(queue);
clone.add(e);
return new PersistentQueue<E>(clone);
}
/**
 * Returns the queue that removes the object at the head of this queue without modifying this queue
 * 
 * If this queue is empty,throws java.util.NoSuchElementException
 * @return 
 * @throws 
 * /java.util.NoSuchElementException
 */
public PersistentQueue<E> dequeue(){
//TODO:make this method faster
if ( queue.isEmpty()){
throw new NoSuchElementException();
}
List<E> clone = new ArrayList<E>(queue);
clone.remove(0);
return new PersistentQueue<E>(clone);
}
public E peek(){
//modify this method if needed
if (queue.isEmpty()){
throw new NoSuchElementException();
}
return queue.get(0);
}
public int size(){
//modify this method if necessary
return queue.size();
}

public static void main(String[] args){
PersistentQueue<String> ps = new PersistentQueue<String>();
ps.enqueue("string");
System.out.print(ps.peek());
}
}

------解决方案--------------------
我怎么感觉可以就这样写呢
public class PersistentQueue<E> extends ArrayList<E>
------解决方案--------------------
哪里感觉出效率低呢
------解决方案--------------------
用ArrayList去实现队列就不可能快起来。
------解决方案--------------------

引用:

Quote: 引用:

每个人的出发点可能不一样，一般队列的使用方式就进栈，出栈，清空等，你这个等于是有特殊使用需求，一般是构造一个特殊的队列，可供改变原内容的，比如可以改变队列中某具体位置元素内容的，这个需求貌似就是java.util.LinkedList<E>

其实这个示例不需要在任意位置插入和删除元素，就是一个FIFO，队尾插入，队头删除，用LinkedList当然也是可以的。这是某知名IT公司的一道应试题，就是要求尽可能提升enqueue和dequeue的速度。

呵呵，尽可能啊。
这个很坑。
可不可以回答jni呢？
------解决方案--------------------
队列为什么不用LinkedList，这个是《Java编程思想》推荐的。
具体原理如下：
LinkedList底层实现是链表（双向链表），检索效率低、插入、删除效率；
ArrayList的底层实现是数组，检索效率高、插入、删除效率低。

从效率来看队列是先进先出，最频繁的操作应该是插入和移出，因此使用LinkedList的效率肯定比ArrayList高，还有楼主可以看一下LinkedList的源码，使用的双向循环链表，实现stack、单向队列、双向队列都能满足，而且效率肯定不会低，当然你也可以自己根据里面的算法原理，自己实现。
------解决方案--------------------

引用:

Quote: 引用:

每个人的出发点可能不一样，一般队列的使用方式就进栈，出栈，清空等，你这个等于是有特殊使用需求，一般是构造一个特殊的队列，可供改变原内容的，比如可以改变队列中某具体位置元素内容的，这个需求貌似就是java.util.LinkedList<E>

其实这个示例不需要在任意位置插入和删除元素，就是一个FIFO，队尾插入，队头删除，用LinkedList当然也是可以的。这是某知名IT公司的一道应试题，就是要求尽可能提升enqueue和dequeue的速度。

推荐使用LinkedList来做，LinkedList是实现了Deque接口的，而Deque是继承了Queue接口的，所以说用LinkedList可以像使用队列一样，FIFO