LinkedList实现队列和栈的技巧-java教程-PHP中文网

LinkedList实现队列和栈的技巧

P粉602998670

发布： 2025-09-22 16:45:01

原创

345人浏览过

使用LinkedList可高效实现栈和队列：栈利用addFirst()/removeFirst()实现LIFO，队列通过addLast()/removeFirst()实现FIFO，操作均O(1)时间复杂度，无需扩容且内存动态分配。

linkedlist实现队列和栈的技巧

用

LinkedList

登录后复制

实现队列和栈，核心在于巧妙利用其双向链表的特性，通过在头部或尾部进行高效的添加和删除操作，从而精确模拟这两种数据结构各自的先进先出（FIFO）和后进先出（LIFO）行为。这避免了数组在中间插入或删除元素时可能带来的高昂开销，也省去了扩容的烦恼。

直接输出解决方案即可

解决方案

LinkedList

登录后复制

作为一种双向链表，在Java等语言中，天然提供了在链表两端进行操作的方法，例如

addFirst()

登录后复制

、

removeFirst()

登录后复制

、

addLast()

登录后复制

、

removeLast()

登录后复制

等。正是这些方法，使得它成为实现队列和栈的理想基石。

对于栈（Stack），其核心是LIFO（Last In, First Out）原则，即最后进入的元素最先出去。我们可以将

LinkedList

登录后复制

的一端（比如头部或尾部）固定作为栈的“顶部”。

入栈 (Push)：将元素添加到链表的“顶部”。如果选择链表头部作为栈顶，则使用
```
addFirst(E e)
```
登录后复制
。如果选择链表尾部作为栈顶，则使用
```
addLast(E e)
```
登录后复制
。我个人倾向于使用
```
addFirst()
```
登录后复制
，感觉更直观，就像往一叠盘子顶部放盘子。
出栈 (Pop)：从链表的“顶部”移除元素。对应
```
removeFirst()
```
登录后复制
（如果栈顶是头部）或
```
removeLast()
```
登录后复制
（如果栈顶是尾部）。
查看栈顶元素 (Peek)：查看但不移除链表“顶部”的元素。对应
```
getFirst()
```
登录后复制
或
```
getLast()
```
登录后复制
。

对于队列（Queue），其核心是FIFO（First In, First Out）原则，即最先进入的元素最先出去。这通常意味着元素从一端进入，从另一端离开。

入队 (Enqueue)：将元素添加到队列的“尾部”。使用
```
addLast(E e)
```
登录后复制
。
出队 (Dequeue)：从队列的“头部”移除元素。使用
```
removeFirst()
```
登录后复制
。
查看队首元素 (Peek)：查看但不移除队列“头部”的元素。使用
```
getFirst()
```
登录后复制
。

这种利用

LinkedList

登录后复制

两端操作的策略，使得入队、出队、入栈、出栈操作的时间复杂度都保持在O(1)，非常高效。

为什么LinkedList是实现队列和栈的理想选择？

在我看来，

LinkedList

登录后复制

在实现队列和栈时，简直是“量身定制”的。它之所以被认为是理想选择，主要有几个深层原因。首先，最直接的就是它的O(1)时间复杂度特性。无论是向链表头部还是尾部添加或删除元素，都只需要修改少数几个节点的指针，这与数组在中间插入或删除元素时需要移动大量元素的开销形成了鲜明对比。想象一下，如果用数组实现队列，每次出队都要将所有后续元素向前移动一位，那效率可想而知。而

LinkedList

登录后复制

则完全避免了这个问题。

其次，

LinkedList

登录后复制

的动态扩容特性也是一个巨大的优势。数组在容量不足时需要进行扩容，这涉及创建一个更大的新数组并将旧数组的元素复制过去，这个过程是耗时的。而

LinkedList

登录后复制

则没有固定容量的限制，它会根据需要动态地创建和销毁节点，天然支持动态增长，这在处理不确定大小的数据流时尤其方便，避免了预估容量的烦恼。

巧文书

巧文书是一款AI写标书、AI写方案的产品。通过自研的先进AI大模型，精准解析招标文件，智能生成投标内容。

查看详情

再者，从内存使用的角度看，虽然每个节点会额外存储前后节点的引用，导致单个元素占用内存稍多于数组，但在某些场景下，这种分散的内存分配反而更灵活。它不会像数组那样要求一块连续的内存空间，这对于内存碎片化严重的系统来说，可能更容易分配到所需空间。当然，这也不是绝对的，具体还得看应用场景和数据量。但总体来说，

LinkedList

登录后复制

在处理头部和尾部操作的效率上，确实是无与伦比的。

使用LinkedList实现栈：具体操作与考量

当我们需要一个栈时，

LinkedList

登录后复制

提供了一个非常简洁且高效的实现途径。我通常会这样操作：

1. 入栈 (Push) 将元素压入栈顶。在

LinkedList

登录后复制

中，我们可以选择

addFirst(E e)

登录后复制

。

