MENU
  1. ホーム
  2. C言語
  3. アルゴリズム
  4. [C言語] スタックを配列や構造体を用いて実装する方法

[C言語] スタックを配列や構造体を用いて実装する方法

C言語でスタックを実装する際、配列や構造体を使用する方法があります。

配列を用いる場合、スタックの要素を配列に格納し、スタックのトップを指すインデックスを管理します。

基本的な操作は「プッシュ(push)」で要素を追加し、「ポップ(pop)」で要素を取り出します。

構造体を使う場合、スタックの状態(配列、トップのインデックス、サイズなど)を1つの構造体にまとめて管理します。

これにより、スタックの操作がより整理され、拡張性が向上します。

この記事でわかること
  • スタックの基本と操作
  • 配列と構造体による実装方法
  • スタックの応用例と具体的な使用場面
  • スタックとキューの違い
  • スタックの動的サイズ変更方法

目次から探す

スタックとは

スタックは、データ構造の一つで、LIFO(Last In, First Out)方式でデータを管理します。

つまり、最後に追加されたデータが最初に取り出される特性を持っています。

スタックは、プログラミングやアルゴリズムの実装において非常に重要な役割を果たします。

スタックの基本

スタックは、主に以下の2つの操作を提供します。

  • push: スタックの最上部にデータを追加する操作
  • pop: スタックの最上部からデータを取り出す操作

これに加えて、スタックの最上部のデータを確認するための操作(peek)もあります。

スタックの特徴と用途

スタックの特徴は以下の通りです。

スクロールできます
特徴説明
LIFO最後に追加されたデータが最初に取り出される
限定的なアクセス最上部のデータのみアクセス可能
メモリ効率必要なデータのみを保持するため効率的

スタックは、以下のような用途で広く使用されます。

  • 関数の呼び出しと戻り
  • 再帰処理の管理
  • 演算子の優先順位管理
  • バックトラックアルゴリズム

スタックの代表的な操作(push, pop, peek)

  1. push: スタックにデータを追加します。

例えば、整数をスタックに追加する場合、次のように実装します。

#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1; // スタックの初期状態
void push(int value) {
    if (top >= MAX - 1) {
        printf("スタックオーバーフロー\n");
        return;
    }
    stack[++top] = value; // データを追加
}
  1. pop: スタックからデータを取り出します。

スタックが空でないか確認し、データを返します。

int pop() {
    if (top < 0) {
        printf("スタックアンダーフロー\n");
        return -1; // エラー値
    }
    return stack[top--]; // データを取り出し
}
  1. peek: スタックの最上部のデータを確認しますが、取り出しはしません。
int peek() {
    if (top < 0) {
        printf("スタックは空です\n");
        return -1; // エラー値
    }
    return stack[top]; // 最上部のデータを返す
}

これらの操作を組み合わせることで、スタックを効果的に利用することができます。

配列を用いたスタックの実装

配列を用いてスタックを実装する方法は、シンプルで効率的です。

ここでは、配列を使ったスタックの基本構造から、各操作の実装方法までを解説します。

配列を使ったスタックの基本構造

配列を用いたスタックの基本構造は、以下のように定義します。

#define MAX 100 // スタックの最大サイズ
int stack[MAX]; // スタックを表す配列
int top = -1;   // スタックの最上部を指すインデックス

ここで、MAXはスタックの最大サイズを定義し、topはスタックの最上部のインデックスを管理します。

スタックの初期化

スタックの初期化は、topを-1に設定することで行います。

これにより、スタックが空であることを示します。

void initializeStack() {
    top = -1; // スタックを初期化
}

push操作の実装

push操作は、スタックの最上部にデータを追加します。

スタックが満杯でないかを確認し、データを追加します。

void push(int value) {
    if (top >= MAX - 1) {
        printf("スタックオーバーフロー\n");
        return;
    }
    stack[++top] = value; // データを追加
}

pop操作の実装

pop操作は、スタックの最上部からデータを取り出します。

スタックが空でないかを確認し、データを返します。

int pop() {
    if (top < 0) {
        printf("スタックアンダーフロー\n");
        return -1; // エラー値
    }
    return stack[top--]; // データを取り出し
}

peek操作の実装

peek操作は、スタックの最上部のデータを確認しますが、取り出しはしません。

int peek() {
    if (top < 0) {
        printf("スタックは空です\n");
        return -1; // エラー値
    }
    return stack[top]; // 最上部のデータを返す
}

スタックのオーバーフローとアンダーフローの対策

  • オーバーフロー: スタックが満杯の状態でpush操作を行うと、データが追加できなくなります。

この場合、エラーメッセージを表示します。

  • アンダーフロー: スタックが空の状態でpop操作を行うと、データを取り出せません。

この場合もエラーメッセージを表示します。

配列スタックのメリットとデメリット

スクロールできます
メリットデメリット
実装が簡単サイズが固定されている
メモリの連続確保が可能スタックサイズを超えるとオーバーフロー
アクセス速度が速いメモリの無駄が生じる可能性がある

完成したサンプルコード

以下は、配列を用いたスタックの実装例です。

