C++ でリンクリストを使用してキューデータ構造を実装する
この記事では、C++ でリンクリストを使用してキューデータ構造を実装する方法について説明します。
C++ で単一リンクリストを使用してキューデータ構造を実装する
キューは、FIFO（先入れ先出し）方式で要素を管理するデータ構造であるため、最初に追加された要素が最初にキューから削除されます。
一般に、キューデータ構造の挿入操作と削除操作は、それぞれエンキューとデキューと呼ばれます。抽象キューは、さまざまなメソッドとデータ構造を使用して実装できます。通常、新しい要素が追加される側はフロントと呼ばれ、要素が削除される側はキューの後ろと呼ばれます。
次の例では、データオブジェクトを格納するノードと次のノードへのポインタで構成される単一リンクリストを使用してキューを実装します。この場合、簡単にするために単一の string オブジェクトでデータオブジェクトを表すことを選択しましたが、最適なノード構造を設計するのはプログラマーの責任です。
次に、Queue と呼ばれるクラスを定義できます。これには、front、back、size の 3つのデータメンバーが含まれます。前者の 2つは自明ですが、後者はキューの現在の要素数を示します。キューデータ構造には、制限なしと制限付きの 2つの主要なバリエーションがあり、前者は使用可能なメモリができるまで要素を追加できます。一方、制限付きキューは、固定数の要素のみを格納するように設計されています。
この記事では、制限のないキューを設計しますが、読者は、指定されたコードサンプルを少し変更するだけで、制限のあるキューを直感的に開発できます。無制限のキューを最初から実装しているため、キューが大きくなるにつれて動的メモリ割り当てを管理する必要があります。したがって、enQueue および deQueue メンバー関数には、new および delete 演算子が含まれます。キューのこの実装は、効率的な実装を目的としたものではなく、一般的なこのデータ構造の基本的な動作メカニズムを示していることに注意してください。
Queue には 2つのコンストラクターがあり、そのうちの 1つは string 値の initializer_list を取り、enQueue 関数を複数回呼び出して Queue オブジェクトを構築します。各 enQueue 呼び出しは size メンバーをインクリメントし、必要に応じて、クラスのユーザーは getSize 関数を使用してその値を取得できます。また、指定された Queue オブジェクトの内容を検査するためのヘルパー関数 printNodes を実装しました。この関数は、実際のシナリオで定義する必要はありませんが、テストとデバッグには役立ちます。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
q1.enQueue("Xenial");
q1.enQueue("Bionic");
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
出力：
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
queue size = 4
/ ------------------------------ /
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Xenial
node 5 - data: Bionic
queue size = 6
以前の Queue クラスには、デストラクタの実装と、キューから要素を削除する機能がありません。これら 2つは次のコードスニペットで定義されており、対応するドライバーコードはプログラムの main 関数に含まれています。
deQueue 関数は、実装に固有の文字列値を返すように設計されています。したがって、この関数はキューが空であることを示す空の文字列を返し、ユーザーは戻り値を確認する責任があります。一方、デストラクタ関数は、オブジェクトがスコープ外になる前に、割り当てられたすべてのメモリが解放されていることを確認します。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
string Queue::deQueue() {
if (front == nullptr)
return "";
else {
auto tmp = front->next;
auto data = front->data;
delete front;
front = tmp;
size--;
return data;
}
}
Queue::~Queue() {
struct ListNode *tmp = nullptr;
while (front) {
tmp = front->next;
delete front;
front = tmp;
}
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
auto ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
while (!q1.deQueue().empty())
;
cout << "queue size = " << q1.getSize() << endl;
ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
for (int i = 0; i < 100; ++i) {
q1.enQueue("hello");
}
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Precise
queue size = 3
/ ------------------------------ /
queue size = 0
Queue is empty!
queue size = 100
