30001：不透明整数栈 ADT

题目

把整数栈设计成不透明 ADT：公开头文件只描述行为契约，动态数组及其状态只能由实现文件管理。

解析

头文件中的不完整类型：

typedef struct IntStack IntStack;

允许调用方持有 IntStack *，但无法访问或依赖结构体成员。实现文件再给出完整定义，从而可以在不修改公开接口的情况下替换底层表示。

实现维持：

size <= capacity
capacity == 0 当且仅当 items == NULL

扩容结果先由临时指针接收。只有分配成功后才更新栈，所以 push 的失败分支不会改变原有元素、大小或容量。

解析

int_stack.h

#ifndef MDR_INT_STACK_H
#define MDR_INT_STACK_H

#include <stddef.h>

typedef struct IntStack IntStack;

typedef enum {
    INT_STACK_OK,
    INT_STACK_EMPTY,
    INT_STACK_INVALID,
    INT_STACK_OUT_OF_MEMORY
} IntStackStatus;

IntStack *int_stack_create(void);
void int_stack_destroy(IntStack *stack);
IntStackStatus int_stack_push(IntStack *stack, int value);
IntStackStatus int_stack_pop(IntStack *stack, int *out);
IntStackStatus int_stack_peek(const IntStack *stack, int *out);
size_t int_stack_size(const IntStack *stack);

#endif

int_stack.c

#include "int_stack.h"

#include <stdint.h>
#include <stdlib.h>

struct IntStack {
    int *items;
    size_t size;
    size_t capacity;
};

static IntStackStatus int_stack_grow(IntStack *stack) {
    size_t max_capacity = SIZE_MAX / sizeof *stack->items;
    if (stack->capacity >= max_capacity) {
        return INT_STACK_OUT_OF_MEMORY;
    }

    size_t next;
    if (stack->capacity == 0) {
        next = max_capacity < 8 ? max_capacity : 8;
    } else if (stack->capacity > max_capacity / 2) {
        next = max_capacity;
    } else {
        next = stack->capacity * 2;
    }

    int *replacement = realloc(
        stack->items,
        next * sizeof *replacement
    );
    if (replacement == NULL) {
        return INT_STACK_OUT_OF_MEMORY;
    }

    stack->items = replacement;
    stack->capacity = next;
    return INT_STACK_OK;
}

IntStack *int_stack_create(void) {
    return calloc(1, sizeof(IntStack));
}

void int_stack_destroy(IntStack *stack) {
    if (stack == NULL) {
        return;
    }
    free(stack->items);
    free(stack);
}

IntStackStatus int_stack_push(IntStack *stack, int value) {
    if (stack == NULL) {
        return INT_STACK_INVALID;
    }
    if (stack->size == stack->capacity) {
        IntStackStatus status = int_stack_grow(stack);
        if (status != INT_STACK_OK) {
            return status;
        }
    }

    stack->items[stack->size] = value;
    ++stack->size;
    return INT_STACK_OK;
}

IntStackStatus int_stack_pop(IntStack *stack, int *out) {
    if (stack == NULL || out == NULL) {
        return INT_STACK_INVALID;
    }
    if (stack->size == 0) {
        return INT_STACK_EMPTY;
    }

    *out = stack->items[stack->size - 1];
    --stack->size;
    return INT_STACK_OK;
}

IntStackStatus int_stack_peek(
    const IntStack *stack,
    int *out
) {
    if (stack == NULL || out == NULL) {
        return INT_STACK_INVALID;
    }
    if (stack->size == 0) {
        return INT_STACK_EMPTY;
    }

    *out = stack->items[stack->size - 1];
    return INT_STACK_OK;
}

size_t int_stack_size(const IntStack *stack) {
    return stack == NULL ? 0 : stack->size;
}

来源与改编

题型借鉴 Pat Morin 的 Open Data Structures 中数组栈及抽象接口的组织方式，原作采用 CC BY 2.5 Canada。本题改写为不透明 C 接口，并补充状态码、溢出与失败保证；完整记录见习题来源与许可。