C/C++のデータ構造

Stackデータ構造

Stackはtopだけを操作し、pushで追加、popで削除、peekで参照します。

Stackデータ構造とは？

Stackはtopだけを操作し、pushで追加、popで削除、peekで参照します。

Last-in-first-out操作を実装します。

重要なポイント

操作より先にinvariantを定義します。
空・満杯・allocation失敗を処理します。
計算量とownershipを一緒に評価します。

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版はoverflow/underflowを検出します。std::stackは内部containerでcapacityを管理します。

構造体と操作は分離され、allocationは明示的です。

C++

classとcontainerがinvariantとresourceを管理します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

空と容量境界をテストします。
cleanupを実装しleakを確認します。
standard containerと比較します。