我在寻找一种Java中的快速队列
实现。我看到LinkedList
实现了Queue
接口,但它只能像一个LinkedList
一样快吗?有没有一种方法可以拥有一个更快的队列,特别是对于add
操作(我只需要poll
,add
和检查是否empty
)。未来我可能还需要PriorityQueue
,但现在还不需要。
ArrayBlockingQueue
。否则,可以查看ArrayDeque
。从ArrayDeque
API中了解到:LinkedList
更快地向队列添加元素。请注意,ArrayBlockingQueue
是有界实现,而ArrayDeque
会根据需要调整大小。LinkedList
通常提供更紧凑的表示,特别是在队列增长和缩小大量的情况下。例如,如果您向ArrayDeque
添加1000万个元素,然后删除9999999个元素,则底层数组仍为长度1000万,而LinkedList
不会遇到此问题。LinkedList
。我想性能差异微不足道,您可能不会注意到差异。current_element_amt < 0.5 * capacity
时自动缩小其大小,这一点你不知道吗? - PacerierGapList
的新列表实现。该实现结合了ArrayList
和LinkedList
的优点。Deque
接口,并且还可以像上述的ArrayDeque
一样进行预调整大小。此外,您还可以免费获得所有List
接口的功能。获取地址:https://github.com/magicwerk/brownies-collections。从具有“C/C++风格”和固定大小的非常简单的旋转队列实现开始。
class SimpleQueue<E>
{
int index = 0;
int head = 0;
int size = 100;
int counter = 0;
E[] data ;
@SuppressWarnings("unchecked")
SimpleQueue()
{
data = (E[]) new Object[size];
}
public void add(E e)
{
data[index]=e;
index=(index+1)%size;
counter++;
}
public E poll()
{
E value = data[head];
head=(head+1)%size;
counter--;
return value;
}
public boolean empty()
{ return counter==0; }
//Test
public static void main(String[] args)
{
SimpleQueue<Integer> s = new SimpleQueue<Integer>();
System.out.println(s.empty());
for(int i=0; i< 10; i++)
s.add(i);
System.out.println(s.empty());
for(int i=0; i<10; i++)
System.out.print(s.poll()+",");
System.out.println("\n"+s.empty());
}
}
ArrayDeque
是一个旋转队列。既然 Java SE 6 库中已经有了这个工具,为什么要重新发明轮子呢? - ThePyroEagle