[C言語のはじめ方] Part31: スタック・キュー・リスト構造

こんにちは！C言語学習の旅、Step 7へようこそ！ここでは、プログラムでデータを効率的に扱うための基本的な「型」とも言える「データ構造」の中から、特に重要なスタック、キュー、そしてリスト構造について学びます。これらは、より複雑なアルゴリズムやプログラムを構築するための基礎となります。💪

これまでのステップで学んだポインタや構造体、動的メモリ確保の知識がここで活きてきます。準備はいいですか？さっそく見ていきましょう！

スタックは、LIFO (Last-In, First-Out)、つまり「後入れ先出し」の原則に従うデータ構造です。皿洗いで積み重ねたお皿をイメージしてください。一番最後に置いたお皿を一番最初に取り出しますよね？それと同じです。

主な操作

• Push (プッシュ): スタックの一番上に新しいデータを追加します。
• Pop (ポップ): スタックの一番上のデータを取り出します（取り出したデータはスタックから削除されます）。

C言語での実装

スタックは配列や連結リストを使って実装できます。ここでは、連結リストを使ったスタックのイメージを見てみましょう。新しいデータ（ノード）を追加するときはリストの先頭に追加し、取り出すときも先頭から取り出します。これはStep 6で学んだ動的メモリ確保 (malloc, free) や Step 4の構造体 (struct)、Step 3のポインタの知識を活用します。

#include <stdio.h>
#include <stdlib.h> // malloc, free, exit を使うため

// スタックのノードを表す構造体
typedef struct Node {
    int data;           // 格納するデータ
    struct Node* next;  // 次のノードへのポインタ (自分自身を指す可能性があるので struct Node*)
} Node;

// スタック本体（先頭ノードへのポインタを持つ構造体）
typedef struct Stack {
    Node* top; // スタックの先頭（一番上）を指すポインタ
} Stack;

// スタックを初期化する関数
void initializeStack(Stack* s) {
    s->top = NULL; // 最初は空なのでNULLを指す
}

// スタックが空かどうかをチェックする関数
int isEmpty(Stack* s) {
    return s->top == NULL;
}

// Push操作: スタックにデータを追加する関数
void push(Stack* s, int data) {
    // 新しいノードのメモリを確保
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "エラー: メモリ確保に失敗しました。\n");
        exit(EXIT_FAILURE); // メモリ確保失敗は致命的なのでプログラム終了
    }
    newNode->data = data;          // データを格納
    newNode->next = s->top;        // 新しいノードの次を、現在のスタックの先頭にする
    s->top = newNode;             // スタックの先頭ポインタを、新しいノードに向ける
    printf("Pushed: %d\n", data);
}

// Pop操作: スタックからデータを取り出す関数
int pop(Stack* s) {
    // スタックが空かチェック
    if (isEmpty(s)) {
        fprintf(stderr, "エラー: スタックは空です。Popできません。\n");
        return -1; // エラーを示す値（実際にはより良いエラー処理を検討）
    }
    Node* temp = s->top;         // 先頭ノードを一時的に保存
    int poppedData = temp->data; // 取り出すデータを取得
    s->top = s->top->next;     // スタックの先頭を、次のノードに更新
    free(temp);                  // 取り出したノードのメモリを解放
    printf("Popped: %d\n", poppedData);
    return poppedData;
}

// スタックの先頭データを覗き見する関数 (削除はしない)
int peek(Stack* s) {
     if (isEmpty(s)) {
        fprintf(stderr, "エラー: スタックは空です。Peekできません。\n");
        return -1; // エラーを示す値
    }
    return s->top->data;
}

// メイン関数での使用例
int main() {
    Stack myStack;
    initializeStack(&myStack); // スタックを初期化

    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    printf("Top element is %d\n", peek(&myStack)); // 30

    pop(&myStack); // 30を取り出す
    pop(&myStack); // 20を取り出す

    printf("Top element is %d\n", peek(&myStack)); // 10

    pop(&myStack); // 10を取り出す
    pop(&myStack); // 空の状態でPopしようとする (エラーメッセージが出る)

    // 注意: スタックに残っているノードがあれば、最後に全て解放する処理が必要です。
    // この例では全てpopしているので不要ですが、途中で終了する場合などは解放漏れに注意。

    return 0;
}

用途例

• 💻 関数の呼び出しと戻りアドレスの管理（コールスタック）
• ⏪ テキストエディタなどの「元に戻す」（Undo）機能
• 🧮 数式の構文解析や評価（逆ポーランド記法など）
• 🌲 深さ優先探索 (DFS: Depth First Search) アルゴリズム
• 🔙 ウェブブラウザの「戻る」ボタンの履歴

キューは、FIFO (First-In, First-Out)、つまり「先入れ先出し」の原則に従うデータ構造です。スーパーのレジ待ちの行列を思い浮かべてください。最初に列に並んだ人が、最初に会計を済ませますよね？それと同じ仕組みです。

