栈的概念及结构
在学习栈前，我们先看一下栈的正式解释：
栈底就是我们栈的开头位置，我们放数据进去，就是以一种往上叠的感觉， 现在栈底已经有a1、a2两个数据，我们现在放a3进去，它就应该在a2的上面。
现在a3已经进栈，我们现在要拿出数据，就从栈顶开始拿，也就是说a3回先被我们拿出来
然后出栈的顺序就是：a3、a2、a1
这就是栈的后进先出，但是我们没必要全部放进去了再一起拿出来，我们也可以放一个数据拿一个数据出来，比方说；
现在有a3、a4要进栈，我们让a3先进栈：
但是我们又要用到a3这个数据，我们就直接把a3拿出去，然后把a4压进去：
那我们出数据的时候，就变成了：
a3、a4、a2、a1
------------
我们来看两道题加深理解：
栈的实现
我们之前学过数组、链表，这两种都可以用在栈上，栈只需要在栈顶进行操作，我们来看看两种分别怎么实现：
数组：可以把数组首元素地址看作栈底，而数组之后的位置看作栈顶，这样数组的栈压栈即是在尾补插入数据，也就是top的位置
链表：
我们如果把数组第一个节点认为是栈底，那压栈就是在它后面尾插，尾插不难，但是我们要如何出栈呢？
如果是双向的链表就可以解决这个问题，但未免有些麻烦
如果是单链表，我们首插就简单一点。
这里我们就来实现一下数组的栈：
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);在实现之前，我们要做几件事：
头文件，就不多说了
类型最好定义一下，用typedef，这样我们之后修改存储类型直接在这里修改就好
定义一个结构体
声明我们要实现的函数
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int STDataType;typedef struct Stack
{STDataType* arr;int top;int capacity;
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);然后我们一个一个来实现：
初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}很简单，我们让指针指向NULL，然后数据为0即可，这里要注意的是：
top位置，如果top的位置是0开始的话，也就是说以下标位置为栈顶
当放 1 2 3 4 5数据的时候，top的下标就是5，也就是下一个数据的位置
当top为-1开始的时候，放1 2 3 4 5的时候，top的下标为4，也就是当前数据的位置
入栈
入栈也就是我们数组top的位置放上要存储的数据，看代码实现：
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;ps->arr = (Stack*)realloc(ps->arr, sizeof(Stack)* newcapacity);if (ps->arr == NULL){printf("realloc fail\n");exit(-1);}ps->capacity = newcapacity;}ps->arr[ps->top++] = data;
}一进函数，先判断ps是否空指针，其次判断是否还有空间，如果没有空间我们就开辟一个新空间，开辟失败就退出并打印错误信息，如果开辟成功并有空间，我们就放数据进去。
出栈
就跟顺序表一样，如果出栈，我们就直接将top--即可，不需要销毁什么空间
void StackPop(Stack* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps->arr[ps->top-1];
}
我们直接返回即可，不过要注意这里top，top是0和top是-1的返回值课不一样，别搞错了。
获取栈的有效数据个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}直接返回top即可。
看看栈是否为空
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}直接在返回里面判断即可
销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}跟初始化一样，主要是注销里面的指针，然后将其他置零。
-----------
栈的练习
我们知道并了解了栈，做一道题看看：
20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)
这里就可以用到我们刚刚学会的栈。
先说思路：
我们将得到的字符进行判断，如果是左半边，就压栈，如果就右半边就取出来然后配对，配对错就返回false。
看代码实现：
我们先把上面的函数都拿过来用，先复制过来，下面的是主程序
bool isValid(char * s)
{Stack arr;StackInit(&arr);while(*s){//压栈if(*s == '('||*s == '['||*s == '{'){StackPush(&arr,*s);++s;}//*s是右半边，我们开始配对else{//如果取不出来直接就返回falseif(StackEmpty(&arr)){return false;}//取出来开始判断char data = StackTop(&arr);//取出来顶上一个我们就删一个，方便下一次配对StackPop(&arr);if((*s =='}' && data != '{')|| (*s == ')' && data != '(')|| (*s == ']' && data != '[')){StackDestroy(&arr);return false;}//配对成功继续走else{++s;}}}//看栈里面还有没有括号int ret = StackEmpty(&arr);StackDestroy(&arr);return ret;
}感谢您的观看，我们下次再见
