C言語でのスタックの実装方法！

Last updated at 2025-05-22Posted at 2025-05-22

スタックの実装方法 🎉

データ構造としては特別なものではなく、配列や連結リストの“上手な使い方”の一つにすぎません。使いどころを理解することが大切です

Qiita: スタックとキューを極める！〜考え方と使い所を特集〜

目次 📖

スタックとキューの違い ✨
スタックADTとは？ 📚
スタックの実装方法
おわりに 🎯

スタックとキューの違い ✨

スタック は LIFO（Last In, First Out）
キュー は FIFO（First In, First Out）

操作	スタック	キュー
追加する時	一番上に追加 🆙	一番下に追加 🆗
取り出す時	一番上から取り出し 🆙	一番下から取り出し 🆗

スタックADTとは？ 📚

ADT（Abstract Data Type） とは、操作の意味と性質を抽象化した“型”のことです。
スタックADTでは、主に以下の操作を定義します。

push(data)：データを追加
pop()：一番上のデータを取り出して削除
top()：一番上のデータを参照（削除しない）
size()：要素数を返す
isEmpty()：空かどうか判定
isFull()：満杯かどうか判定（配列実装のみ）
delete()：メモリ解放

スタックの実装方法

1. 単純配列実装 🗃️

データ構造

typedef struct {
    int top;        // 現在の先頭位置（インデックス）
    int capacity;   // 配列の最大サイズ
    int *array;     // データを格納する配列
} ArrayStack;

作成・初期化

ArrayStack* createStack() {
    ArrayStack *stack = malloc(sizeof(ArrayStack));
    if (!stack) return NULL;
    stack->capacity = 4;     // 初期容量はお好みでOK
    stack->top      = -1;    // 空のときは -1
    stack->array    = malloc(sizeof(int) * stack->capacity);
    if (!stack->array) {
        free(stack);
        return NULL;
    }
    return stack;
}

主要操作

push

int push(ArrayStack *stack, int data) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return 0;
    }
    stack->array[++(stack->top)] = data;
    return 1;
}

pop

int pop(ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->array[(stack->top)--];
}

補助操作

top

int top(const ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return stack->array[stack->top];
}

size

int size(const ArrayStack *stack) {
    return stack->top + 1;
}

isEmpty

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

isFull

int isFull(const ArrayStack *stack) {
    return (stack->top == stack->capacity - 1);
}

delete

void deleteStack(ArrayStack *stack) {
    if (!stack) return;
    free(stack->array);
    free(stack);
}

単純配列実装はシンプルですが、容量変更ができません。

2. 動的配列実装 🔄

容量を自動で拡張できるよう、繰り返し二倍法を使います。

DoubleStack 関数例

void doubleStack(ArrayStack *stack) {
    int newCap = stack->capacity * 2;
    int *newArr = malloc(sizeof(int) * newCap);
    if (!newArr) return;
    for (int i = 0; i <= stack->top; i++) {
        newArr[i] = stack->array[i];
    }
    free(stack->array);
    stack->array    = newArr;
    stack->capacity = newCap;
}

push の改良例

int push(ArrayStack *stack, int data) {
    if (isFull(stack)) {
        doubleStack(stack);  // 足りなくなったら容量拡張！
    }
    stack->array[++(stack->top)] = data;
    return 1;
}

動的配列実装なら要素数の増加を自動でカバーできます。

3. 連結リスト実装 🌿

ノードを使ってリンクすることで、容量制限なしのスタックを実現します。