ジェネリックスタック
CoddyのCジャーニー「Object Oriented Programming」セクションの一部 — レッスン 60/61。
チャレンジ
簡単スタックは、後入れ先出し（LIFO: Last-In-First-Out）の原則に従う基本的なデータ構造です。つまり、最後に追加された要素が最初に取り出されます。皿の積み重ねを想像してください。一番上に追加し、一番上から取り出します。
void* ポインタを使用してあらゆるタイプのデータを格納できる、汎用性の高いデータ構造である汎用スタック（Generic Stack）を構築しましょう。あなたのスタックは後入れ先出しの原則に従い、すべての必須操作を備えたものになります。
コードは以下の3つのファイルに分けて構成します：
stack.h: 3つのメンバを持つStack構造体を定義します。アイテム用のvoid**配列、次の空きスロットを示すint型のtopインデックス、およびint型のcapacityです。スタックの作成（容量を指定）、アイテムのプッシュ、アイテムのポップ、トップアイテムのピーク（参照）、スタックが空かどうかの確認、およびスタックの解放を行うための関数プロトタイプを宣言します。stack.c: 汎用スタックを実装します：create_stack— ヒープ上に Stack を割り当て、指定された容量でアイテム配列を割り当て、top を 0 に初期化し、そのポインタを返します。push— 空きがある場合（top が capacity 未満の場合）、アイテムをトップに追加します。pop— トップのアイテムを削除して返します。スタックが空の場合はNULLを返します。peek— トップのアイテムを削除せずに返します。空の場合はNULLを返します。is_empty— スタックにアイテムがない場合は 1 を、それ以外の場合は 0 を返します。free_stack— 最初にアイテム配列を解放し、次に Stack 構造体自体を解放します。
main.c: 実行する操作の数を読み取ります。次に、各操作についてコマンドを読み取ります。コマンドは、整数値が続くpush、pop、またはpeekです。容量 10 のスタックを作成します。pushの場合は、ヒープ上に整数を割り当て、そのポインタをプッシュします。popの場合は、アイテムを取得してその値を表示し、整数を解放します。peekの場合は、削除せずに値を表示します。空のスタックに対してpopまたはpeekが呼び出された場合は、emptyと表示します。すべての操作が終わったら、残っているアイテムとスタックを解放します。
プログラムは以下を受け取ります：
- 操作の数
- 各操作を別々の行に（
push X、pop、またはpeek）
入力が 5 で、その後に push 10、push 20、peek、pop、pop と続いた場合の出力例：
20
20
10入力が 3 で、その後に pop、push 42、peek と続いた場合の出力例：
empty
42入力が 4 で、その後に push 5、push 15、pop、pop と続いた場合の出力例：
15
5スタックは void* ポインタを格納することに注意してください。実際のデータの割り当てと解放は呼び出し側の責任です。ポップするときは、返された void* を int* にキャストし直して値にアクセスします。コマンド文字列の比較には <string.h> の strcmp を使用してください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
int main() {
int n;
scanf("%d", &n);
// TODO: 容量10のスタックを作成する
// TODO: 各操作を処理する
for (int i = 0; i < n; i++) {
char command[10];
scanf("%s", command);
if (strcmp(command, "push") == 0) {
int value;
scanf("%d", &value);
// TODO: ヒープ上に整数を割り当て、そのポインタを push する
}
else if (strcmp(command, "pop") == 0) {
// TODO: アイテムを pop する
// - NULL でない場合、値を表示してその整数を free する
// - NULL の場合（スタックが空）、"empty" と表示する
}
else if (strcmp(command, "peek") == 0) {
// TODO: 最上位のアイテムを peek する
// - NULL でない場合、値を表示する（削除や free はしない）
// - NULL の場合（スタックが空）、"empty" と表示する
}
}
// TODO: スタックに残っているすべてのアイテムを free する
// TODO: スタック自体を free する
return 0;
}
