当前位置：首页 > news >正文

List、Queue、Deque、Stack常用方法总结

news 2025/6/18 15:19:37

Java 中几个常见的线性数据结构的 方法总结与对比，包括：

List（ArrayList、LinkedList）
Queue（LinkedList、PriorityQueue）
Deque（ArrayDeque、LinkedList）
Stack（传统 Stack 类，和推荐的 Deque 实现）

一、接口/类总览

接口/类	常见实现类	特点
`List<E>`	`ArrayList`, `LinkedList`	有序、可重复、索引访问
`Queue<E>`	`LinkedList`, `PriorityQueue`	FIFO 队列
`Deque<E>`	`LinkedList`, `ArrayDeque`	双端队列，支持栈和队列
`Stack<E>`	`Stack`（继承 `Vector`）	LIFO 栈（已不推荐）

二、常用方法对比

方法名	`List`	`Queue`	`Deque`	`Stack`
`add(E)`	✅ 尾部添加	✅ 尾部添加	✅ 尾部添加	✅ 尾部添加
`add(int, E)`	✅ 指定位置插入	❌	❌	❌
`addFirst(E)`	❌（ArrayList） ✅（LinkedList）	❌	✅	❌
`addLast(E)`	❌（ArrayList） ✅（LinkedList）	❌	✅	❌
`offer(E)`	❌	✅（添加）	✅	❌
`offerFirst(E)`	❌	❌	✅	❌
`offerLast(E)`	❌	❌	✅	❌
`get(int)`	✅	❌	❌	✅（search用）
`remove()`	❌	✅（移除队首）	✅（移除队首）	✅（移除栈顶）
`poll()`	❌	✅（移除队首）	✅	❌
`pollFirst()`	❌	❌	✅	❌
`pollLast()`	❌	❌	✅	❌
`peek()`	❌	✅（查看队首）	✅	✅（查看栈顶）
`peekFirst()`	❌	❌	✅	❌
`peekLast()`	❌	❌	✅	❌
`pop()`	❌	❌	✅（从头）	✅
`push(E)`	❌	❌	✅（加头）	✅
`isEmpty()`	✅	✅	✅	✅
`clear()`	✅	✅	✅	✅
`contains(E)`	✅	✅	✅	✅
`size()`	✅	✅	✅	✅

三、队列和栈的实现

//队列
Queue<Integer> queue = new LinkedList<>();
//deque实现队列
Deque<Integer>queue = new ArrayDeque<>();
//栈
Stack<Integer>stack = new Stack<>();
//deque实现栈
Deque<Integer>stack = new ArrayDeque<>();

四、`LinkedList`和 `ArrayList`底层结构对比

特性	`ArrayList`	`LinkedList`
底层结构	动态数组（连续内存）	双向链表（非连续内存）
查询效率	✅ O(1) 直接索引	❌ O(n) 从头/尾遍历
插入效率（中间）	❌ O(n)（需要移动元素）	✅ O(1)（节点引用调整）
插入效率（尾部）	✅ 摊销 O(1)	✅ O(1)
删除效率（中间）	❌ O(n)	✅ O(1)（已定位）
内存使用	少（仅数据）	多（每个节点额外两个指针）