C++ のリンクリストを使用したスタックデータ構造
この記事では、C++ でリンクリストを使用してスタックデータ構造を実装する方法について説明します。
C++ で単一リンクリストを使用してスタックデータ構造を実装する
スタックは、プログラムで頻繁に使用される抽象的なデータ構造であり、最もよく知られているユースケースはプログラムスタックメモリです。
この抽象データ型には、プッシュとポップの 2つのコア操作があります。前者は他の要素の上に要素の挿入を実行し、後者はスタックから最新の要素を削除します。
スタックは、LIFO（後入れ先出し）データ構造として分類されます。スタックはさまざまな方法で実装できますが、この記事では、単一リンクリストからスタックを構築します。
スタックは、変更が発生する場所であるため、最上位の要素を追跡するだけでよいことに注意してください。それ以外の場合、それは本質的に、固定容量を持つ場合と持たない場合があるデータの順次収集です。後者は、プログラマーが行う設計上の決定に依存します。
次のコードスニペットは、事前定義された容量制限なしで拡張できるスタックを実装します。最初に、単一リンクリストのノードを定義し、それを typedef として ListNode として定義します。次に、Stack クラスを宣言し、リストの先頭を追跡するために 1つのデータメンバーのみを含めます。
この例では、push 関数と printNodes 関数のみを実装します。push メンバー関数は、リストの先頭にすべての新しい要素を追加することを除いて、単一リンクリストの挿入操作と同様に動作します。
Stack クラスには最初の要素を初期化するコンストラクターがありますが、この不適切な設計の選択は、この紹介記事のサンプルコードを単純化するためにのみ採用されています。
一方、printNodes メンバー関数はスタックデータ型に必須の関数ではありませんが、デモンストレーションが容易になります。これは、実装が意図したとおりに機能することを確認するのに役立ちます。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
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 を呼び出して、上の前の要素によって保持されていたメモリを解放します。実際のシナリオでは、パフォーマンスを向上させるために、スタックの容量を制限するか、事前にメモリを割り当てることをお勧めします。
最後に、スコープから外れた後にオブジェクトを解放するデストラクタが必要です。デストラクタ関数は、スタックの終わりを示す nullptr が見つかるまで、top 要素から繰り返します。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
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
