C/C++のデータ構造

C・C++のスタック（stack）

このレッスンでは、Cの固定長配列とC++のstd::stackで、後入れ先出しのスタックの操作を実装します。

はじめに

スタック（stack）は一番上でしか操作できません。pushは新しい要素を一番上に積み、popは一番上の要素を取り出し、peekは取り出さずに一番上の要素を確認します。スタックは積み重ねた本のように、後入れ先出し（LIFO）のルールで動きます。

大切なポイント

操作を書く前に、データ構造で常に成り立つべき条件（不変条件、invariant）を決めましょう。
空のとき、満杯のとき、メモリ確保に失敗したときもきちんと処理しましょう。
各操作の計算量とメモリ管理を、あわせて評価しましょう。

動きで理解する

pushとpopを試すと、最後に入れた要素が必ず最初に出ることがわかります。

CとC++のコード例

実行 →

main.c

#include <stdio.h>

typedef struct {
    int data[8];
    int size;
} Stack;

int push(Stack *stack, int value) {
    if (stack->size == 8) return 0;
    stack->data[stack->size++] = value;
    return 1;
}

int pop(Stack *stack, int *value) {
    if (stack->size == 0) return 0;
    *value = stack->data[--stack->size];
    return 1;
}

int main(void) {
    Stack stack = {{0}, 0};
    int value;
    push(&stack, 10);
    push(&stack, 20);
    pop(&stack, &value);
    printf("%d\n", value);
}

実行結果

C++

実行 →

main.cpp

#include <iostream>
#include <stack>

int main() {
    std::stack<int> values;
    values.push(10);
    values.push(20);
    std::cout << values.top() << '\n';
    values.pop();
}

実行結果

CとC++の比較

Cのバージョンは8要素の固定長配列を使うので、push時にスタックが満杯（スタックオーバーフロー）でないか、pop時に空でないかを確認する必要があります。C++のstd::stackは内部のコンテナを通して容量を自動で管理し、LIFOのルールで同じpush、pop、topの操作を提供します。

データ（struct）と操作は分かれていて、メモリは手作業で確保・解放します。

C++

クラスとコンテナが、データの正しさを守り、リソースを自分で管理します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

空の状態と、容量の上限に達したときのテストを追加しましょう。
メモリを解放する処理を書き、メモリリークがないか確認しましょう。
標準ライブラリの対応するコンテナと計算量を比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

Mini Stack-Language Interpreter Evaluate a small stack language. 難しい

すべてのチャレンジ