主な操作

• Enqueue (エンキュー): キューの末尾 (rear) に新しいデータを追加します。
• Dequeue (デキュー): キューの先頭 (front) からデータを取り出します（取り出したデータはキューから削除されます）。

C言語での実装

キューも配列や連結リストで実装できます。連結リストで実装する場合、効率的に末尾への追加と先頭からの削除を行うために、リストの先頭 (front) と末尾 (rear) の両方を指すポインタを持つことが一般的です。

#include <stdio.h>
#include <stdlib.h>

// キューのノードを表す構造体（スタックと同じものを使えます）
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// キュー本体（先頭と末尾へのポインタを持つ）
typedef struct Queue {
    Node* front; // キューの先頭 (取り出す側)
    Node* rear;  // キューの末尾 (追加する側)
} Queue;

// キューを初期化する関数
void initializeQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// キューが空かどうかをチェックする関数
int isEmptyQueue(Queue* q) {
    return q->front == NULL; // frontがNULLなら空
}

// Enqueue操作: キューの末尾にデータを追加する関数
void enqueue(Queue* q, int data) {
    // 新しいノードを作成
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "エラー: メモリ確保に失敗しました。\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL; // 末尾に追加するので、nextは常にNULL

    if (isEmptyQueue(q)) { // キューが空の場合
        q->front = newNode; // frontとrearの両方が新しいノードを指す
        q->rear = newNode;
    } else { // キューに要素がある場合
        q->rear->next = newNode; // 現在の末尾ノードのnextを新しいノードに向ける
        q->rear = newNode;       // rearポインタを新しいノードに更新
    }
    printf("Enqueued: %d\n", data);
}

// Dequeue操作: キューの先頭からデータを取り出す関数
int dequeue(Queue* q) {
    if (isEmptyQueue(q)) {
        fprintf(stderr, "エラー: キューは空です。Dequeueできません。\n");
        return -1; // エラーを示す値
    }
    Node* temp = q->front;         // 先頭ノードを一時的に保存
    int dequeuedData = temp->data; // 取り出すデータを取得
    q->front = q->front->next;     // frontポインタを次のノードに更新

    // もしデキュー後にキューが空になったら、rearもNULLにする必要がある
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp); // 元の先頭ノードのメモリを解放
    printf("Dequeued: %d\n", dequeuedData);
    return dequeuedData;
}

// キューの先頭データを覗き見する関数 (削除はしない)
int peekQueue(Queue* q) {
     if (isEmptyQueue(q)) {
        fprintf(stderr, "エラー: キューは空です。Peekできません。\n");
        return -1; // エラーを示す値
    }
    return q->front->data;
}

// メイン関数での使用例
int main() {
    Queue myQueue;
    initializeQueue(&myQueue);

    enqueue(&myQueue, 100);
    enqueue(&myQueue, 200);
    enqueue(&myQueue, 300);

    printf("Front element is %d\n", peekQueue(&myQueue)); // 100

    dequeue(&myQueue); // 100を取り出す
    enqueue(&myQueue, 400);
    dequeue(&myQueue); // 200を取り出す

    printf("Front element is %d\n", peekQueue(&myQueue)); // 300

    dequeue(&myQueue); // 300を取り出す
    dequeue(&myQueue); // 400を取り出す
    dequeue(&myQueue); // 空の状態でDequeueしようとする (エラー)

    // 注意: キューに残っているノードがあれば、最後に全て解放する処理が必要です。
    // この例では全てdequeueしているので不要ですが、注意が必要です。

    return 0;
}

用途例

• 📠 プリンターへの印刷ジョブの待ち行列
• ⌨️ キーボード入力やマウスイベントなどの処理待ち
• 🌐 ネットワーク通信におけるパケットの順次処理
• 🗺️ 幅優先探索 (BFS: Breadth First Search) アルゴリズム（グラフやツリーの探索）
• ⏳ OSによるタスクスケジューリング（実行待ちタスクの管理）

リスト構造（連結リスト）は、データを格納する「ノード」と呼ばれる要素を、ポインタを使って鎖のようにつなげたデータ構造です。配列 (Step 2で学習) とは異なり、メモリ上に要素が連続して配置されている必要がありません。そのため、データの追加や削除が柔軟かつ効率的に行えるという大きなメリットがあります。

基本的な概念

• ノード (Node): データ本体と、次のノードを指すポインタ（next）を持ちます。これがリストの構成要素です。
• ポインタ (Pointer): ノードとノードをつなぐ「鎖」の役割を果たします。リストの先頭を指すポインタ（しばしば head と呼ばれる）が、リスト全体へのアクセス起点となります。

主な種類

リスト構造にはいくつかのバリエーションがあります。

