链表、栈与队列：结构、实现与转换
总结链表、栈、队列的基本特性、两种实现方式以及相互转换的经典问题。
1. 链表、栈、队列
1.1 链表 (Linked List)
链表是一种通过指针串联的线性数据结构，其节点在内存中无需连续存放。每个节点包含数据域和指向下一个节点的指针域。这种结构使得链表的插入和删除操作非常高效（时间复杂度为 O(1)），因为只需改变相邻节点的指针即可。然而，它的缺点是无法随机访问，查找某个元素必须从头节点开始遍历，时间复杂度为 O(n)。常见的链表有单向链表和支持双向遍历的双向链表。
plaintext
Head
│
▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Data: A │───>│ Data: B │───>│ Data: C │───> NULL
└─────────┘ └─────────┘ └─────────┘1.2 栈 (Stack)
栈是一种严格遵循 后进先出 (LIFO, Last-In, First-Out) 原则的数据结构。可以将其理解为一个只能从一端存取物品的容器。最后放入栈顶的元素，将最先被移出。其核心操作为 Push（入栈）和 Pop（出栈）。
plaintext
PUSH (C) POP
│ │
▼ ▼
┌─────────┐ ┌─────────┐ ┌─────────┐
│ C │ <── Top │ B │ <── Top │ B │ <── Top
├─────────┤ ├─────────┤ ├─────────┤
│ B │ │ A │ │ A │
├─────────┤ └─────────┘ └─────────┘
│ A │
└─────────┘
(入栈后) (出栈前) (出栈后)1.3 队列 (Queue)
队列是一种遵循 先进先出 (FIFO, First-In, First-Out) 原则的数据结构，如同现实生活中的排队。数据从队列的一端（队尾）进入，从另一端（队头）离开。其核心操作为 Enqueue（入队）和 Dequeue（出队）。
plaintext
ENQUEUE (C)
│
▼
Front Rear Front Rear
│ │ │ │
▼ ▼ ▼ ▼
┌───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
│ A │ B │ │ ───> │ A │ B │ C │ │ ───> │ B │ C │ │
└───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘
(入队前) (入队后) DEQUEUE (A)
(出队后)
2. 栈和队列的实现
栈和队列的实现方式可以有两种
- 链表实现
- 数组实现
2.0 双向链表 | 双端队列
要实现二者的链表实现，我们首先要写出双向链表的结构
双向链表的结点比普通的链表多了一个指向上一个结点的指针
java
// 双向链表的结点
public static class Node<V> {
public V value;
public Node<V> next;
public Node<V> last;
public Node(V value){
this.value = value;
}
}我们现在使链表允许从头部加，头部出，尾部加，尾部出，就构成了双端队列。
队列初始为空 head = tail = null
依次构造四个方法
添加不难，弹出时可能需要思考：我们在弹出时要用一个新的指针接管要弹出的头or尾结点，以免找不到。我们弹出返回结点时就不返回头尾结点了（因为头尾结点本身是队列的一部分），而是返回这个指针指向的被弹出结点。
当指针节点接管被弹出结点后，断干净被弹出结点和原队列的一切连接，同时还要移动头指针或尾指针
java
// 双端队列
public static class BothWaysQueue<V> {
Node<V> head;
Node<V> tail;
// 从头添加
public void headAdd (V val) {
Node<V> cur = new Node<>(val);
if (head == null) {
head = cur;
tail = head;
} else {
head.last = cur;
cur.next = head;
head = head.last;
}
}
// 从尾部添加
public void tailAdd (V val) {
Node<V> cur = new Node<>(val);
if (tail == null){
tail = cur;
head = tail;
} else {
tail.next = cur;
cur.last = tail;
tail = tail.next;
}
}
// 从头部弹出
public Node<V> headPop () {
if (head == null) {
return null;
}
Node<V> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur;
}
// 从尾部弹出
public Node<V> tailPop() {
if (tail == null) {
return null;
}
Node<V> cur = tail;
if (head == tail) {
head=null;
tail=null;
} else {
tail = tail.last;
cur.last = null;
tail.next = null;
}
return cur;
}
}2.1 栈的链表实现
基于上面的双端队列，我们可以采取从头部加并且从头部弹出，这样即可实现先入后出的栈结构（尾部加尾部出也可以）
java
// 双端队列实现栈
public static class BWQtoStack<V> {
public int size;
public BothWaysQueue<V> stack;
public BWQtoStack() {
stack = new BothWaysQueue<V>();
}
public void add(V val) {
stack.tailAdd(val);
size++;
}
public Node<V> pop() {
size--;
return stack.tailPop();
}
public boolean isEmpty() {
return stack.head == stack.tail;
}
public int size() {
return size;
}
}
2.2 队列的链表实现
这就更简单了，我们刚刚实现了双端队列，要实现普通队列只需要让头结点加，尾结点出即可。
java
public static class BWQtoQueue<V> {
public BothWaysQueue<V> queue;
public BWQtoQueue () {
queue = new BothWaysQueue<>();
}
public void add (V val) {
queue.headAdd(val);
}
public Node<V> pop() {
return queue.tailPop();
}
}
2.3 栈的数组实现
plaintext
ArrayStack 内部结构 (limit = 5)
+-----------------+
| (空) | Index 4
+-----------------+
| (空) | Index 3
+-----------------+
| "C" | Index 2 <-- top 指针 (当前值为 2)
+-----------------+
| "B" | Index 1
+-----------------+
| "A" | Index 0
+-----------------+栈用数组实现很简单，我们只需要用到三个成员变量
- top：初始值为-1，指向栈顶元素的位置
- limit：标明数组大小
- 数组stack：存储核心
当我们加入元素的时候，先将top++，再把元素加到对应的stack[top]
弹出栈顶元素的时候，返回栈顶元素，再top--即可
java
public class ArrayStack<V> {
private int top;
private final int limit;
private final V[] stack;
// 初始化栈
public ArrayStack (int limit) {
this.top = -1;
this.limit = limit;
stack = (V[]) new Object[limit];
}
// 入栈
public void push(V val) {
if (top == limit - 1) {
throw new RuntimeException("栈已经满了！");
}
top++;
stack[top] = val;
}
// 出栈
public V pop() {
if (isEmpty()) {
throw new RuntimeException("栈内没有任何元素");
}
top--;
return stack[top + 1];
}
public boolean isEmpty() {
return top == -1;
}
}
2.4 队列的数组实现
要用数组实现，我们需要循环利用数组空间
我们先设置几个成员变量
- limit：标记数组的最大长度
- pushIdx：用于标记新加入的元素该放的位置
- popIdx：用于记录弹出元素的位置
- size：这个很关键，记录队列中有效数据有多少个，我们不再思考两个Idx的关系来判断什么时候可以加可以不加，而是根据size来判断，size == limit则满，size == 0 即空
- 数组queue：存储结构
java
public class ArrayQueue<V> {
private final int limit;
private int pushIdx;
private int popIdx;
private int size;
private V[] queue;
public ArrayQueue (int limit) {
this.limit = limit;
pushIdx = 0;
popIdx = 0;
size = 0;
queue = (V[]) new Object[limit];
}
}接下来是入队，判断合法性后，我们让size++，直接根据pushIdx添加元素即可，添加后再将其向后移动
出队也一样，判断合法性后，我们让size--，直接根据popIdx弹出元素即可，弹出后再将其向后移动
一定要操纵size的变化
java
public class ArrayQueue<V> {
// 入队
public void push (V val) {
if (size == limit) {
throw new RuntimeException("队列已满！");
}
size++;
queue[pushIdx] = val;
pushIdx = nextPos(pushIdx);
}
// 出队
public V pop() {
if (size == 0) {
throw new RuntimeException("队列为空！");
}
size--;
V cur = queue[popIdx];
popIdx = nextPos(popIdx);
return cur;
}
}将索引向后移动的过程，涉及到边界问题，不能简单+1，我们应该将数组考虑成循环的结构，也就是收尾相连，当索引在数组尾部，+1要越界时，我们将索引的后移操作变为移动到头部，即可实现首尾相接
java
public class ArrayQueue<V> {
private int nextPos(int curIdx) {
if (curIdx == limit - 1) {
return 0;
} else {
return curIdx + 1;
}
}
public int size() {
return size;
}
}
3. 相关题目
3.1 返回栈中最小的值
要求：实现有getMin()功能的栈，用时间复杂度O(1)，即该方法不遍历栈可获得当前栈的最小值
思路：
我们采取空间换时间的方法，运用两个栈来实现这个类，一个存储数据的栈，一个存储当前最小值的栈（栈顶元素表示当前栈的最小值）。
每当一个数据压入或弹出数据栈的时候，最小栈要同步变化
数据压入：
- 如果没有元素，两栈压入同样的元素。
- 如果有元素，判断当前新元素是否比最小栈栈顶元素小，如果没有他小则复制一份栈顶元素加入最小栈，如果比最小栈栈顶元素小则新数据压入最小栈
数据弹出则同步弹出
getMin()方法则只用peek()最小栈栈顶元素即可
plaintext
<-- 栈顶
stack stackMin
| 4 | | 3 |
| 3 | | 3 |
| 5 | | 5 |
|---| |---| 代码：
java
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> stackMin;
public MinStack() {
stack = new Stack<>();
stackMin = new Stack<>();
}
public void push(int val) {
if (stackMin.isEmpty()) {
stackMin.push(val);
} else {
int curMin = Math.min(val, stackMin.peek());
stackMin.push(curMin);
}
stack.push(val);
}
public int pop() {
int val = stack.pop();
stackMin.pop();
return val;
}
private int getMin() {
return stackMin.peek();
}
public boolean isEmpty() {
return stack.isEmpty();
}
public int size() {
return stack.size();
}
}
3.2 用栈实现队列 ※
要求：只能使用栈，实现一个类，该类能实现队列的出入队操作
思路：
（图解在代码后）
我们还是使用两个栈，一个push栈，一个pop栈。
当我们正常添加元素时，向push栈内push元素即可
依据队列的特性，先入先出，我们如果想要弹出元素，就需要将push栈的所有元素反着放，于是我们想到将push栈的元素依次弹出到pop栈内，这样pop栈存储的就是反着放的push栈
于是pop栈内顶上的元素就是先加入的元素了，在pop栈内弹出就满足了队列先入先出的规则
准备一个方法pushToPop，用于在pop栈空时，将push栈内元素全部倒入pop栈中
我们每在要用pop方法弹元素时调用一次pushToPop，从pop栈弹就可以了
注意：pop栈的元素我们不需要倒回push栈，因为这没有意义
代码：
java
public class StackToQueue {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public StackToQueue() {
pushStack = new Stack<>();
popStack = new Stack<>();
}
public void push(int val) {
pushStack.push(val);
}
public void pushToPop() {
if (popStack.isEmpty()) {
while (!pushStack.isEmpty()) {
popStack.push(pushStack.pop());
}
}
}
public int pop(){
pushToPop();
if (popStack.isEmpty()) {
throw new RuntimeException("队列为空");
}
return popStack.pop();
}
}图解：
plaintext
+----------------------------------------------------------------------+
| 两栈实现队列图解 |
+----------------------------------------------------------------------+
| |
| 操作 1: 入队 (Push) |
| 将元素 1, 2, 3 依次推入 `pushStack`。 |
| |
| pushStack (入) popStack (出) |
| +-------+ +-------+ |
| | 3 | <-- 新元素 | | |
| +-------+ +-------+ |
| | 2 | | | |
| +-------+ +-------+ |
| | 1 | | | |
| +-------+ +-------+ |
| |
|----------------------------------------------------------------------|
| |
| 操作 2: 首次出队 (Pop) |
| 1. `popStack` 为空，触发 `pushToPop` 方法。 |
| 2. `pushStack` 的元素依次弹出并压入 `popStack`。 |
| |
| pushStack (入) popStack (出) |
| +-------+ +-------+ |
| | | -- 3 pop --> | 1 | |
| +-------+ +-------+ |
| | | -- 2 pop --> | 2 | |
| +-------+ +-------+ |
| | | -- 1 pop --> | 3 | <-- 顺序反转 |
| +-------+ +-------+ |
| |
| 3. 从 `popStack` 顶部弹出元素 `1`，实现“先进先出”。 |
| |
| pushStack (入) popStack (出) |
| +-------+ +-------+ |
| | | | | <-- 1 被弹出 |
| +-------+ +-------+ |
| | | | 2 | |
| +-------+ +-------+ |
| | | | 3 | |
| +-------+ +-------+ |
| |
|----------------------------------------------------------------------|
| |
| 操作 3: 再次入队 (Push 4) |
| 新元素 `4` 仍然进入 `pushStack`。`popStack` 保持不变。 |
| |
| pushStack (入) popStack (出) |
| +-------+ +-------+ |
| | | <-- 新元素 | | |
| +-------+ +-------+ |
| | | | 2 | |
| +-------+ +-------+ |
| | 4 | | 3 | |
| +-------+ +-------+ |
| |
|----------------------------------------------------------------------|
| |
| 操作 4: 再次出队 (Pop) |
| `popStack` 不为空，直接从顶部弹出 `2`，无需移动数据。 |
| |
| pushStack (入) popStack (出) |
| +-------+ +-------+ |
| | 4 | | | <-- 2 被弹出 |
| +-------+ +-------+ |
| | | | | |
| +-------+ +-------+ |
| | | | 3 | |
| +-------+ +-------+ |
| |
| 核心思想: |
| - 所有元素从 `pushStack` 入。 |
| - 所有元素从 `popStack` 出。 |
| - 仅当 `popStack` 为空时，才将 `pushStack` 的数据一次性倒入， |
| 这个“倒入”操作完成了顺序的反转。 |
+----------------------------------------------------------------------+
3.3 用队列实现栈 ※
要求：只能使用队列，实现一个类，该类能实现栈的出入栈操作
思路：
有了上面两道题的启示，我们同样可以使用两个队列：一个queue，一个help
由于队列是先入先出，我们不能来回导来颠覆先后顺序
要弹出元素时，我们可以将queue队列中的元素依次加入到help中，加到只剩最后一个元素，那么这最后一个元素就是我们栈要弹出的元素，即是最后加入的。
完成后我们将help和queue对调，保证代码其他方法的正确性
代码：
java
public class QueueToStack {
private Queue<Integer> queue;
private Queue<Integer> help;
public QueueToStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(int val) {
queue.add(val);
}
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("栈是空的！");
}
while (queue.size() > 1) {
help.add(queue.poll());
}
int cur = queue.poll();
Queue<Integer> temp = help;
help = queue;
queue = temp;
return cur;
}
}图解：
plaintext
1. 依次执行 push(1), push(2), push(3):
操作后状态:
queue: [1, 2, 3] <-- 元素按顺序入队
help: []
----------------------------------------------------------------------------
2. pop() 操作:
目标: 取出栈顶元素 (也就是队列的最后一个元素 3)
a. [循环] 将 queue 中的元素逐个出队，并加入 help 队列，直到 queue 只剩一个元素。
- 第一次循环: queue.poll() -> 1
queue: [2, 3]
help: [1]
- 第二次循环: queue.poll() -> 2
queue: [3]
help: [1, 2]
b. [获取] queue 中剩下的最后一个元素就是目标元素。
- cur = queue.poll() -> 3
queue: []
help: [1, 2]
返回: 3 (此时已成功模拟 "后进先出")
c. [交换] 交换 queue 和 help 的引用，为下一次操作做准备。
(help 变成了新的主队列)
queue: [1, 2]
help: []