#include <stdio.h>
#define MAX 100 // スタックの最大サイズ
int stack[MAX]; // スタックを表す配列
int top = -1;   // スタックの最上部を指すインデックス
void initializeStack() {
    top = -1; // スタックを初期化
}
void push(int value) {
    if (top >= MAX - 1) {
        printf("スタックオーバーフロー\n");
        return;
    }
    stack[++top] = value; // データを追加
}
int pop() {
    if (top < 0) {
        printf("スタックアンダーフロー\n");
        return -1; // エラー値
    }
    return stack[top--]; // データを取り出し
}
int peek() {
    if (top < 0) {
        printf("スタックは空です\n");
        return -1; // エラー値
    }
    return stack[top]; // 最上部のデータを返す
}
int main() {
    initializeStack(); // スタックの初期化
    push(10);
    push(20);
    push(30);
    printf("最上部のデータ: %d\n", peek()); // 30を表示
    printf("ポップしたデータ: %d\n", pop()); // 30を取り出し
    printf("ポップしたデータ: %d\n", pop()); // 20を取り出し
    printf("ポップしたデータ: %d\n", pop()); // 10を取り出し
    printf("ポップしたデータ: %d\n", pop()); // スタックアンダーフローを表示
    return 0;
}

このコードを実行すると、スタックの基本的な操作が確認できます。

最上部のデータ: 30
ポップしたデータ: 30
ポップしたデータ: 20
ポップしたデータ: 10
スタックアンダーフロー
ポップしたデータ: -1

構造体を用いたスタックの実装

構造体を用いてスタックを実装する方法は、データとその管理をより明確にすることができます。

ここでは、構造体を使ったスタックの基本構造から、各操作の実装方法までを解説します。

構造体を使ったスタックの基本構造

構造体を用いたスタックの基本構造は、以下のように定義します。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // スタックの最大サイズ
typedef struct {
    int data[MAX]; // スタックを表す配列
    int top;       // スタックの最上部を指すインデックス
} Stack;

ここで、Stackという構造体を定義し、データを格納する配列と最上部のインデックスを管理します。

構造体を使ったスタックの初期化

スタックの初期化は、topを-1に設定することで行います。

これにより、スタックが空であることを示します。

void initializeStack(Stack* s) {
    s->top = -1; // スタックを初期化
}

push操作の実装

push操作は、スタックの最上部にデータを追加します。

スタックが満杯でないかを確認し、データを追加します。

void push(Stack* s, int value) {
    if (s->top >= MAX - 1) {
        printf("スタックオーバーフロー\n");
        return;
    }
    s->data[++(s->top)] = value; // データを追加
}

pop操作の実装

pop操作は、スタックの最上部からデータを取り出します。

スタックが空でないかを確認し、データを返します。

int pop(Stack* s) {
    if (s->top < 0) {
        printf("スタックアンダーフロー\n");
        return -1; // エラー値
    }
    return s->data[(s->top)--]; // データを取り出し
}

peek操作の実装

peek操作は、スタックの最上部のデータを確認しますが、取り出しはしません。

int peek(Stack* s) {
    if (s->top < 0) {
        printf("スタックは空です\n");
        return -1; // エラー値
    }
    return s->data[s->top]; // 最上部のデータを返す
}

構造体スタックのメリットとデメリット

スクロールできます
メリットデメリット
データと管理を一つの構造体で管理できるサイズが固定されている
可読性が向上スタックサイズを超えるとオーバーフロー
メモリの連続確保が可能メモリの無駄が生じる可能性がある

完成したサンプルコード

以下は、構造体を用いたスタックの実装例です。

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // スタックの最大サイズ
typedef struct {
    int data[MAX]; // スタックを表す配列
    int top;       // スタックの最上部を指すインデックス
} Stack;
void initializeStack(Stack* s) {
    s->top = -1; // スタックを初期化
}
void push(Stack* s, int value) {
    if (s->top >= MAX - 1) {
        printf("スタックオーバーフロー\n");
        return;
    }
    s->data[++(s->top)] = value; // データを追加
}
int pop(Stack* s) {
    if (s->top < 0) {
        printf("スタックアンダーフロー\n");
        return -1; // エラー値
    }
    return s->data[(s->top)--]; // データを取り出し
}
int peek(Stack* s) {
    if (s->top < 0) {
        printf("スタックは空です\n");
        return -1; // エラー値
    }
    return s->data[s->top]; // 最上部のデータを返す
}
int main() {
    Stack s; // スタックのインスタンスを作成
    initializeStack(&s); // スタックの初期化
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("最上部のデータ: %d\n", peek(&s)); // 30を表示
    printf("ポップしたデータ: %d\n", pop(&s)); // 30を取り出し
    printf("ポップしたデータ: %d\n", pop(&s)); // 20を取り出し
    printf("ポップしたデータ: %d\n", pop(&s)); // 10を取り出し
    printf("ポップしたデータ: %d\n", pop(&s)); // スタックアンダーフローを表示
    return 0;
}

このコードを実行すると、スタックの基本的な操作が確認できます。

