MENU
  1. ホーム
  2. C言語
  3. 初心者向け：C言語でスタックを実装する方法を完全ガイド

初心者向け：C言語でスタックを実装する方法を完全ガイド

C言語

この記事では、C言語でスタックを実装する方法を初心者向けにわかりやすく解説します。基本的な概念から実際のコード例、応用例までカバーします。スタックの基礎知識を学び、実際にプログラムに取り入れていくためのステップを順を追って説明しますので、初めてスタックを扱う方でも理解できるようになっています。

目次

スタックとは何か

スタックは、データを順序良く管理するためのデータ構造の一つです。主に「後入れ先出し（LIFO: Last In, First Out）」の原則に基づいて動作します。これは、最後に追加されたデータが最初に取り出されるという意味です。

スタックの基本概念

スタックは、主に次の二つの基本操作によって管理されます：

プッシュ（Push）

データをスタックの一番上に追加する操作。

ポップ（Pop）

スタックの一番上のデータを取り出す操作。

スタックは、メモリ管理や関数呼び出しの際の一時的なデータ保存、アルゴリズムの設計など、様々な場面で利用されます。

スタックの用途

スタックは、データを一時的に保存し、その順序を保持するための便利なデータ構造です。以下に、スタックが使用される代表的な用途をいくつか紹介します。

関数呼び出しの管理

プログラムが関数を呼び出すとき、現在の関数の状態（ローカル変数や戻り先アドレスなど）を保存するためにスタックが使用されます。これにより、関数が終了した際に正確に元の状態に戻ることができます。

逆ポーランド記法の計算

スタックは、逆ポーランド記法（Postfix Notation）の数式を評価するために使用されます。この方法では、演算子の順序に依存せずに数式を簡単に計算できます。

ブラウザの履歴管理

ウェブブラウザは、ユーザーの閲覧履歴をスタックに保存することで、「戻る」ボタンで前のページに戻れるようにしています。各ページのURLがスタックにプッシュされ、戻るときにはポップされます。

再帰アルゴリズムの実装

再帰的なアルゴリズム（例えば、ツリーの探索やバックトラッキング問題）では、スタックを使用して現在の状態を保存し、必要に応じて元に戻ることができます。

これらの用途を理解することで、スタックの重要性とその実用性を実感できるでしょう。次のセクションでは、スタックの基本操作について詳しく見ていきます。

スタックの基本操作

スタックの基本操作は、主にデータの追加と取り出しに関するものです。これらの操作を理解することが、スタックを効果的に利用するための第一歩です。

プッシュ操作（Push）

プッシュ操作は、スタックの一番上に新しいデータを追加する操作です。以下はプッシュ操作の擬似コードです。

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

ポップ操作（Pop）

ポップ操作は、スタックの一番上のデータを取り出す操作です。この操作により、取り出されたデータはスタックから削除されます。以下はポップ操作の擬似コードです。

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1; // またはエラーコード
    }
    return stack->items[(stack->top)--];
}

ピーク操作（Peek）

ピーク操作は、スタックの一番上のデータを確認する操作です。データは削除されず、現在のトップの値を返します。以下はピーク操作の擬似コードです。

int peek(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1; // またはエラーコード
    }
    return stack->items[stack->top];
}

スタックの判定操作

スタックが空かどうか、または満杯かどうかを確認するための操作も重要です。以下はそれらの擬似コードです。

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

これらの基本操作を理解し、実装することで、スタックを効果的に利用することができるようになります。次のセクションでは、C言語でスタックを実装するための具体的な構造設計について説明します。

C言語でのスタックの構造設計

スタックをC言語で実装するには、データ構造とその操作を設計する必要があります。以下では、スタックを実装するための基本的な構造体とその設計について説明します。

スタックの構造体定義

スタックを表現するために、配列とトップインデックスを含む構造体を定義します。配列はスタックのデータを保持し、トップインデックスは現在のスタックの最上位要素を示します。

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

スタックの初期化

スタックを使用する前に、初期化する必要があります。初期化関数は、スタックのトップインデックスを-1に設定します。

void initializeStack(Stack *stack) {
    stack->top = -1;
}

プッシュ操作の実装

スタックに要素を追加するプッシュ操作は、スタックのトップインデックスをインクリメントし、その位置に新しい要素を追加します。スタックが満杯の場合はオーバーフローのエラーメッセージを表示します。

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

ポップ操作の実装

スタックから要素を取り出すポップ操作は、スタックのトップインデックスの位置から要素を取り出し、そのインデックスをデクリメントします。スタックが空の場合はアンダーフローのエラーメッセージを表示します。

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1; // またはエラーコード
    }
    return stack->items[(stack->top)--];
}

