从叠盘子到括号匹配——用C实现栈

具体实现时，初始化函数把指针置空、容量和栈顶标记归零：

void StackInit(Stack* pst) {
    assert(pst);
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
}

销毁函数负责释放内存并把结构体成员重置：

void StackDestroy(Stack* pst) {
    assert(pst);
    if (pst->a != NULL) {
        free(pst->a);
        pst->a = NULL;
    }
    pst->capacity = 0;
    pst->top = 0;
}

入栈是核心。当容量已满（top == capacity）时需要扩容：第一次分配4个元素的空间，之后每次容量翻倍。realloc可能会失败，所以用临时指针接收，检查后才赋值。最后把元素放到a[top]，然后top自增：

void Push(Stack* pst, STDatatype x) {
    assert(pst);
    if (pst->capacity == pst->top) {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDatatype* tmp = (STDatatype*)realloc(pst->a, newcapacity * sizeof(STDatatype));
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    pst->a[pst->top++] = x;
}

出栈就简单多了，只要保证栈非空，直接top--即可。数据仍然留在内存里，但逻辑上已经不属于栈。

void Pop(Stack* pst) {
    assert(pst && pst->top > 0);
    pst->top--;
}

获取栈顶元素时，注意索引是top-1：

STDatatype top(Stack* pst) {
    assert(pst && pst->top > 0);
    return pst->a[pst->top - 1];
}

元素个数直接返回top，判空就是top == 0。

int Size(Stack* pst) {
    assert(pst);
    return pst->top;
}

bool Empty(Stack* pst) {
    assert(pst);
    return pst->top == 0;
}

测试代码演示了基本用法，可以看到连续的入栈出栈以及判空：

void Test() {
    Stack st = {0};
    StackInit(&st);
    Push(&st, 1);
    printf("%d\n", top(&st));
    Push(&st, 2);
    printf("%d\n", top(&st));
    Push(&st, 3);
    printf("%d\n", top(&st));
    Push(&st, 4);
    printf("%d\n", top(&st));
    printf("当前栈中元素的总个数为：%d\n", Size(&st));

    Pop(&st);
    printf("%d\n", top(&st));
    Pop(&st);
    printf("%d\n", top(&st));
    Pop(&st);
    printf("%d\n", top(&st));
    Pop(&st);
    if (Empty(&st)) printf("当前栈为空\n");
    else printf("当前栈不为空\n");
    printf("当前栈中元素的总个数为：%d\n", Size(&st));
    StackDestroy(&st);
}

有了自己的栈，我们来看一个经典问题：有效的括号。题目要求判断一个只包含 ()、{}、[] 的字符串是否有效——不但每种括号数量要一致，左右顺序也必须正确。

仅仅统计次数无法处理 "][[" 这种反例，关键是要保证每个右括号都能与最近的左括号配对。栈正好匹配这种'最近相关'的特性：遇左括号入栈，遇右括号弹出栈顶左括号并检查是否匹配。遍历结束时栈为空才说明完全匹配。

这里给出C++版本，用 std::stack 直接完成：

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            // 左括号入栈
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                st.push(s[i]);
            } else {
                // 右括号时，栈内必须有左括号
                if (st.empty()) return false;
                char ch = st.top();
                st.pop();
                if ((ch == '(' && s[i] != ')') ||
                    (ch == '{' && s[i] != '}') ||
                    (ch == '[' && s[i] != ']'))
                    return false;
            }
        }
        // 最后栈空才是有效括号
        return st.empty();
    }
};

栈的手写实现虽然短小，却覆盖了内存管理、边界检查和典型设计决策。它在很多场景里都值得自己造一次轮子。