栈的概念：
栈：像是一种容器，东西只能从一个地方进，一个地方出，且后进先出！这是其和队列（先进先出，像排队一样，先到先得）的本质区别
⼀种特殊的线性表，其只允许在固定的⼀端进行插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
入栈：插入数据在栈顶。
出栈：栈的删除操作。出数据也在栈顶。
栈的模拟实现Stack.h代码语言：javascript代码运行次数：0运行复制#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#include
#include
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int capacity;//栈的空间大小
int top;//栈顶（插入数据和删除数据的位置）
}ST;
//初始化
void STInit(ST* ps);//传的是地址
//销毁
void STDestory(ST* ps);
//栈顶-=--如数据、出数据
//栈的入数据操作
void SrackPush(ST* ps, STDataType x);//第二个参数是要插入的数据
//栈的出数据操作
void SrackPop(ST* ps);
//取栈顶元素---循环打印栈顶的数据
STDataType StackTop(ST* ps);//返回值是栈顶的元素
//判断栈是否为空
bool StackEmpty(ST* ps);
//获取栈中有效个数
int STSize(ST* ps);Stack.c代码语言：javascript代码运行次数：0运行复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps) {
assert(ps);//看文件是不是传空
ps->arr = NULL;
ps->capacity = ps->top = 0;
//初始的栈顶和栈底都为0（栈为空）
}
//销毁
void STDestory(ST* ps) {
assert(ps);
if (ps->arr != NULL) //栈不为空，说明里面有数据占用空间，直接将其释放掉
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈顶-=--如数据、出数据
//入栈要判断空间是否满了（满了就没法加入数据了）
//出栈，取栈顶元素都要判断栈是否为空（空的栈你能取啥玩意啊）
//栈的入数据操作
void SrackPush(ST* ps, STDataType x) {
assert(ps);
//先判断空间情况，还能否加入数据！！！！！！！！！！
if (ps->top == ps->capacity)//空间满了,需要增容
{
//一般情况是二倍的增加
//初始情况下我们的capacity是定义为0的，所以我们不能直接进行乘二的操作
//我们需要创建一个变量newCapacity
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType*));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
//申请成功，将tmp申请的空间给pa->arr
ps->arr = tmp;
ps->capacity = newCapacity;//容量增加
}
//到此为止，空间够够的了，可以放入数据了
//往栈顶添加数据
ps->arr[ps->top++] = x;
}
//判断栈是否为空
bool StackEmpty(ST* ps) {
assert(ps);
//return ps->arr == NULL;这是判断指针是否为空
return ps->top == 0;
}
//栈的出数据操作
void SrackPop(ST* ps) {
assert(ps);
//要判断是否栈为空！！！不然空栈怎么出数据！
assert(!StackEmpty(ps));
//走到这里就说明栈不为空
--ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了
}
栈的出数据操作
//void SrackPopError(ST* ps) {
// assert(ps);
// return --ps->arr[ps->top];
//}
//取栈顶元素---循环打印栈顶的数据
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));//判断当前栈是不是空的，如果是空的话，我们没有什么能取的
return ps->arr[ps->top-1];//类似数组，最后一个数据是top-1下标
}
//获取栈中有效个数
int STSize(ST* ps) {
assert(ps);
return ps->top;
}栈的相关OJ练习题有效的括号思路：①用指针ps遍历括号字符串
②ps遇到左括号->入栈，ps++继续向下走
ps遇到右括号->与在栈顶的左括号比较是否匹配
③两者匹配->出栈，ps++继续向下走，直至全部匹配，返回true
两者不匹配->非有效括号，返回false，栈销毁
代码及解析代码语言：javascript代码运行次数：0运行复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//定义栈的结构
typedef char STDataType;
typedef struct Stack
{
STDataType* arr;
int capacity;//栈的容量
int top;//栈顶
}ST;
//初始化
void STInit(ST* ps) {
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//销毁
void STDestory(ST* ps) {
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈顶-=--如数据、出数据
//栈的入数据操作
void StackPush(ST* ps, STDataType x) {
assert(ps);
//判断空间是否已满
if (ps->capacity == ps->top) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType*));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
//判断栈是否为空
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
//栈的出数据操作
void StackPop(ST* ps) {
assert(ps);
//判断数据是否为空
assert(!StackEmpty(ps));
--ps->top;
}
//取栈顶元素---循环打印栈顶的数据
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
//获取栈中有效个数
int STSize(ST* ps) {
assert(ps);
return ps->top;
}
bool isValid(char* s) {
//创立新的栈
ST S;
//初始化
STInit(&S);
//取字符指针遍历括号字符串
char* ps = s;
while (*ps != '\0') {
//判断是否是左括号，是->入栈
if (*ps == '(' || *ps == '[' || *ps == '{') {
StackPush(&S,*ps);
}
else//此时的ps是右括号->比较匹配左括号
{
//因为可能拿了左括号没有右括号，得先判断此时栈是否为空
if (StackEmpty(&S))
return false;
//取目前栈顶的左括号保存在ch中，方便比较
char ch = StackTop(&S);
//若匹配
if ((*ps == ')' && ch == '(') || (*ps == ']' && ch == '[') || (*ps == '}' && ch == '{')) {
//将第一个栈顶左括号出栈
StackPop(&S);
}
else//不匹配，是无效括号，直接返回错误
{
STDestory(&S);//返回前记得销毁
return false;
}
}
ps++;
}
bool ret = StackEmpty(&S) == true;//为空->全匹配完了->返回true
//销毁
STDestory(&S);
return ret;
}