在 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