基于先进先出（FIFO）的队列实现？

Question

我需要一个简单的先进先出(FIFO)队列，用于存储一些整数 (如果是泛型实现也没关系)。

java.util 或 Trove/Guava 库中是否有现成的实现？

- Rajat Gupta

---

请看这里：https://docs.oracle.com/javase/tutorial/collections/implementations/queue.html - Koray Tugay

Answer 1

是的。 队列

链表 是最简单的具体实现。

- John B

---

请注意，Javadoc 列出了所有的实现。另外，上面第二个链接是指 LinkedList。 - John B

LinkedList不是一个接口，而是一个具体的类。另外，ArrayDeque通常更快。 - Louis Wasserman

嘿，我正在使用ArrayDeque，但我需要一种修改其所有元素（整数）实际上从所有元素中减去一个值的方法..有更好的方法吗？ - Rajat Gupta

在这里补充一个指针... 参考这个链接阅读有关比较ArrayDeque和LinkedList速度的实验以及可能的原因.. http://javaqueue2010.blogspot.com/2010/06/performance-comparison-between.html - Shatu

实际上这并不正确：根据Java文档的说明，队列不一定是先进先出的（FIFO）：http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html。然而，由于LinkedList的顺序是固定的，因此可以将其用作队列。 - Pieter Bos

Answer 2

以下是使用Java内置的先进先出队列（FIFO queue）的示例代码：

public static void main(String[] args) {
    Queue<Integer> myQ = new LinkedList<Integer>();
    myQ.add(1);
    myQ.add(6);
    myQ.add(3);
    System.out.println(myQ);   // 1 6 3
    int first = myQ.poll();    // retrieve and remove the first element
    System.out.println(first); // 1
    System.out.println(myQ);   // 6 3
}

- DavidNg

Answer 3

ArrayDeque 可能是JDK中最快的基于对象的队列；Trove有 TIntQueue 接口，但我不知道它的实现在哪里。

- Louis Wasserman

---

为了使ArrayDeque作为队列（先进先出）而不是栈（后进先出）运行，您应该使用add和remove。如果您使用push和pop，它将表现为一个栈。（严格来说，remove和pop是相同的，但由于add/pop或push/remove不成对，因此我们选择add/remove和push/pop。） - ADTC

Answer 4

LinkedList可以用作队列，但您需要正确使用它。以下是示例代码：

@Test
public void testQueue() {
    LinkedList<Integer> queue = new LinkedList<>();
    queue.add(1);
    queue.add(2);
    System.out.println(queue.pop());
    System.out.println(queue.pop());
}

输出：

1
2

注意，如果您使用push而不是add( 这很可能是您直觉的选择 ),这将在列表前添加元素，使其表现得像一个栈。

因此，仅当与add一起使用时，它才是一个队列。

试试这个：

@Test
public void testQueue() {
    LinkedList<Integer> queue = new LinkedList<>();
    queue.push(1);
    queue.push(2);
    System.out.println(queue.pop());
    System.out.println(queue.pop());
}

输出：

2
1

- Gautam

Answer 5

Queue是一个在Java中扩展Collection接口的接口。它具有支持FIFO架构所需的所有功能。

对于具体的实现，您可以使用LinkedList。 LinkedList实现了Deque，后者又实现了Queue。所有这些都是java.util包的一部分。

有关具有示例的方法的详细信息，您可以参考Java中基于FIFO的队列实现。

注：上面的链接指向我的个人博客，其中包含有关此内容的其他详细信息。

- Aniket Thakur