1.栈的概念
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
2.栈的结构
逻辑结构：是线性的 物理结构：是线性的
栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插 ⼊数据的代价⽐较⼩。
typedef struct Stack
{
STDataType* arr;
int top;\\\\等于size，表示栈中有效数据的数量
int capacity;\\\\表示栈可存储的数据数量
}ST;
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
4.代码实现
1.初始化栈
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top=ps->capacity = 0;
}
2.销毁栈
void STDestroy(ST* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->top = ps->capacity=0;
}
3.入栈
void STPush(ST* ps, STDataType x)
{
if (ps->top == ps->capacity)
{
int newcapcaity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newcapcaity*sizeof(STDataType));
if (tmp == ((void*)0))
{
perror("realloc fail");
return 0;
}
ps->arr = tmp;
ps->capacity = newcapcaity;
}
ps->arr[ps->top++] = x;
}
4.判空
bool STEmpty(ST*ps)
{
if (ps->top == 0)
return true;
else
return false;
}
5.出栈
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top–;
}
6.取栈顶数据
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return(ps->arr[ps->top-1]);
}
7.获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
5.题目运用
利用定义好的栈函数。
此题充分利用到栈—先进后出的特点，将复杂对比情况简化，我们在完成题目时，尤其要注意栈的销毁问题。
bool isValid(char* s) {
ST st;
STInit(&st);
char* ps = s;
while (*ps != '\\0') {
if (*ps == '(' || *ps == '[' || *ps == '{') {
STPush(&st, *ps);
}
else {
if (STEmpty(&st)) {
STDestroy(&st);
return false;
}
char i = STTop(&st);
if ((i == '(' && *ps != ')') ||(i == '[' && *ps != ']') ||(i == '{' && *ps != '}'))
{
STDestroy(&st);
return false;
}
STPop(&st);
}
ps++;
}
bool result=STEmpty(&st)?true:false;
STDestroy(&st);
return result;
}
