栈实现

const int N = 1e5 + 10;
int stk[N], n;

void push(int data) {
    stk[++n] = data;
}
void pop() {
    n--;
}
int top() {
    return stk[n];
}
bool empty() {
    return n == 0;
}
int size() {
    return n;
}

typedef int data_type;
typedef struct {
    // 本质是一个访问受限的动态顺序表
    data_type* pdata;
    int size;
    int capacity;
} stack;

static void check_capacity(stack* ptr) {
    assert(ptr);

    if (ptr->capacity == ptr->size) {
        int newcapacity = (ptr->capacity == 0) ? 4 : ptr->capacity * 2; // 每次增容两倍
        data_type* ptmp = (data_type*)realloc(ptr->pdata, newcapacity * sizeof(data_type));
        if (ptmp == NULL)
            exit(0);
        else {
            ptr->pdata = ptmp;
            ptr->capacity = newcapacity;
        }
    }
}

stack* init() {
    stack* ret = (stack*)malloc(sizeof(stack));
    if (ret == NULL)
        exit(0);

    ret->pdata = NULL;
    ret->size = 0;
    ret->capacity = 0;
    return ret;
}

void destory(stack* ptr) {
    assert(ptr && ptr->pdata);

    free(ptr->pdata);
    free(ptr);
}

void push(stack* ptr, data_type data) {
    check_capacity(ptr);

    ptr->pdata[++ptr->size] = data;
}

void pop(stack* ptr) {
    ptr->size--;
}

bool empty(stack* ptr) {
    return ptr->size == 0;
}

int size(stack* ptr) {
    return ptr->size;
}

int top(stack* ptr) {
    return ptr->pdata[ptr->size];
}