データ構造 - スタック

スタック(Stack)は、後入れ先出し(Last In First Out、LIFO)の原則に従う線形データ構造です。積み重ねた皿のように、一番上からしか置けず、一番上からしか取り出せないと理解できます。


スタックの概念と原理

スタック (Stack) — LIFO 原理の模式図
スタックトップ (Top) — ここからしか操作できない
皿 1 (スタックの底)
皿 2
皿 3
皿 4 (スタックトップ)
スタックの底 (Bottom) — 最後にしか取り出せない
▲ push(プッシュ) ▼ pop(ポップ)

LIFO の確認:プッシュ 10→20→30、ポップ 30→20→10(後入れ先出し)| スタックはスタックトップのみを扱い、中間は気にしない

配列による実装(順序スタック)

格納:固定サイズ配列 + top ポインタ

push:items[++top] = value

pop:return items[top--]

利点:アクセスが速い、キャッシュに優しい、実装が簡単

欠点:容量が固定、オーバーフローする可能性がある

連結リストによる実装(連結スタック)

格納:動的ノード + スタックトップポインタ(連結リストの先頭)

push:先頭挿入法 newNode->next = top

pop:top = top->next; free(旧先頭)

利点:容量制限なし、柔軟に動的拡張可能

欠点:余分なポインタのオーバーヘッド、キャッシュに不向き


配列によるスタックの実装

例

#include <stdio.h>
#include <stdbool.h> /* bool 型 */

#define MAX_SIZE 100 /* スタックの最大容量 */

/* スタック構造体:データ配列とスタックトップポインタを含む */
struct Stack {
    int items[MAX_SIZE];  /* スタック要素を格納する配列 */
    int top;              /* スタックトップポインタ、-1 はスタックが空を表す */
};

/* スタックの初期化:top を -1 にする */
void initStack(struct Stack* s) {
    s->top = -1;
}

/* 空判定:top が -1 のときスタックは空 */
bool isEmpty(struct Stack* s) {
    return s->top == -1;
}

/* 満杯判定:top が容量上限 -1 に達したときスタックは満杯 */
bool isFull(struct Stack* s) {
    return s->top == MAX_SIZE - 1;
}

/* プッシュ(push):要素をスタックトップに置く
先に top を移動し、それからデータを書き込む */

void push(struct Stack* s, int value) {
    if (isFull(s)) {
        printf("スタックが満杯のため、プッシュできません!\n");
        return;
    }
    s->items[++s->top] = value;  /* top を先に +1 し、それから代入する */
    printf("プッシュ: %d\n", value);
}

/* ポップ(pop):スタックトップの要素を削除して返す
先にデータを取り出し、それから top を移動する */

int pop(struct Stack* s) {
    if (isEmpty(s)) {
        printf("スタックが空のため、ポップできません!\n");
        return -1;  /* 特殊な値を返してエラーを表す */
    }
    return s->items[s->top--];  /* 先に値を返し、top を 1 減らす */
}

/* スタックトップの参照(peek):ポップせず、参照のみ */
int peek(struct Stack* s) {
    if (isEmpty(s)) {
        printf("スタックが空です!\n");
        return -1;
    }
    return s->items[s->top];
}

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);  /* プッシュ: 10 */
    push(&s, 20);  /* プッシュ: 20 */
    push(&s, 30);  /* プッシュ: 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 */

    if (isEmpty(&s)) {
        printf("スタックは空です\n");                /* 出力: スタックは空です */
    }
    return 0;
}

連結リストによるスタックの実装

例

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

/* 連結リストのノード */
struct Node {
    int data;
    struct Node* next;
};

/* プッシュ(push):連結リストの先頭をスタックトップとし、先頭挿入法
時間計算量:O(1) */

struct Node* push(struct Node* top, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;   /* 新しいノードが元のスタックトップを指す */
    printf("プッシュ: %d\n", value);
    return newNode;          /* 新しいノードが新しいスタックトップになる */
}

/* ポップ(pop):連結リストの先頭ノードを削除する
時間計算量:O(1) */

struct Node* pop(struct Node* top) {
    if (top == NULL) {
        printf("スタックが空です!\n");
        return NULL;
    }
    struct Node* temp = top;
    printf("ポップ: %d\n", top->data);
    top = top->next;   /* スタックトップを後へ移動 */
    free(temp);         /* 古いスタックトップを解放 */
    return top;
}

/* 空判定 */
bool isEmpty(struct Node* top) {
    return top == NULL;
}

int main() {
    struct Node* stackTop = NULL;  /* 初期状態ではスタックは空 */

    stackTop = push(stackTop, 100);  /* プッシュ: 100 */
    stackTop = push(stackTop, 200);  /* プッシュ: 200 */
    stackTop = push(stackTop, 300);  /* プッシュ: 300 */

    printf("スタックトップ: %d\n", stackTop->data);  /* 出力: スタックトップ: 300 */

    stackTop = pop(stackTop);  /* ポップ: 300 */
    stackTop = pop(stackTop);  /* ポップ: 200 */
    stackTop = pop(stackTop);  /* ポップ: 100 */

    if (isEmpty(stackTop)) {
        printf("スタックは空です\n");      /* 出力: スタックは空です */
    }
    return 0;
}

連結リストによるスタックの利点は、理論上固定の容量制限がなく、システムの利用可能メモリのみに制限されることです。ただし、各ノードには追加のポインタ用記憶領域が必要です。


スタックの応用場面

応用場面説明なぜスタックを使うのか
関数呼び出しスタック関数の戻り先アドレスとローカル変数を保存する関数呼び出しは入れ子になっており、自然と LIFO になる
括弧の対応コード内の括弧が正しく対応しているかを検査する左括弧が出たらスタックにプッシュし、右括弧がスタックトップと対応したらポップする
元に戻す操作テキストエディタやブラウザの元に戻す機能操作のたびにスタックにプッシュし、元に戻すときにポップする
式の評価中置記法/後置記法の式の値を計算するオペランドをスタックにプッシュし、演算子で計算した結果をスタックにプッシュする
深さ優先探索グラフの DFS 走査アルゴリズム明示的にスタックまたは再帰を使用(暗黙的に呼び出しスタックを使用)
その他の拡張