• 単方向リスト (Singly Linked List): 各ノードが次のノードへのポインタ (next) のみを持つ、一方向のリスト。今回主に説明するのはこれです。
• 双方向リスト (Doubly Linked List): 各ノードが次 (next) と前 (prev) の両方のノードへのポインタを持つリスト。逆方向への走査も容易ですが、ポインタ管理が少し複雑になります。
• 循環リスト (Circular Linked List): 末尾のノードが先頭のノードを指す、ループ状になったリスト。リストのどこからでも走査を開始できるなどの利点があります（単方向・双方向どちらもあり）。

C言語での実装（単方向リスト）

リスト構造の実装には、ノードを表す自己参照構造体（自分自身の型へのポインタを持つ構造体）と、動的メモリ確保 (malloc, free) が不可欠です。

#include <stdio.h>
#include <stdlib.h>

// リストのノードを表す構造体
typedef struct ListNode {
    int data;               // 格納するデータ
    struct ListNode* next;  // 次のノードへのポインタ
} ListNode;

// リストの先頭にノードを追加する関数
// 新しい先頭ノードのアドレスを返す (headポインタを更新するため)
ListNode* insertAtBeginning(ListNode* head, int data) {
    // 新しいノードのメモリを確保
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        fprintf(stderr, "エラー: メモリ確保に失敗しました。\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;     // データを格納
    newNode->next = head;     // 新しいノードの次を、現在のリストの先頭にする
    return newNode;           // 新しいノードが新しいリストの先頭になるので、そのアドレスを返す
}

// リストの全要素を表示する関数
void printList(ListNode* head) {
    ListNode* current = head; // 先頭から走査を開始
    printf("List: ");
    while (current != NULL) { // currentがNULLになるまで (リストの終端まで)
        printf("%d -> ", current->data);
        current = current->next; // 次のノードへ移動
    }
    printf("NULL\n"); // リストの終端を示す
}

// リスト全体のメモリを解放する関数
void freeList(ListNode* head) {
    ListNode* current = head;
    ListNode* nextNode;
    while (current != NULL) {
        nextNode = current->next; // 次のノードのアドレスを一時的に保存
        free(current);            // 現在のノードのメモリを解放
        current = nextNode;       // 次のノードへ移動
    }
    printf("List freed.\n");
}

// メイン関数での使用例
int main() {
    ListNode* myList = NULL; // 最初は空リスト (先頭ポインタがNULL)

    // リストの先頭にデータを追加していく
    myList = insertAtBeginning(myList, 30); // myList: 30 -> NULL
    myList = insertAtBeginning(myList, 20); // myList: 20 -> 30 -> NULL
    myList = insertAtBeginning(myList, 10); // myList: 10 -> 20 -> 30 -> NULL

    printList(myList); // リストの内容を表示

    // プログラム終了前に、確保したメモリを解放する
    freeList(myList);
    myList = NULL; // 解放後は無効なポインタを指さないようにNULLを入れておくのが安全

    return 0;
}

配列との比較

リスト構造は配列とよく比較されます。それぞれの利点と欠点を理解し、状況に応じて使い分けることが重要です。

※ O(1) は処理時間がデータ量によらず一定、O(n) はデータ量に比例して処理時間が増加することを意味します（計算量という概念です）。

用途例

• 💾 サイズが事前に予測できない、または頻繁に変動するデータの管理
• 🔄 要素の挿入や削除が頻繁に発生する場面
• 🏗️ スタックやキューなど、他のデータ構造を実装するための基盤として
• 🎵 音楽プレイヤーのプレイリストのように、曲順の変更や追加・削除が容易に必要な場合
• 📝 OSでのメモリ管理（空き領域リストなど）

今回は、基本的なデータ構造であるスタック、キュー、リスト構造について、それぞれの概念、主な操作、C言語での実装イメージ、そして用途例を見てきました。

• スタック: LIFO (後入れ先出し)。Push / Pop。関数呼び出しやUndo機能など。
• キュー: FIFO (先入れ先出し)。Enqueue / Dequeue。待ち行列やイベント処理など。
• リスト構造: ノードとポインタで連結。動的なサイズ変更、柔軟な挿入/削除。配列とは異なる特性を持つ。

これらのデータ構造は、単なるデータの入れ物ではなく、特定の操作を効率的に行うための「仕組み」です。プログラムでどのようなデータ操作が必要になるかを考え、最適なデータ構造を選択することが、パフォーマンスの良い、洗練されたコードを書くための第一歩となります。 🧰

次のステップでは、今回学んだデータ構造の知識も活用しながら、簡易的なデータベースの実装や、電卓・ToDoリストといった、より具体的なアプリケーションの作成に挑戦します。お楽しみに！🚀

これらのデータ構造について、さらに深く学びたい場合は、以下のキーワードで検索したり、信頼できるC言語の参考書や技術サイトを参照することをおすすめします。

• C言語 データ構造 スタック 実装
• C言語 キュー 連結リスト FIFO
• C言語 連結リスト 挿入 削除 アルゴリズム
• データ構造とアルゴリズム C言語 入門
• struct ポインタ 自己参照構造体 C言語
• malloc free メモリ管理 C言語