在软件开发的广阔天地中，数据结构是我们构建高效算法的基石。作为一名开发者，我们每天都在与不同的数据结构打交道，而栈和链表无疑是其中最基础也最重要的两个角色。你是否思考过这样一个问题：我们如何将这两种结构的优势结合起来，构建一个既灵活又高效的栈？
通常，当我们提到栈，脑海中浮现的第一个实现方案往往是数组。然而，数组在动态扩容时往往伴随着高昂的性能成本。在这篇文章中，我们将一起探索一种更优雅的方案——利用双向链表来实现栈。我们将通过详细的代码示例和原理剖析，带你领略这种实现方式的精妙之处，并帮助你理解为什么在某些场景下，它是优于数组栈的最佳选择。
为什么要用双向链表实现栈？
在深入代码之前，我们先来聊聊“为什么”。栈遵循后进先出的原则，这意味着我们主要关心的是栈顶的元素。
- 数组栈的痛点：数组虽然提供了快速的随机访问，但它的内存空间是连续的。当栈满需要扩容时，我们必须申请新的更大内存块并将数据一一复制，这在性能上是极大的浪费。此外，如果我们在栈满时无法申请到连续的大内存，程序甚至会崩溃。
- 双向链表的优势：双向链表通过指针连接各个节点，不需要连续的内存空间。这意味着:
1. 动态扩容无需拷贝：我们可以随时在堆上分配新节点，无需担心搬运旧数据的开销。
2. 双向遍历能力：虽然栈通常只操作栈顶，但双向链表赋予了我们在不改变栈结构的前提下，反向遍历数据的能力（例如在调试、历史记录回溯等场景中非常有用）。
基础构建：定义节点结构
首先，我们需要定义双向链表中的“节点”。这个节点不仅要存储数据，还需要持有指向“前一个节点”和“后一个节点”的指针。
#### 节点类的定义
为了让我们的代码具备多语言的普适性，我们定义了一个标准的 Node 类。它包含三个核心部分：数据域、前驱指针和后继指针。
让我们看看不同语言下具体的实现方式：
C++ 实现
class Node {
public:
int data;
Node* next;
Node* prev;
// 构造函数：初始化节点及指针
Node(int val) {
data = val;
next = nullptr; // 新节点的后继暂时为空
prev = nullptr; // 新节点的前驱暂时为空
}
};
Java 实现
class Node {
public int data;
public Node next;
public Node prev;
public Node(int val) {
data = val;
next = null;
prev = null;
}
}
Python 实现
class Node:
def __init__(self, val):
self.data = val
self.next = None
self.prev = None
C# 实现
class Node {
public int data;
public Node next;
public Node prev;
public Node(int val) {
data = val;
next = null;
prev = null;
}
}
JavaScript 实现
class Node {
constructor(val) {
this.data = val;
this.next = null;
this.prev = null;
}
}
核心操作之一：Push() – 入栈
入栈是栈最核心的操作，意味着要在结构的顶部添加一个新元素。在使用双向链表时，我们通常将链表的头部或尾部作为栈顶。在本文的实现中，我们将链表的尾部视为栈顶，这样操作起来非常直观。
#### 实现逻辑
我们需要处理两种情况，这就像是我们在搭建积木塔：
- 情况一：栈是空的（这是第一个积木）
* 我们创建一个新节点。
* 因为它是唯一的一个节点，所以它的 INLINECODE901481c1 和 INLINECODEc3b71bd3 都指向 INLINECODE0a97a844（或 INLINECODE82b72851）。
* 最重要的是，我们需要记录下这个节点，它是我们的“起始节点”也是当前的“栈顶节点”。
- 情况二：栈不为空（已有积木）
* 创建新节点，存入数据。
* 将当前栈顶的 next 指针指向新节点（建立向后连接）。
* 将新节点的 prev 指针指向当前栈顶（建立向前连接，这是双向链表的精髓）。
* 最后，更新全局的 top 指针，让它指向这个新加入的节点。
#### 代码实战
C++ 实现
void push(int val) {
Node* h = new Node(val);
if (isEmpty()) {
// 如果栈为空，新节点即为栈顶和起始节点
h->prev = nullptr;
h->next = nullptr;
start = h;
top = h;
}
else {
// 将新节点链接到当前的栈顶之后
top->next = h;
h->next = nullptr;
h->prev = top;
// 更新栈顶指针
top = h;
}
}
Java 实现
void push(int d) {
Node n = new Node();
n.data = d;
if (isEmpty()) {
// 初始化状态，前驱后继均为空
n.prev = null;
n.next = null;
start = n;
top = n;
} else {
// 链接逻辑
top.next = n;
n.next = null;
n.prev = top;
top = n;
}
}
Python 实现
def push(self, element):
newP = Node(element) # 实例化新节点
if self.start is None:
# 空栈处理
self.start = self.top = newP
return
# 链接新节点到栈顶
newP.prev = self.top
self.top.next = newP
self.top = newP
核心操作之二：Pop() – 出栈
出栈操作意味着我们要移除栈顶的元素，并返回它的值（如果需要）。这就像是从积木塔顶端取下一块积木。在使用双向链表时，这个操作非常高效，因为我们始终持有 top 指针。
#### 实现逻辑
- 检查下溢：首先，我们得看看栈是不是空的。如果是空的，我们就没法取东西了，需要提示用户。
- 处理最后一个节点：如果栈里只有一个节点（INLINECODE2c57edfd），移除它之后，栈就空了，我们需要重置 INLINECODEa208c66a 和 INLINECODE413865ca 为 INLINECODEda6a9e83。
- 常规情况：
* 我们需要将新的栈顶（即原栈顶的前一个节点）的 INLINECODEfb6461ba 指针断开（设为 INLINECODE50916857）。这一步是为了让被移除的节点彻底脱离链表。
* 将 INLINECODE448874ad 指针向前移动一位 (INLINECODE38eef81d)。
* （注：在 C++ 等语言中，记得释放被移除节点的内存，防止内存泄漏）。
#### 代码实战
C++ 实现
void pop() {
Node* n = top; // 暂存待删除的节点
if (isEmpty()) {
printf("Stack is empty");
}
else if (top == start) {
// 栈中仅有一个元素的情况
top = nullptr;
start = nullptr;
free(n); // 释放内存
}
else {
// 断开原栈顶的连接
top->prev->next = nullptr;
// 移动栈顶指针
top = n->prev;
free(n); // 释放内存
}
}
Java 实现
void pop() {
Node n = top;
if (isEmpty()) {
System.out.println("Stack is empty");
} else if (top == start) {
// 仅有一个元素
top = null;
start = null;
} else {
// 常规出栈逻辑
top.prev.next = null;
top = n.prev;
// 垃圾回收器会自动处理内存回收
}
}
Python 实现
def pop(self):
if self.isEmpty():
print(‘List is Empty‘)
return
self.top = self.top.prev
if self.top is not None:
self.top.next = None
# 注意：Python 会有垃圾回收机制自动清理无引用对象
进阶技巧与实战建议
除了基础的 Push 和 Pop，一个完整的栈通常还需要其他辅助功能。让我们看看如何实现它们，以及在实际开发中的一些注意事项。
#### 1. Peek 操作（查看栈顶）
有时你只想看看栈顶是什么，而不想把它移除。这在表达式求值或解析器中非常常见。
def peek(self):
if self.isEmpty():
return None
return self.top.data
#### 2. 空栈检查与大小
虽然简单，但健壮的代码总是时刻检查状态。
- isEmpty(): 检查 INLINECODE9d77256f 是否为 INLINECODE85b00c35。
- size(): 由于我们没有维护一个计数变量，要获取栈的大小，我们需要从头遍历到尾部。如果你需要频繁获取栈的大小，建议在类中增加一个
count变量，在 Push 时加 1，在 Pop 时减 1。
常见陷阱与解决方案
在实现过程中，作为开发者，我们要时刻警惕以下几个陷阱：
- 内存泄漏 (C/C++ 特有)：在 INLINECODE8670c57b 操作中，仅仅移动指针是不够的。原来的节点还在内存中挂着，如果不调用 INLINECODE9d03c0cc 或 INLINECODEa7d20f54，长此以往会导致内存耗尽。这就是为什么在上面的 C++ 代码中我们显式地调用了 INLINECODEfbe8b656。
- 空指针异常：在执行 INLINECODE034c010c 这类操作前，必须确保 INLINECODE0708c010 不是 INLINECODEe9519879，否则程序会崩溃。这就是为什么我们在操作前总是先调用 INLINECODE74ca5064 进行判断。
- 指针丢失：在更新指针顺序时，如果先写 INLINECODEe55b28cc，然后再去尝试修改 INLINECODE5010dd9d，你就丢失了原来真正的栈顶节点。经验法则：先记录要删除的节点，再修改邻居的指针，最后才移动主指针。
总结
通过这篇文章，我们深入探讨了如何利用双向链表来实现栈这一基础数据结构。相比于数组实现，双向链表虽然牺牲了一些访问特定位置的效率，但在动态扩容和内存利用上提供了更大的灵活性。
我们学习了如何定义节点，如何安全地实现 INLINECODE96866a03 和 INLINECODEefa44bc2 操作，以及在编码过程中需要注意的内存管理和边界条件问题。掌握这种实现方式，不仅能帮助你应对面试中的算法题，更能让你在处理实际的动态数据流问题时，多一种高效的解决思路。
希望这篇文章能对你有所帮助。接下来，你可以尝试动手实现一个完整的 INLINECODE0fae05c1 类，并尝试添加 INLINECODEdd23838c 方法来正向或反向打印栈中的所有元素，以此来巩固你对双向链表指针操作的理解。