在 C++ 中使用链表的堆栈数据结构
本文将解释如何在 C++ 中使用链表实现堆栈数据结构。
在 C++ 中使用单向链表实现堆栈数据结构
堆栈是程序中经常使用的抽象数据结构，它们最熟悉的用例是程序堆栈内存。
这种抽象数据类型有两个核心操作：push 和 pop。前者在其他元素的顶部进行元素插入，后者从堆栈中删除最近的元素。
堆栈被归类为 LIFO（后进先出）数据结构。堆栈可以用不同的方法实现，但我们将在本文中从一个单向链表构造它。
请注意，堆栈只需要跟踪最上面的元素，因为它是发生修改的地方。否则，它本质上是一个连续的数据集合，可能有也可能没有固定容量。后者取决于程序员做出的设计决定。
以下代码片段实现了一个可以在没有预定义容量限制的情况下增长的堆栈。首先，我们定义一个单向链表的节点，并将其 typedef 定义为 ListNode。然后我们声明一个 Stack 类并只包含一个数据成员来跟踪列表的顶部。
在这个例子中，我们将只实现 push 和 printNodes 函数。push 成员函数的操作类似于单向链表的插入操作，不同之处在于它将每个新元素添加到列表的头部。
尽管我们的 Stack 类具有初始化第一个元素的构造函数，这种糟糕的设计选择只是为了简化这篇介绍性文章的示例代码。
另一方面，printNodes 成员函数不是堆栈数据类型的基本函数，但它使演示更容易。它帮助我们验证我们的实现是否按预期工作。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void printNodes();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
前面的代码缺少 pop 操作，这是堆栈数据结构正常运行所必需的。由于我们实现了一个无限的堆栈并且只关心示例的简单性，因此内存分配是按需管理的。每个 pop 操作都会调用 delete 以释放顶部的前一个元素持有的内存。在实际场景中，人们应该更喜欢限制堆栈的容量或提前分配一些内存以获得更好的性能。
最后，我们需要一个析构函数，在对象超出范围后释放它。析构函数从 top 元素开始迭代，直到找到 nullptr，这表示堆栈的末尾。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void pop();
void printNodes();
~Stack();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::pop() {
auto tmp = top->next;
delete top;
top = tmp;
}
Stack::~Stack() {
struct ListNode *tmp = nullptr;
while (top) {
tmp = top->next;
delete top;
top = tmp;
}
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
cout << "/ ------------------------------ / " << endl;
s1.pop();
s1.pop();
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
/ ------------------------------ /
node 0 - data: Quantal
node 1 - data: Precise
node 2 - data: Xenial
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn