数据结构精讲：从栈的定义到链式实现，再到LeetCode实战

// ADT Stack (stack)
Data:
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。

Operation:
    InitStack(*S);          // 初始化操作，建立一个空栈S。
    DestroyStack(*S);       // 若栈存在，则销毁它。
    ClearStack(*S);         // 将栈清空。
    StackEmpty(S);          // 若栈为空，返回true，否则返回false。
    GetTop(S, *e);          // 若栈存在且非空，用*e返回栈顶元素。
    Push(*S, e);            // 若栈S存在，插入新元素e到栈S中并成为栈顶元素。
    Pop(*S, *e);            // 删除栈S中栈顶元素，并用*e返回其值。
    StackLength(S);         // 返回栈S的元素个数。
endADT

typedef int SElemType; // 假设元素类型为int

typedef struct {
    SElemType data[MAXSIZE]; // 存储元素的数组
    int top;                 // 栈顶指针
} SqStack;

/* 进栈操作 */
Status Push(SqStack *S, SElemType e) {
    if (S->top == MAXSIZE - 1) { // 判断是否栈满
        return ERROR;
    }
    S->top++;              // 栈顶指针加1
    S->data[S->top] = e;   // 将新元素赋值给栈顶空间
    return OK;
}

/* 出栈操作 */
Status Pop(SqStack *S, SElemType *e) {
    if (S->top == -1) { // 判断是否栈空
        return ERROR;
    }
    *e = S->data[S->top]; // 将栈顶元素值赋给e
    S->top--;             // 栈顶指针减1
    return OK;
}

typedef struct {
    SElemType data[MAXSIZE];
    int top1; // 栈1的栈顶指针
    int top2; // 栈2的栈顶指针
} SqDoubleStack;

/* 入栈操作，需指定是哪个栈 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
    if (S->top1 + 1 == S->top2) { // 栈满判断
        return ERROR;
    }
    if (stackNumber == 1) {
        S->data[++S->top1] = e; // 栈1入栈
    } else if (stackNumber == 2) {
        S->data[--S->top2] = e; // 栈2入栈
    }
    return OK;
}

/* 出栈操作，同样需指定是哪个栈 */
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (S->top1 == -1) { // 栈1空
            return ERROR;
        }
        *e = S->data[S->top1--]; // 栈1出栈
    } else if (stackNumber == 2) {
        if (S->top2 == MAXSIZE) { // 栈2空
            return ERROR;
        }
        *e = S->data[S->top2++]; // 栈2出栈
    }
    return OK;
}

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top; // 栈顶指针
    int count;        // 栈中元素个数
} LinkStack;

/* 进栈操作 */
Status Push(LinkStack *S, SElemType e) {
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!s) {
        return ERROR;
    }
    s->data = e;
    s->next = S->top; // 新节点指向原栈顶
    S->top = s;       // 栈顶指针指向新节点
    S->count++;
    return OK;
}

/* 出栈操作 */
Status Pop(LinkStack *S, SElemType *e) {
    LinkStackPtr p;
    if (S->top == NULL) { // 栈空
        return ERROR;
    }
    *e = S->top->data;
    p = S->top;
    S->top = S->top->next; // 栈顶指针下移
    free(p);               // 释放原栈顶节点
    S->count--;
    return OK;
}

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool isValid(char * s){
    int len = strlen(s);
    char *stack = (char*)malloc(len * sizeof(char)); // 用数组模拟栈
    int top = -1;

    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c == '(' || c == '{' || c == '[') {
            stack[++top] = c; // 左括号入栈
        } else {
            if (top == -1) return false; // 栈空，却遇到右括号，无效
            char topChar = stack[top--]; // 弹出栈顶
            // 判断是否匹配
            if ((c == ')' && topChar != '(') ||
                (c == '}' && topChar != '{') ||
                (c == ']' && topChar != '[')) {
                return false;
            }
        }
    }

    free(stack);
    return top == -1; // 栈空则有效
}