java 中可以使用 arraylist 模拟队列的先进先出(fifo)行为,具体做法是结合使用 add() 方法在尾部追加元素,以及 remove(0) 方法从头部移除并返回元素。这种实现方式虽然能达成队列的基本功能,但由于 arraylist 底层是数组,头部删除操作会导致后续所有元素向前移动,时间复杂度为 o(n),因此在数据量较大时性能较差。

ArrayList 作为队列的核心操作逻辑
当我们将 ArrayList 视为队列时,核心在于明确队头和队尾的操作位置。入队操作对应 add(E e),它直接将新元素追加到列表末尾,这一步的时间复杂度是 O(1)。出队操作对应 remove(int index),指定索引为 0,即移除第一个元素。由于数组的物理连续性,移除首元素后,剩余的所有元素都需要向左平移一位以填补空缺,这就是其性能瓶颈所在。

import java.util.ArrayList;
import java.util.List;
public class ArrayListQueue {
private List<String> queue = new ArrayList<>();
// 入队:添加到列表末尾
public void enqueue(String item) {
queue.add(item);
}
// 出队:移除并返回列表头部元素
public String dequeue() {
if (queue.isEmpty()) {
return null;
}
return queue.remove(0);
}
// 查看队头元素
public String peek() {
if (queue.isEmpty()) {
return null;
}
return queue.get(0);
}
// 判断是否为空
public boolean isEmpty() {
return queue.isEmpty();
}
public static void main(String[] args) {
ArrayListQueue q = new ArrayListQueue();
q.enqueue("A");
q.enqueue("B");
q.enqueue("C");
System.out.println(q.dequeue()); // 输出 A
System.out.println(q.peek()); // 输出 B
}
}
上述代码展示了基于 ArrayList 的最小队列实现。通过 enqueue 方法调用 add 实现入队,通过 dequeue 方法调用 remove(0) 实现出队。运行该程序,输入 "A", "B", "C" 后,依次出队和查看,预期结果为控制台打印 "A" 和 "B"。这验证了 FIFO 的顺序特性,但需注意每次 remove(0) 都会触发数组拷贝。
立即学习“Java免费学习笔记(深入)”;
ArrayList 队列与 LinkedList 的性能对比
在实际开发中,如果必须使用列表结构实现队列,需要关注不同实现类的性能差异。ArrayList 的 remove(0) 操作涉及内存复制,而 LinkedList 基于双向链表,其 removeFirst() 操作仅涉及指针修改,时间复杂度为 O(1)。因此,对于高频的入队出队场景,LinkedList 是更优的选择,尽管它在随机访问和内存占用上不如 ArrayList。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class QueueComparison {
public static void main(String[] args) {
// 使用 ArrayList 模拟队列
ArrayList<Integer> arrayListQ = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
arrayListQ.add(i);
}
long start1 = System.currentTimeMillis();
while (!arrayListQ.isEmpty()) {
arrayListQ.remove(0);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList time: " + (end1 - start1) + "ms");
// 使用 LinkedList 模拟队列
Queue<Integer> linkedListQ = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
linkedListQ.add(i);
}
long start2 = System.currentTimeMillis();
while (!linkedListQ.isEmpty()) {
linkedListQ.poll();
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList time: " + (end2 - start2) + "ms");
}
}
这段代码通过批量插入和移除 10000 个整数来对比两者性能。预期结果是 LinkedList 的执行时间显著短于 ArrayList。这是因为 LinkedList 的 poll() 方法内部调用的是链表的头节点移除,无需移动其他元素。此对比证实了在队列场景下,数据结构的选择对性能有决定性影响。
ArrayList 队列在并发环境下的线程安全问题
当多个线程同时访问同一个 ArrayList 实例进行入队和出队操作时,会引发线程安全问题。ArrayList 不是线程安全的,并发修改可能导致 ConcurrentModificationException 或数据丢失。例如,两个线程同时调用 remove(0),可能获取到相同的元素,或者因内部状态不一致导致程序崩溃。因此,在生产环境中不应直接使用 ArrayList 作为并发队列。


















