栈的结构及概念
栈是一种特殊的线性表，只允许在固定的一端插入或删除数据，进行插入和删除的一端被称为栈顶，另一端称为栈底。栈中的数据遵循后进先出原则
LIFO（LAST IN FIRST OUT)
- 俗称栈的插入过程叫做压栈，入栈，从栈顶入数据
- 出栈就是栈的删除，出数据也在栈顶哦，不然怎么做到后进先出原则。
来看一个动态图理解入栈出栈的过程。
接下来首先要进行分析，由于是后进先出，如果用链表来实现的话，相比数组的尾删和尾插，用链表实现更加麻烦一点，如果用数组来实现，尾删只需要size减一，如果需要入栈的话只需要在末尾的位置添加这个数就可以了。
一步一步来实现他
//静态的
//#define N 10
//struct stack
//{
// int a[N];
// int top;
//};
typedef int TYPE;
typedef struct Stack
{
TYPE* a;
TYPE top;
int capacity;
}ST;
如果还是用静态的数组就太低端了，而且还会遇到容量不够的问题,因为要储存的值的类型有可能会发生变化，所以可以将变量类型定义一下，需要修改时不至于要修改很多地方。
- 定义一个数组，top是栈内储存的数据的量，capacity是数组的容量，如果存储的数据的量等于容量就要用malloc函数进行扩容，大体思路就是如此了。
进入正题
- 仍然利用分文件的形式来实现，以下栈的功能全部放在STACK.c中
初始化函数
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
判断创建的结构体指针变量是否为空assert
将ps指向的数组先置空，然后将容量capacity设置为0，数据量设置为0。
判空函数
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
还是要检查ps是否有问题，返回一个bool变量，判断是false还是true，如果等于0，就返回true，说明栈内为空。
求栈内元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
这个很简单，只需要返回top的值即可。
删除元素
这个很很简单相较于用链表实现
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
即可，当然如果ps指向的top已经是0了就不能再删除了。
添加元素
void STPush(ST* ps, TYPE x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//ps->capacity *= 2;//当capacity等于零时不好用
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
TYPE* tmp = (TYPE*)realloc(ps->a, sizeof(TYPE) * newcapacity);//判断是否扩容成功
if (tmp == NULL)
{
perror("realloc fail");
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
- 传入一个x，首先来判断容量是否为零，如果容量为零的话，那就申请4个空间的内存，然后先存放数据，存放完数据会使数据量top加一，如果top和数据的容量相等时，那就扩充容量为原来的二倍。将x放进该位置，入栈的过程就结束啦。
销毁栈
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
判断必不可少，因为内存是malloc过来的，要用free函数将其释放掉，然后恢复到初始化函数时的状态。将容量还有数量全部还原为零。
获取栈顶元素
TYPE STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
判断栈内到底有没有元素，这是很重要的，不然会越界访问，然后返回入栈的数量减一下标的元素即可，为什么减一呢，第一个元素，下标为零，懂了吧！
别忘记在STACK.h中声明这几个函数
void STInit(ST* ps);
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,TYPE x);
//出栈
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
//获取栈顶元素
TYPE STTop(ST* ps);
来测试一波
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
#include <stdbool.h>
Test1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));
STPop(&st);
}
printf("\n");
STDestroy(&st);
}
运行后如图
如果有想测验一下的，下边就是代码
Test1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));
STPop(&st);
}
printf("\n");
STDestroy(&st);
}
int main()
{
Test1();
return 0;
}
学习完了栈的定义及实现，上一个重头戏
题目：括号的匹配
这道题实现起来很不简单，如果没有学习栈相关的知识，我们在判断时会遇到很多阻力，这道题也可以叫做括号的匹配。例如
- ( { } )这组括号就是可以匹配的。
- ( [ ] ) { } ( )还有像这种。
- ( [ ( ) } ) 然而这组中明显匹配有问题，然而我们怎么来找呢？
如果用字符数组的话，会有很多情况需要判断，而且很容易出错，现在我们来尝试利用栈的特性来解决这一问题。
分析题目要求，仔细分析可以发现，在利用括号开始进行匹配时，如果是右括号（统称）那就入栈，如果是左括号，那就从栈中取出一个元素与其相匹配，如果匹配成功，那就继续向后匹配，如果匹配失败，那就直接返回，并标明匹配错误。
拿出一个测试用例进行解释
接下来解决逻辑问题
首先，因为我们需要用到栈，可以将上边所讲的栈的实现函数全部复制粘贴进去，然后利用栈的特性来实现大体逻辑。
代码如下
bool isValid(char * s){
ST st;
STInit(&st);
char top;
while(*s)
{
if((*s=='[')||(*s=='(')||(*s=='{'))
{
STPush(&st,*s);
}
if(*s==')')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='(')
{
return false;
STDestroy(&st);
}
}
if(*s=='}')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='{')
{
return false;
STDestroy(&st);
}
}
if(*s==']')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='[')
{
return false;
STDestroy(&st);
}
}
s++;
}
bool ret=STEmpty(&st);
STDestroy(&st);//销毁
return ret;
}
创建一个结构体指针变量，这里要注意，上边所写的默认是整型数组，将设置的TYPE改成char类型即可。
在循环体中，我们可以选择使用switch case语句，也可以用if else 语句，代码逻辑十分清晰，在遍历数组的过程中，如果是右括号，则直接入栈，如果是左括号，就出栈顶元素与其相匹配，匹配成功，则走到循环体最后s++的位置，进行下一次判断。
也要注意数组是否为空，可以使用判空函数，如果为空就返回true，如果不为空就返回false，如果是空的话，相当于经历循环体后已经没有左括号了，但是如果不为空的话，那就相当于数组中还剩下一些括号，这些括号是没有被匹配的。
例如
{}()[]{{{
经历过循环后，前边的三组已经匹配完成了，然而后边还有三个右括号入栈，这三个括号没有匹配，所以用判空函数判断一下，如果循环之后栈不为空的话，那就说明匹配不成功，返回false。
需要注意的是取出栈顶元素后将栈顶元素删除。
全部代码如下
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
STDataType top;
int capacity;
}ST;
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
// 11:40
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}
STDataType STTop(ST* ps)
{
assert(ps);
//
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
// bool isValid(char * s)
// {
// }
bool isValid(char * s){
ST st;
STInit(&st);
char top;
while(*s)
{
if((*s=='[')||(*s=='(')||(*s=='{'))
{
STPush(&st,*s);
}
if(*s==')')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='(')
{
return false;
STDestroy(&st);
}
}
if(*s=='}')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='{')
{
return false;
STDestroy(&st);
}
}
if(*s==']')
{
if(STEmpty(&st))
{
return false;
}
top=STTop(&st);
STPop(&st);
if(top!='[')
{
return false;
STDestroy(&st);
}
}
s++;
}
bool ret=STEmpty(&st);
STDestroy(&st);//销毁
return ret;
}
7777777,加油！
