数据结构C语言练习(栈)

一、引言

在LeetCode 20 题 “有效的括号” 中，我们需要判断一个只包含 {} [] () 的字符串是否有效。本文通过实现一个动态栈结构，详细讲解代码逻辑，帮助理解栈在括号匹配问题中的应用。

二、栈结构核心函数讲解

1. 栈的初始化：StackInit

void StackInit(Stack* ps) {
    ps->_a = NULL;
    ps->_top = ps->_capacity = 0;
}

• 作用：初始化栈的成员变量。
• 细节：将存储数据的指针 _a 置为空，栈顶 _top 和容量 _capacity 初始化为 0，为后续操作做准备。

2. 获取栈顶元素：StackTop

STDataType StackTop(Stack* ps) {
    return ps->_a[ps->_top - 1];
}

• 作用：返回栈顶元素。
• 细节：通过 _top - 1 定位栈顶元素（因为 _top 指向栈顶下一个位置），使用前需确保栈非空。

3. 入栈操作：StackPush

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->_top == ps->_capacity) {
        int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            exit(1);
        }
        ps->_a = tmp;
        ps->_capacity = newCapacity;
    }
    ps->_a[ps->_top++] = data;
}

• 作用：向栈中插入元素，支持动态扩容。
• 细节：
  • 先检查栈空间是否不足，不足则用 realloc 扩容（初始容量 4，之后双倍扩容）。
  • 插入元素后，_top 自增指向下一个位置。

4. 检查栈是否为空：StackEmpty

bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->_top == 0;
}

• 作用：判断栈是否为空。
• 细节：通过 _top 是否为 0 判断，是则返回 true，否则 false。

5. 出栈操作：StackPop

void StackPop(Stack* ps) {
    assert(!StackEmpty(ps));
    ps->_top--;
}

• 作用：删除栈顶元素。
• 细节：先通过 assert 确保栈非空，再将 _top 减 1，实现逻辑删除。

6. 销毁栈：StackDestroy

void StackDestroy(Stack* ps) {
    if (ps->_a) {
        free(ps->_a);
    }
    ps->_a = NULL;
    ps->_top = ps->_capacity = 0;
}

• 作用：释放栈占用的内存，防止内存泄漏。
• 细节：先释放动态分配的数组 _a，再将成员变量重置为初始状态。

三、核心逻辑：isValid 函数

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    char* ps = s;
    while (*ps != '\0') {
        if (*ps == '(' || *ps == '[' || *ps == '{') {
            StackPush(&st, *ps);
        } else {
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            if ((top == '(' && *ps == ')') || (top == '[' && *ps == ']') || (top == '{' && *ps == '}')) {
                StackPop(&st);
            } else {
                StackDestroy(&st);
                return false;
            }
        }
        ps++;
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

• 逻辑解析：
  1. 初始化栈：创建栈 st 并初始化。
  2. 遍历字符串：
     • 遇到左括号 ({[，直接入栈。
     • 遇到右括号 )}]：
       • 若栈为空，说明无匹配左括号，直接返回 false。
       • 检查栈顶元素是否匹配当前右括号，匹配则出栈，不匹配返回 false。
  3. 最终检查：遍历结束后，若栈为空，说明所有括号匹配，否则不匹配。
  4. 销毁栈：无论结果如何，最后销毁栈释放资源。

四、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef char STDataType;
typedef struct Stack {
    STDataType* _a;
    int _top;
    int _capacity;
} Stack;

void StackInit(Stack* ps) {
    ps->_a = NULL;
    ps->_top = ps->_capacity = 0;
}

STDataType StackTop(Stack* ps) {
    return ps->_a[ps->_top - 1];
}

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->_top == ps->_capacity) {
        int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            exit(1);
        }
        ps->_a = tmp;
        ps->_capacity = newCapacity;
    }
    ps->_a[ps->_top++] = data;
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->_top == 0;
}

void StackPop(Stack* ps) {
    assert(!StackEmpty(ps));
    ps->_top--;
}

void StackDestroy(Stack* ps) {
    if (ps->_a) {
        free(ps->_a);
    }
    ps->_a = NULL;
    ps->_top = ps->_capacity = 0;
}

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    char* ps = s;
    while (*ps != '\0') {
        if (*ps == '(' || *ps == '[' || *ps == '{') {
            StackPush(&st, *ps);
        } else {
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            if ((top == '(' && *ps == ')') || (top == '[' && *ps == ']') || (top == '{' && *ps == '}')) {
                StackPop(&st);
            } else {
                StackDestroy(&st);
                return false;
            }
        }
        ps++;
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

五、总结

通过实现动态栈，我们高效解决了括号匹配问题。栈的 “后进先出” 特性完美契合括号匹配逻辑：左括号入栈，右括号与栈顶匹配。这一思路可扩展到更多需要匹配关系的场景（如标签匹配、表达式校验等）。理解栈的底层实现，能更灵活地应用这一数据结构解决实际问题。