ピーク操作の実装

スタックの最上位要素を確認するピーク操作は、トップインデックスの位置にある要素を返します。スタックが空の場合はエラーメッセージを表示します。

int peek(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1; // またはエラーコード
    }
    return stack->items[stack->top];
}

スタックの判定操作の実装

スタックが空かどうか、または満杯かどうかを確認する関数を実装します。

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

これらの構造体と基本操作を実装することで、C言語でスタックを効果的に利用できるようになります。次のセクションでは、スタックの初期化方法について詳しく解説します。

スタックの初期化

スタックを利用するためには、まず初期化が必要です。初期化は、スタックのトップインデックスを適切に設定し、スタックが空であることを示す状態にします。

初期化関数の実装

スタックの初期化関数では、トップインデックスを-1に設定します。これにより、スタックが空であることを示します。以下は、初期化関数の具体的なコード例です。

void initializeStack(Stack *stack) {
    stack->top = -1;
}

初期化の手順

  1. スタックの構造体を宣言します。
  2. 初期化関数を呼び出して、スタックを初期化します。

具体的な使用例を以下に示します。

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initializeStack(Stack *stack) {
    stack->top = -1;
}

int main() {
    Stack myStack;
    initializeStack(&myStack);

    // スタックが正しく初期化されたか確認
    if (isEmpty(&myStack)) {
        printf("Stack is successfully initialized and is currently empty.\n");
    } else {
        printf("Stack initialization failed.\n");
    }

    return 0;
}

スタックが初期化されているかの確認

初期化が正しく行われたかを確認するために、スタックのトップインデックスをチェックします。以下の関数で、スタックが空かどうかを確認できます。

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

これにより、スタックが空であることを確認し、初期化が成功したことを確認できます。

初期化が完了したら、次はスタックに要素を追加するプッシュ操作について学びます。次のセクションでは、プッシュ操作の実装方法を具体的なコード例とともに説明します。

スタックに要素を追加する（プッシュ操作）

プッシュ操作は、スタックに新しい要素を追加する基本的な操作です。この操作により、スタックのトップに新しいデータが積み重ねられます。

プッシュ操作の実装

プッシュ操作を実装するには、スタックのトップインデックスをインクリメントし、その位置に新しい要素を追加します。スタックが満杯の場合は、オーバーフローエラーを防ぐためのチェックも必要です。

以下に、プッシュ操作の具体的なコード例を示します。

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initializeStack(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

int main() {
    Stack myStack;
    initializeStack(&myStack);

    // スタックに要素を追加
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    // スタックの内容を表示
    for (int i = 0; i <= myStack.top; i++) {
        printf("%d ", myStack.items[i]);
    }

    return 0;
}

プッシュ操作の手順

  1. スタックが満杯かどうかを確認します。
  2. スタックが満杯でない場合、トップインデックスをインクリメントします。
  3. インクリメントした位置に新しい要素を追加します。

プッシュ操作のポイント

  • スタックが満杯の場合、オーバーフローエラーを防ぐために操作を中止し、エラーメッセージを表示します。
  • スタックが満杯でない場合、新しい要素を追加し、トップインデックスを更新します。

これで、スタックに要素を追加するプッシュ操作の実装方法を理解できました。次のセクションでは、スタックから要素を取り出すポップ操作の実装方法について説明します。

スタックから要素を取り出す（ポップ操作）

ポップ操作は、スタックから最新の要素を取り出し、その要素を削除する基本的な操作です。この操作により、スタックのトップにあるデータが取得されます。

ポップ操作の実装

ポップ操作を実装するには、スタックのトップインデックスをデクリメントし、その位置にある要素を取得します。スタックが空の場合は、アンダーフローエラーを防ぐためのチェックも必要です。

以下に、ポップ操作の具体的なコード例を示します。

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initializeStack(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1; // またはエラーコード
    }
    return stack->items[(stack->top)--];
}

int main() {
    Stack myStack;
    initializeStack(&myStack);

    // スタックに要素を追加
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    // スタックから要素を取り出し
    int value = pop(&myStack);
    printf("Popped value: %d\n", value);

    // スタックの残りの内容を表示
    for (int i = 0; i <= myStack.top; i++) {
        printf("%d ", myStack.items[i]);
    }

    return 0;
}

ポップ操作の手順

  1. スタックが空かどうかを確認します。
  2. スタックが空でない場合、トップインデックスの位置にある要素を取得します。
  3. トップインデックスをデクリメントします。