最上部のデータ: 30
ポップしたデータ: 30
ポップしたデータ: 20
ポップしたデータ: 10
スタックアンダーフロー

スタックの応用例

スタックは、さまざまなアルゴリズムやデータ構造で重要な役割を果たします。

ここでは、スタックの具体的な応用例をいくつか紹介します。

再帰処理のシミュレーション

再帰処理は、関数が自分自身を呼び出すことによって問題を解決する手法です。

スタックは、再帰の呼び出しを管理するために使用されます。

再帰的な関数呼び出しは、内部的にスタックを利用して、戻り先のアドレスやローカル変数を保存します。

例えば、フィボナッチ数列を再帰的に計算する場合、各呼び出しがスタックに積まれ、最終的に戻り値がスタックから取り出されます。

数式の逆ポーランド記法(RPN)の評価

逆ポーランド記法(RPN)は、演算子がオペランドの後に来る表記法です。

スタックを使用して、RPN式を評価することができます。

例えば、式 3 4 + 2 * を評価する場合、次のようにスタックを利用します。

  1. 3 をスタックにプッシュ
  2. 4 をスタックにプッシュ
  3. + を見つけ、スタックから 3 と 4 をポップし、計算して 7 をプッシュ
  4. 2 をスタックにプッシュ
  5. * を見つけ、スタックから 7 と 2 をポップし、計算して 14 をプッシュ

最終的にスタックには 14 が残ります。

括弧の整合性チェック

スタックは、括弧の整合性をチェックするためにも使用されます。

例えば、式に含まれる括弧が正しく閉じられているかを確認することができます。

以下の手順でチェックを行います。

  1. 開き括弧 (, {, [ をスタックにプッシュ
  2. 閉じ括弧 ), }, ] を見つけたら、スタックから開き括弧をポップし、対応する括弧と一致するか確認
  3. 最後にスタックが空であれば、括弧は整合性があると判断

深さ優先探索(DFS)での利用

深さ優先探索(DFS)は、グラフや木構造を探索するアルゴリズムの一つで、スタックを使用して実装されます。

DFSでは、訪問したノードをスタックにプッシュし、次に訪問するノードを選択する際にスタックからポップします。

この方法により、探索の経路を記録し、戻るべきノードを管理することができます。

関数コールスタックの理解

関数コールスタックは、プログラムの実行中に関数が呼び出されるたびに、呼び出し元のアドレスやローカル変数をスタックに保存します。

これにより、関数が終了した際に、正しい位置に戻ることができます。

例えば、関数Aが関数Bを呼び出すと、関数Aの実行状態がスタックに保存され、関数Bが終了すると、スタックから関数Aの状態が復元されます。

この仕組みは、再帰的な関数呼び出しや複雑なプログラムの実行において非常に重要です。

よくある質問

スタックのサイズを動的に変更するにはどうすれば良いですか？

スタックのサイズを動的に変更するには、動的メモリ割り当てを使用します。

C言語では、mallocやreallocを使ってスタックのサイズを変更できます。

以下の手順で実装できます。

  1. 初期サイズのスタックをmallocで作成します。
  2. スタックが満杯になった場合、reallocを使って新しいサイズのメモリを割り当てます。
  3. 新しいサイズのスタックにデータを移動し、古いメモリを解放します。 
stack = realloc(stack, newSize * sizeof(int));

この方法により、スタックのサイズを必要に応じて変更できます。

スタックとキューの違いは何ですか？

スタックとキューは、どちらもデータ構造ですが、データの取り出し方に違いがあります。

スクロールできます
特徴スタックキュー
データの取り出し方LIFO(Last In, First Out)FIFO(First In, First Out)
主な操作push, pop, peekenqueue, dequeue
使用例再帰処理、関数コールスタックプリンタのジョブ管理、タスクスケジューリング

スタックは最後に追加したデータが最初に取り出されるのに対し、キューは最初に追加したデータが最初に取り出されます。

スタックを使うべき場面はどのような場合ですか？

スタックを使うべき場面は以下のような場合です。

  • 再帰処理の管理: 再帰的な関数呼び出しをシミュレーションする際に、スタックを使用して呼び出し履歴を管理します。
  • 演算子の優先順位管理: 数式の評価や変換(例：逆ポーランド記法)において、演算子の優先順位を管理するためにスタックを使用します。
  • 括弧の整合性チェック: プログラムの構文解析において、括弧の整合性を確認するためにスタックを利用します。
  • 深さ優先探索(DFS): グラフや木構造の探索アルゴリズムで、訪問したノードを管理するためにスタックを使用します。

これらの場面では、スタックのLIFO特性が非常に有効です。

まとめ

この記事では、C言語におけるスタックの基本から、配列や構造体を用いた実装方法、さらにはスタックの応用例について詳しく解説しました。

スタックは、データの管理やアルゴリズムの実装において非常に重要な役割を果たし、特に再帰処理や数式の評価、データ構造の探索においてその特性が活かされます。

これを機に、スタックの実装や応用を実際のプログラミングに取り入れてみてはいかがでしょうか。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

アルゴリズム
  • URLをコピーしました！

関連記事

目次から探す