はじめに
このプロジェクトでは、C 言語でキューデータ構造を実装する方法を学びます。キューはコンピュータサイエンスにおいて広く使用されており、たとえばコンピュータ内でデータを送信するためのメッセージキューなどです。
👀 予習
$ gcc queue.c -o queue
$./queue
11250
🎯 タスク
このプロジェクトでは、以下を学びます。
- キューの先頭要素の値を返す
front()メソッドを実装する方法 - キューから先頭要素を削除して返す
pop()メソッドを実装する方法 - 現在キュー内にある要素の数を返す
count()メソッドを実装する方法 - キューが空かどうかをチェックする
is_empty()メソッドを実装する方法
🏆 成果
このプロジェクトを完了すると、以下のことができるようになります。
- キューデータ構造の基本操作を理解する
- C 言語でキューのコアメソッドを実装する
- キューの知識を活用して現実世界の問題を解決する
front() メソッドを実装する
このステップでは、キューの front() メソッドをどのように実装するか学びます。
front() メソッドは、キューの先頭要素の値を返す必要があります。キューが空の場合、このメソッドは exit(-1) でプログラムを終了する必要があります。
以下の手順に従ってこのステップを完了しましょう。
/home/labex/project/queue.cにあるqueue.cファイルを開きます。- コード内の
front()メソッドを見つけます。 front()メソッドを以下のように実装します。
static int front() {
if(!phead) {
exit(-1);
}
return phead->val;
}
front() メソッドはまず、空のキューを示す phead ポインタが NULL であるかどうかをチェックします。キューが空の場合、このメソッドは exit(-1) でプログラムを終了します。
キューが空でない場合、このメソッドはキューの先頭要素を表す phead ノードに格納されている値を返します。
pop() メソッドを実装する
このステップでは、キューの pop() メソッドをどのように実装するか学びます。
pop() メソッドは、キューから先頭要素を削除して返す必要があります。キューが空の場合、このメソッドは exit(-1) でプログラムを終了する必要があります。
以下の手順に従ってこのステップを完了しましょう。
/home/labex/project/queue.cにあるqueue.cファイルを開きます。- コード内の
pop()メソッドを見つけます。 pop()メソッドを以下のように実装します。
static int pop() {
if(!phead) {
exit(-1);
}
int val = phead->val;
phead = phead->next;
return val;
}
pop() メソッドはまず、空のキューを示す phead ポインタが NULL であるかどうかをチェックします。キューが空の場合、このメソッドは exit(-1) でプログラムを終了します。
キューが空でない場合、このメソッドはキューの先頭要素を表す phead ノードの値を格納します。次に、phead ポインタを次のノードに更新して、実際にキューから先頭要素を削除します。最後に、このメソッドは格納された値を返します。
count() メソッドを実装する
このステップでは、キューの count() メソッドをどのように実装するか学びます。
count() メソッドは、現在キュー内にある要素の数を返す必要があります。
以下の手順に従ってこのステップを完了しましょう。
/home/labex/project/queue.cにあるqueue.cファイルを開きます。- コード内の
count()メソッドを見つけます。 count()メソッドを以下のように実装します。
static int count() {
int cnt = 0;
for(struct node* p = phead; p; p=p->next) {
cnt++;
}
return cnt;
}
count() メソッドは、cnt 変数を 0 に初期化します。次に、phead ノードとその後続ノードの next ポインタを辿ってキューを巡回します。遭遇した各ノードに対して、cnt 変数をインクリメントします。最後に、このメソッドは cnt 値を返します。この値は、キュー内の要素数を表します。
is_empty() メソッドを実装する
このステップでは、キューの is_empty() メソッドをどのように実装するか学びます。
is_empty() メソッドは、キューが空の場合には 1 を返し、そうでない場合には 0 を返す必要があります。
以下の手順に従ってこのステップを完了しましょう。
/home/labex/project/queue.cにあるqueue.cファイルを開きます。- コード内の
is_empty()メソッドを見つけます。 is_empty()メソッドを以下のように実装します。
static int is_empty() {
return phead == NULL;
}
is_empty() メソッドは、空のキューを示す phead ポインタが NULL であるかどうかを単にチェックします。phead が NULL の場合、このメソッドは 1 を返してキューが空であることを示します。そうでない場合、0 を返してキューが空でないことを示します。
おめでとうございます！これで、キューデータ構造に必要なすべてのメソッドを実装しました。これで、キューの機能をテストするためにプログラムをコンパイルして実行できます。
- コンパイルと実行：
$ gcc queue.c -o queue
$./queue
00000
期待される出力は以下の通りです。
$ gcc queue.c -o queue
$./queue
11250
まとめ
おめでとうございます！このプロジェクトを完了しました。スキルを向上させるために、LabEx でさらに多くの実験を行って練習できます。