ポップ操作のポイント

  • スタックが空の場合、アンダーフローエラーを防ぐために操作を中止し、エラーメッセージを表示します。
  • スタックが空でない場合、トップインデックスの位置にある要素を取得し、トップインデックスを更新します。

これで、スタックから要素を取り出すポップ操作の実装方法を理解できました。次のセクションでは、スタックの動作を確認し、テストする方法について説明します。

スタックの動作確認とテスト

スタックを実装した後は、その動作を確認し、正しく機能するかをテストすることが重要です。ここでは、スタックの基本操作をテストするための方法を紹介します。

テストケースの作成

スタックの動作を確認するために、いくつかのテストケースを作成します。以下の例では、スタックの初期化、プッシュ、ポップ、アンダーフロー、オーバーフローの各操作をテストします。

スタックのテストコード例

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initializeStack(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1; // またはエラーコード
    }
    return stack->items[(stack->top)--];
}

int peek(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty\n");
        return -1; // またはエラーコード
    }
    return stack->items[stack->top];
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

int main() {
    Stack myStack;
    initializeStack(&myStack);

    // テスト：スタックが空か確認
    if (isEmpty(&myStack)) {
        printf("Test 1 Passed: Stack is empty after initialization.\n");
    } else {
        printf("Test 1 Failed: Stack is not empty after initialization.\n");
    }

    // テスト：プッシュ操作
    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);

    if (myStack.top == 2 && myStack.items[2] == 30) {
        printf("Test 2 Passed: Push operations.\n");
    } else {
        printf("Test 2 Failed: Push operations.\n");
    }

    // テスト：ポップ操作
    int value = pop(&myStack);
    if (value == 30 && myStack.top == 1) {
        printf("Test 3 Passed: Pop operation.\n");
    } else {
        printf("Test 3 Failed: Pop operation.\n");
    }

    // テスト：ピーク操作
    value = peek(&myStack);
    if (value == 20 && myStack.top == 1) {
        printf("Test 4 Passed: Peek operation.\n");
    } else {
        printf("Test 4 Failed: Peek operation.\n");
    }

    // テスト：アンダーフロー
    pop(&myStack);
    pop(&myStack);
    value = pop(&myStack);
    if (value == -1 && isEmpty(&myStack)) {
        printf("Test 5 Passed: Underflow condition.\n");
    } else {
        printf("Test 5 Failed: Underflow condition.\n");
    }

    // テスト：オーバーフロー
    for (int i = 0; i < MAX_SIZE; i++) {
        push(&myStack, i);
    }
    push(&myStack, 101); // This should cause overflow
    if (isFull(&myStack)) {
        printf("Test 6 Passed: Overflow condition.\n");
    } else {
        printf("Test 6 Failed: Overflow condition.\n");
    }

    return 0;
}

テスト項目の説明

  • 初期化テスト: スタックが初期化後に空であることを確認。
  • プッシュ操作テスト: 複数の要素をプッシュし、スタックの状態を確認。
  • ポップ操作テスト: 要素をポップし、スタックの状態を確認。
  • ピーク操作テスト: 現在のトップ要素を確認。
  • アンダーフローテスト: 空のスタックからポップ操作を行い、アンダーフローエラーを確認。
  • オーバーフローテスト: スタックが満杯の状態でプッシュ操作を行い、オーバーフローエラーを確認。

これらのテストを実行することで、スタックの各操作が正しく動作しているかを確認できます。次のセクションでは、スタックの応用例として逆ポーランド記法の計算方法を紹介します。

応用例：逆ポーランド記法の計算

スタックは、逆ポーランド記法（Postfix Notation）による数式の計算に非常に適しています。このセクションでは、スタックを用いて逆ポーランド記法の数式を評価する方法を解説します。

逆ポーランド記法とは

逆ポーランド記法は、演算子をオペランドの後に記述する表記法です。例えば、通常の中置記法では「3 + 4」は「3 4 +」と表現されます。この表記法では、括弧を必要とせず、スタックを使って簡単に計算を行うことができます。

逆ポーランド記法の計算アルゴリズム

逆ポーランド記法の計算は次の手順で行います：

  1. 式の左から右へ順に読み取ります。
  2. 数字が出てきたらスタックにプッシュします。
  3. 演算子が出てきたら、スタックから必要な数のオペランドをポップし、演算を行います。その結果を再びスタックにプッシュします。
  4. 最終的にスタックには計算結果が一つだけ残ります。

逆ポーランド記法の計算コード例

以下に、逆ポーランド記法の数式を計算するC言語のコード例を示します。

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

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void initializeStack(Stack *stack) {
    stack->top = -1;
}

