C言語で連結リストを使ったスタックの実装方法を徹底解説

はじめに

スタック（Stack）は「後入れ先出し（LIFO：Last In First Out）」という特徴を持つ基本的なデータ構造です。配列ではなく連結リスト（リンクリスト）を使ってスタックを実装すると、メモリを動的に確保できるため、スタックオーバーフローやスタックアンダーフローといった問題を効果的に回避できます。

C言語におけるスタックに対する主な操作は以下の2つです。

• Push（プッシュ） … スタックの先頭に要素を追加する
• Pop（ポップ） … スタックの先頭から要素を取り出す

この記事では、それぞれの操作の仕組みと、実際に動作するC言語のサンプルプログラムを詳しく解説します。

Push（プッシュ）の実装

Pushは、新しいノードを動的に確保し、スタックの先頭に挿入する処理です。連結リストを使った基本的な実装は次のとおりです。

&item = 10;
newnode = (node*) malloc (sizeof (node));
newnode->data = item;
newnode->link = NULL;
newnode->link = start;
start = newnode;

この処理では、まず malloc によって新しいノードのメモリを確保し、データを格納したうえで、既存の先頭ノードへのポインタをつなぎ替えます。最後に start を新しいノードに更新することで、要素がスタックの先頭に追加されます。

Pop（ポップ）の実装

Popは、スタックの先頭にある要素を削除して取り出す処理です。スタックが空の場合に削除を行おうとするとエラーになるため、必ず空チェックを行います。基本構文は以下のとおりです。

構文

if (start == NULL)
    printf("Deletion is not possible.List is empty");
else {
    temp = start;
    start = start->link;
    free(temp);
}

このコードでは、先頭ノードが存在しない場合は「削除不可・リストが空」というメッセージを表示し、存在する場合は一時ポインタ temp に先頭ノードを退避させてから、free 関数でメモリを解放します。これによりメモリリークを防げます。

サンプルプログラム全体

以下は、連結リストを使用してスタックを実装した完全なC言語プログラムです。Push、Pop、Top（先頭要素の参照）、Empty判定、表示、要素数カウント、スタック破棄など、多彩な機能をメニュー形式で提供しています。

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

struct node {
    int info;
    struct node *ptr;
} *top, *top1, *temp;

int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();

int count = 0;

void main() {
    int no, ch, e;
    printf("\n 1 - Push");
    printf("\n 2 - Pop");
    printf("\n 3 - Top");
    printf("\n 4 - Empty");
    printf("\n 5 - Exit");
    printf("\n 6 - Display");
    printf("\n 7 - Stack Count");
    printf("\n 8 - Destroy stack");
    create();
    while (1) {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("Enter element : ");
                scanf("%d", &no);
                push(no);
                break;
            case 2:
                pop();
                break;
            case 3:
                if (top == NULL)
                    printf("stack is empty");
                else {
                    e = topelement();
                    printf("\n Top element : %d", e);
                }
                break;
            case 4:
                empty();
                break;
            case 5:
                exit(0);
            case 6:
                display();
                break;
            case 7:
                stack_count();
                break;
            case 8:
                destroy();
                break;
            default:
                printf(" wrong choice:Try again ");
                break;
        }
    }
}

// 空のスタックを作成
void create() {
    top = NULL;
}

void stack_count() {
    printf("\n no: of elements in stack : %d", count);
}

// データをプッシュ
void push(int data) {
    if (top == NULL) {
        top = (struct node *)malloc(1 * sizeof(struct node));
        top->ptr = NULL;
        top->info = data;
    } else {
        temp = (struct node *)malloc(1 * sizeof(struct node));
        temp->ptr = top;
        temp->info = data;
        top = temp;
    }
    count++;
}

void display() {
    top1 = top;
    if (top1 == NULL) {
        printf("empty stack");
        return;
    }
    while (top1 != NULL) {
        printf("%d ", top1->info);
        top1 = top1->ptr;
    }
}

void pop() {
    top1 = top;
    if (top1 == NULL) {
        printf("\n error");
        return;
    } else
        top1 = top1->ptr;
        printf("\n Popped value : %d", top->info);
        free(top);
        top = top1;
        count--;
}

int topelement() {
    return (top->info);
}

// スタックが空かどうか確認
void empty() {
    if (top == NULL)
        printf("\n empty stack");
    else
        printf("\n stack not empty with %d values", count);
}

void destroy() {
    top1 = top;
    while (top1 != NULL) {
        top1 = top->ptr;
        free(top);
        top = top1;
        top1 = top1->ptr;
    }
    free(top1);
    top = NULL;
    printf("\n all are destroyed");
    count = 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下のような出力が得られます。各操作が正しく動作している様子を確認できます。

1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice: 1
Enter element: 23
Enter choice: 1
Enter element: 45
Enter choice: 1
Enter element: 56
Enter choice: 2
Popped value: 56
Enter choice: 6
45 23
Enter choice: 8
all are destroyed
Enter choice: 6
empty stack
Enter choice: 5

まとめ

このように、C言語では連結リストを利用することで、サイズに制限のない柔軟なスタックを実装できます。動的メモリ確保（malloc / free）を適切に行うことで、オーバーフローやアンダーフローの問題を回避しながら、PushやPopなどの基本操作を安全に実現できる点が大きなメリットです。ぜひ実際にコードを動かして、スタックの動作原理を体感してみてください。