销毁栈函数
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
判断栈是否为空
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//top为0返回真，否则返回假 }
压栈函数
void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) //判断扩容 { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }
出栈函数
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
取栈顶元素
STDataType StackTop(ST* ps)//取出栈顶元素 { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
计算栈中有多少个元素
int StackSize(ST* ps)//计算栈中有多少个元素 { assert(ps); return ps->top; }
入栈出栈操作
int main() { ST st; StackInit(&st); StackPush(&st, 1); //入栈出栈操作 StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (!StackEmpty(&st)) { printf("%d\t", StackTop(&st)); StackPop(&st); } StackDestroy(&st); return 0; }
入栈序列为1、2、3、4，那么连续的出栈序列就为4、3、2、1
故运行结果为：
习题（有效的括号）
题目描述
给定一个只包括 '(' ，')' ，'{' ，'}' ，'[' ，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。左括号必须用相同类型的右括号闭合。
题目示例
示例 1： 输入：s = "()" 输出：
示例 2： 输入：s = "()[]{}" 输出：true
示例 3： 输入：s = "(]" 输出：false true
题目思路
用一个栈来解题，如果是左括号则入栈；如果是右括号，则进行出栈操作，与该右括号匹配。
（但C语言的库中没有栈，需要我们自己定义一个栈）
题目代码
//上面加一个栈 bool isValid(char* s) { ST st; StackInit(&st); while (*s) { if (*s == '(' || *s == '[' || *s == '{') //遇到左括号，进行入栈操作 { StackPush(&st, *s); } else //遇到右括号 { if (StackEmpty(&st)) //遇到右括号时栈中没有数据的情况，即匹配失败 { StackDestroy(&st); return false; } STDataType top = StackTop(&st); StackPop(&st); if ((*s == '}' && top != '{') || (*s == ']' && top != '[') || (*s == ')' && top != '(')) //把左括号出栈，与右括号进行匹配 { StackDestroy(&st); return false; } else { s++; } } } //while循环结束之后，判断栈中是否为空 //如果栈不为空，则说明栈中的括号没有被成功匹配 //也返回false bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
end