void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->items[++(stack->top)] = value;
}

int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow\n");
        return -1; // またはエラーコード
    }
    return stack->items[(stack->top)--];
}

int evaluatePostfix(char* expression) {
    Stack stack;
    initializeStack(&stack);
    char* token = expression;

    while (*token != '\0') {
        if (isdigit(*token)) {
            int num = *token - '0';
            push(&stack, num);
        } else {
            int val1 = pop(&stack);
            int val2 = pop(&stack);
            switch (*token) {
                case '+': push(&stack, val2 + val1); break;
                case '-': push(&stack, val2 - val1); break;
                case '*': push(&stack, val2 * val1); break;
                case '/': push(&stack, val2 / val1); break;
                default: printf("Invalid operator\n"); return -1;
            }
        }
        token++;
    }
    return pop(&stack);
}

int main() {
    char expression[] = "231*+9-";
    printf("Postfix expression: %s\n", expression);
    int result = evaluatePostfix(expression);
    printf("Result: %d\n", result);
    return 0;
}

コードの説明

  1. evaluatePostfix関数は、文字列として与えられた逆ポーランド記法の式を評価します。
  2. 各文字が数字であるかをチェックし、数字ならスタックにプッシュします。
  3. 演算子が出てきた場合、スタックから2つのオペランドをポップし、演算を行います。その結果を再びスタックにプッシュします。
  4. 式全体を処理した後、スタックには計算結果が1つだけ残ります。

これで、スタックを用いた逆ポーランド記法の計算方法を理解できました。次のセクションでは、スタックの理解を深めるための演習問題を紹介します。

演習問題

スタックの理解を深めるために、いくつかの演習問題を提供します。これらの問題を解くことで、スタックの基本操作とその応用についてより深く理解することができます。

演習問題1: 基本的なスタック操作

以下のスタック操作のシーケンスを実行し、最終的なスタックの状態を示してください。

  1. プッシュ 5
  2. プッシュ 10
  3. プッシュ 15
  4. ポップ
  5. プッシュ 20
  6. ポップ
  7. プッシュ 25

期待される結果

最終的なスタックの状態は [5, 10, 25] になります。

演習問題2: 括弧のバランスチェック

与えられた文字列が括弧のバランスが取れているかどうかを判定するプログラムを作成してください。括弧には (, ), {, }, [, ] の6種類が含まれます。

例

  • 入力: ({[()]})
  • 出力: バランスが取れています
  • 入力: ({[([)])})
  • 出力: バランスが取れていません

演習問題3: 逆ポーランド記法の計算

以下の逆ポーランド記法の式を評価するプログラムを作成し、結果を示してください。

  1. 2 3 1 * + 9 -
  2. 5 1 2 + 4 * + 3 -

期待される結果

  1. 式 2 3 1 * + 9 - の結果は -4
  2. 式 5 1 2 + 4 * + 3 - の結果は 14

演習問題4: 再帰を用いたスタックの実装

再帰を使用してスタックのプッシュとポップ操作を実装してください。再帰的な方法でスタックの要素を逆順に表示する関数も作成してください。

例

スタックに [1, 2, 3, 4, 5] の要素がある場合、逆順に表示する関数の出力は 5, 4, 3, 2, 1 になります。

演習問題5: スタックの最小値を取得する関数

通常のスタック操作（プッシュとポップ）に加えて、現在のスタックの最小値を O(1) の時間で取得できる関数 getMin() を実装してください。

例

  1. push(3)
  2. push(5)
  3. getMin() → 3
  4. push(2)
  5. push(1)
  6. getMin() → 1
  7. pop()
  8. getMin() → 2

これらの演習問題に取り組むことで、スタックの基本操作から応用例まで幅広く学ぶことができます。各問題に対する自分の解答を確認し、必要に応じて改善していきましょう。次のセクションでは、本記事のまとめを行います。

まとめ

本記事では、C言語でスタックを実装する方法について、基本的な概念から応用例までを包括的に解説しました。スタックの基本操作であるプッシュ、ポップ、ピークの実装方法を具体的なコード例とともに紹介し、逆ポーランド記法の計算などの応用例も取り上げました。

また、スタックの理解を深めるための演習問題を提供し、実際に手を動かして学ぶ機会を設けました。これにより、スタックの操作方法とその実用性を実感できたのではないでしょうか。

スタックは、効率的なメモリ管理やアルゴリズム設計において重要な役割を果たします。今回学んだ知識を活かし、さらに高度なデータ構造やアルゴリズムに挑戦してみてください。

C言語
プログラミング コード例 データ構造 スタック C言語

コメント

コメントする

目次