// 假设有一个LinkedList实例
LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Element A"); // 栈：[A]
stack.addFirst("Element B"); // 栈：[B, A]
stack.addFirst("Element C"); // 栈：[C, B, A]

登录后复制

这里，链表的头部被我们定义为栈的“顶部”。

2. 出栈 (Pop) 从栈顶移除并返回元素。对应

removeFirst()

登录后复制

。

String poppedElement = stack.removeFirst(); // 移除并返回 "C"，栈：[B, A]
// 如果栈为空，调用removeFirst()会抛出NoSuchElementException。
// 实际使用时，通常会先检查isEmpty()。

登录后复制

3. 查看栈顶元素 (Peek) 查看栈顶元素，但不移除。对应

getFirst()

登录后复制

。

String topElement = stack.getFirst(); // 返回 "B"，栈：[B, A]
// 同样，如果栈为空，会抛出NoSuchElementException。

登录后复制

4. 判断栈是否为空 (isEmpty) 直接使用

isEmpty()

登录后复制

方法。

boolean isEmpty = stack.isEmpty(); // 返回false

登录后复制

考量点：

异常处理：
```
removeFirst()
```
登录后复制
和
```
getFirst()
```
登录后复制
在链表为空时会抛出
```
NoSuchElementException
```
登录后复制
。在实际应用中，我们通常会在调用这些方法之前先检查
```
isEmpty()
```
登录后复制
，或者使用
```
pollFirst()
```
登录后复制
/
```
peekFirst()
```
登录后复制
等返回
```
null
```
登录后复制
而非抛出异常的方法（这些方法通常用于队列接口，但
```
LinkedList
```
登录后复制
也提供了）。
线程安全：
```
LinkedList
```
登录后复制
本身不是线程安全的。如果在多线程环境中使用，需要外部同步机制，或者考虑使用
```
Collections.synchronizedList(new LinkedList<>())
```
登录后复制
，或者直接使用
```
java.util.concurrent
```
登录后复制
包下的并发数据结构。这其实是一个普遍的问题，不仅仅是
```
LinkedList
```
登录后复制
。

使用LinkedList实现队列：具体操作与性能分析

对于队列，

LinkedList

登录后复制

同样表现出色，尤其是在处理大量元素的入队和出队操作时。

1. 入队 (Enqueue) 将元素添加到队列的尾部。使用

addLast(E e)

登录后复制

。

// 假设有一个LinkedList实例
LinkedList<Integer> queue = new LinkedList<>();
queue.addLast(10); // 队列：[10]
queue.addLast(20); // 队列：[10, 20]
queue.addLast(30); // 队列：[10, 20, 30]

登录后复制

这里，链表的尾部是新元素的入口，头部是元素的出口。

2. 出队 (Dequeue) 从队列的头部移除并返回元素。使用

removeFirst()

登录后复制

。

Integer dequeuedElement = queue.removeFirst(); // 移除并返回 10，队列：[20, 30]
// 同样，如果队列为空，removeFirst()会抛出NoSuchElementException。

登录后复制

3. 查看队首元素 (Peek) 查看队首元素，但不移除。使用

getFirst()

登录后复制

。

Integer frontElement = queue.getFirst(); // 返回 20，队列：[20, 30]

登录后复制

4. 判断队列是否为空 (isEmpty) 直接使用

isEmpty()

登录后复制

方法。

boolean isEmpty = queue.isEmpty(); // 返回false

登录后复制

性能分析：

时间复杂度：如前所述，所有核心操作（入队、出队、查看）都是O(1)。这是
```
LinkedList
```
登录后复制
作为队列实现的最大优势。
与
ArrayDeque
登录后复制
的比较：虽然
```
LinkedList
```
登录后复制
在理论上提供了O(1)的性能，但在实际应用中，
```
java.util.ArrayDeque
```
登录后复制
在很多情况下可能表现更好。
```
ArrayDeque
```
登录后复制
是基于数组实现的双端队列，它在内部使用循环数组，避免了
```
LinkedList
```
登录后复制
每个节点额外的内存开销，并且由于数据在内存中是连续存储的，CPU缓存命中率更高。对于基本数据类型，
```
ArrayDeque
```
登录后复制
避免了装箱拆箱的开销。所以，如果对性能有极致要求，并且数据量不是特别巨大以至于频繁扩容成为瓶颈，
```
ArrayDeque
```
登录后复制
往往是更优的选择。但对于需要频繁在中间进行插入删除操作，或者内存分配不敏感的场景，
```
LinkedList
```
登录后复制
的灵活性依然有其价值。我个人在选择时，如果不是特别明确需要链表的特性，通常会先考虑
```
ArrayDeque
```
登录后复制
，因为它在大多数常见场景下，综合性能更胜一筹。
内存开销：
```
LinkedList
```
登录后复制
的每个节点除了存储元素本身，还需要存储指向前一个和后一个节点的引用。这意味着对于相同数量的元素，
```
LinkedList
```
登录后复制
通常会比
```
ArrayDeque
```
登录后复制
占用更多的内存。这是一个需要权衡的因素。