C言語で学ぶスタックの基本概念と配列による実装方法

データ構造とは、構造化された方法で整理・管理されたデータの集合体のことです。データ構造は大きく「線形データ構造」と「非線形データ構造」の2種類に分類されます。

データ構造の2つの分類

線形データ構造

データが一本の線上に順番に並ぶように配置される構造です。

例： 配列、構造体、スタック、キュー、連結リストなど

非線形データ構造

データが階層的・網目的に配置される構造です。

例： 木（ツリー）、グラフ、集合、テーブルなど

C言語におけるスタックとは

スタックは線形データ構造の一種で、データの挿入と削除が同じ一端（トップ）でのみ行われるという特徴を持ちます。この仕組みは「後入れ先出し（LIFO：Last In First Out）」と呼ばれ、最後に積んだデータが最初に取り出されます。

スタックの基本操作

• Push（プッシュ） – スタックのトップに新しい要素を挿入する。
• Pop（ポップ） – スタックのトップから要素を取り除く（削除する）。

たとえば、10・20・30・40・50 の順にプッシュした後、pop() を1回呼び出すと次のようになります。

Deleted element = 50
Item = a [top]
top --

• pop(), pop(), pop(), pop()

Deleted element = 40
Deleted element = 30
Deleted element = 20
Deleted element = 10

• pop()

さらに pop() を呼び出すと、スタックは空のため「スタックアンダーフロー」が発生します。

スタックの重要な条件

• スタックオーバーフロー – すでに満杯のスタックに対して、さらに要素を挿入しようとすると発生するエラー。

• スタックアンダーフロー – 空のスタックから要素を削除しようとすると発生するエラー。

Push()・Pop()・Display() のアルゴリズム

それぞれの操作は、以下の手順で実装できます。

Push() のアルゴリズム

• まずスタックオーバーフローが起きていないか確認します。

if (top == n-1)
    printf("stack over flow");

• 問題がなければ、スタックのトップに要素を挿入します。

top++;
a[top] = item;

Pop() のアルゴリズム

• まずスタックアンダーフローが起きていないか確認します。

if (top == -1)
    printf("stack under flow");

• 問題がなければ、トップの要素を取り出して削除します。

item = a[top];
top--;

Display() のアルゴリズム

• まずスタックが空かどうかを確認します。

if (top == -1)
    printf("stack is empty");

• 空でなければ、下位から上位へ順に要素を表示します。

for (i = 0; i <= top; i++)
    printf("%d", a[i]);

配列を使ったスタック実装のCプログラム例

以下は、配列を使用してスタックを実装したC言語のサンプルプログラムです。

#include<stdio.h>
#include <conio.h>

int top = -1, n, a[100];

void push(void){
    int item;
    if (top == n-1)
        printf("スタックオーバーフロー\n");
    else{
        printf("挿入する要素を入力してください：");
        scanf("%d", &item);
        top++;
        a[top] = item;
    }
}
void pop(void){
    int item;
    if (top == -1)
        printf("スタックアンダーフロー\n");
    else{
        item = a[top];
        top--;
        printf("削除された要素 = %d\n", item);
    }
}
void display(void){
    int i;
    if (top == -1)
        printf("スタックは空です\n");
    else{
        printf("スタックの内容：");
        for (i = 0; i <= top; i++)
            printf("%d \t", a[i]);
        printf("\n");
    }
}
int main(void){
    int ch;
    clrscr();
    printf("スタックのサイズを入力してください：");
    scanf("%d", &n);
    printf("スタックの実装\n");
    printf("1. プッシュ\n");
    printf("2. ポップ\n");
    printf("3. 終了\n");
    do{
        printf("選択してください：");
        scanf("%d", &ch);
        switch (ch){
            case 1 : push();
                display();
                break;
            case 2 : pop();
                display();
                break;
            case 3 : exit(0);
        }
    }while (ch >= 1 && ch <= 3);
    getch();
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が得られます。

スタックのサイズを入力してください：5 [ユーザー入力]
スタックの実装
1. プッシュ　2. ポップ　3. 終了
選択してください：1 [ユーザー入力]
挿入する要素を入力してください：10
スタックの内容：10
選択してください：1
挿入する要素を入力してください：20
スタックの内容：10 20
選択してください：2
削除された要素 = 20
スタックの内容：10
選択してください：2
削除された要素 = 10
スタックは空です
選択してください：2
スタックアンダーフロー
選択してください：1
挿入する要素を入力してください：30
スタックの内容：30

このように、スタックでは最後に追加した要素から順に取り出される（LIFO）動作を確認できます。また、空のスタックへのポップ操作ではアンダーフローが検出され、適切なメッセージが表示されることも分かります。