扬帆启航于数据结构算法之雅舟旅程，悠然漫步于C++秘境——探索线性表之栈的绮丽定义与精妙实现
人无完人，持之以恒，方能见真我！！！
共同进步！！
文章目录
- 一、栈的概念与结构
- 2.栈的底层结构选型
- 二、栈的实现
- 1.栈结构的定义
- 2. 栈的初始化和销毁
- 栈的初始化
- 栈的销毁
- 3.栈的扩容与入栈
- 栈的扩容
- 入栈
- 4.判断栈是否为空和出栈
- 判断栈是否为空
- 出栈
- 5.取栈顶元素和获取栈中有效元素个数
- 取栈顶元素
- 获取栈中有效元素个数
- 三、栈实现的源码
- 四、栈的简单应用之有效的括号
- 思路1
- 思路2
一、栈的概念与结构
栈是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出（先进后出）的原则
其中栈的插入操作就叫压栈/进栈/入栈，插入操作只能对栈顶进行，而删除栈顶元素的操作就叫出栈，出栈也只在栈顶操作，我们画个图理解一下：
2.栈的底层结构选型
栈其实是通过我们之前写过的两个数据结构——数组(顺序表)/链表实现的，它的底层既可以是数组也可以是链表，我们一般情况下就选择数组来实现栈，因为栈只在数据结构的尾部进行操作，数组在尾上插⼊数据的代价⽐较小
删除数据也比较简单，而链表除非使用双链表，否则使用单链表操作尾部数据，必须遍历整个链表，付出的代价更大，所以我们一般选择使用数组做我们栈的底层
为什么不使用双链表呢？我们之前也讲过单链表和双链表的区别，单链表结构更简单，适合做其它数据结构的底层，双链表结构复杂，更适合直接存放数据，所以我们在考虑数据结构的底层时，一般考虑的是单链表还有数组，在实现栈的时候我们就使用数组作为底层的结构
二、栈的实现
在将栈的实现之前，强烈建议先去学习顺序表，栈和顺序表很相似，如果顺序表能够学懂，栈就是小菜一碟
栈和顺序表最大的区别是，栈中有效元素个数叫top，栈顶元素就是栈中最后一个数据，也就是top-1位置上的数据，而顺序表中有效元素个数叫size，这是最容易搞混的
1.栈结构的定义
栈结构的定义与顺序表类似，还是需要三个成员，一个需要动态开辟空间的数组，记录数组有效元素个数和总容量的整型
但是我们要注意，在栈中，有效元素个数-1就是我们的栈顶元素的位置，所以在栈中有效元素个数换了个名字，不再叫size而叫top了，接下来我们来看看它的结构：
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;//需要动态开辟的数组
int top;//有效元素个数
int capacity;//数组总容量
}ST;
这里就可以看出，栈和顺序表极其的相似，其实栈就是一种特殊的顺序表，把今天的栈学完，我们就可发现了
2. 栈的初始化和销毁
栈的初始化
栈的初始化和顺序表类似，就是将栈中的数组置为空，将数组总容量和有效数据个数置为0，由于我们需要修改栈，所以我们要传地址，如下：
//栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;//置空
ps->capacity = ps->top = 0;//归零
}
栈的销毁
栈的销毁就是手动释放我们申请的资源，就是我们动态开辟的空间，如果不释放掉就会造成内存泄漏，释放完后将数组置空，将数组总容量和有效数据个数置为0，如下：
//栈的销毁
void STDestroy(ST* ps)
{
assert(ps);
if (ps->arr)//如果数组不为空，就是释放掉
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
3.栈的扩容与入栈
栈的扩容
由于栈的底层还是数组，所以我们在进行入栈，也就是插入操作的时候，避免不了要对栈的容量进行判断，如果容量不够要进行扩容，也就是对数组进行扩容，扩容方法也跟顺序表差不多，如下：
malloc函数用于分配指定大小的内存块，并返回指向该内存块的指针。
realloc函数用于重新分配已分配内存的大小。它接受一个已分配内存的指针和新的大小作为参数，并返回重新分配后的内存块的指针。 如果新的大小大于原内存块的大小，则额外的内存空间将被分配，并且原内存块中的数据将被复制到新的内存块中；如果新的大小小于原内存块的大小，则原内存块中的数据可能会被截断或丢失。
//栈的扩容
void STCheckCapacity(ST* ps)
{
assert(ps);
if (ps->top == ps->capacity)//相等就扩容
{
//通过三目运算判断增容多少空间
ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * ps->capacity);
if (tmp == NULL)
{
perror("malloc fail\n");
return;
}
ps->arr = tmp;
}
}
入栈
我们在上面讲到过，对栈数据的操作都是在栈顶进行操作，那么我们就要界定一下在数组中数组的头作为栈顶好还是尾作为栈顶好，很明显数组的尾作为栈顶更好
因为对数组的尾进行插入删除操作相当于顺序表的尾插和尾删，时间复杂度为O(1)，比较简单，而对数组的头进行插入删除操作相当于顺序表的头插和头删，时间复杂度为O(N)，更加复杂
那么有了这个认知我们实现入栈操作就很简单了，就相当于对顺序表进行尾插，就是对栈中top位置进行插入操作，因为栈顶元素就是top-1，top是有效元素个数，它指向的位置就刚好是我们要插入的位置，具体实现如下：
//入栈
void STPush(ST* ps, STDataType x)
{
assert(ps);
STCheckCapacity(ps);
ps->arr[ps->top++] = x;//top下标就是可以尾插的位置
}
4.判断栈是否为空和出栈
判断栈是否为空
判断栈是否为空只需要判断一下有效元素个数top是否为0，这里我们可以巧妙地直接用一条语句写出来，如下：
//栈的判空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//判断有效元素个数top
}
出栈
出栈其实就是删除栈顶元素，也就是删除数组的最后一个元素，对应顺序表中的尾删，顺序表中就是让size直接- -，在栈中就是让top直接- -，我们在顺序表中解释了多次原因，这里就不再多说，代码如下：
//出栈
void STPop(ST* ps)
{
assert(!STEmpty(ps));//不为空就可以出栈
ps->top--;
}
5.取栈顶元素和获取栈中有效元素个数
取栈顶元素
取栈顶元素就是直接返回数组中最后一个有效的数据，注意不是直接返回top位置的数据，top是有效元素个数，top-1才是数组中最后一个有效的数据的下标，知道了这一点我们就可以直接写代码了，如下：
//取栈顶元素
int STTop(ST* ps)
{
assert(ps);
return ps->arr[ps->top - 1];
}
获取栈中有效元素个数
在栈中，top就是有效元素个数，直接返回top即可，如下：
//栈的有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;//直接返回top即可
}
三、栈实现的源码
//栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;//置空
ps->capacity = ps->top = 0;//归零
}
//栈的销毁
void STDestroy(ST* ps)
{
assert(ps);
if (ps->arr)//如果数组不为空，就是释放掉
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//栈的扩容
void STCheckCapacity(ST* ps)
{
assert(ps);
if (ps->top == ps->capacity)//相等就扩容
{
//通过三目运算判断增容多少空间
ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STDataType) * ps->capacity);
if (tmp == NULL)
{
perror("realloc fail\n");
return;
}
ps->arr = tmp;
}
}
//入栈
void STPush(ST* ps, STDataType x)
{
assert(ps);
STCheckCapacity(ps);
ps->arr[ps->top++] = x;//top下标就是可以尾插的位置
}
//栈的判空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//判断有效元素个数top
}
//出栈
void STPop(ST* ps)
{
assert(!STEmpty(ps));//不为空就可以出栈
ps->top--;
}
//取栈顶元素
int STTop(ST* ps)
{
assert(ps);
return ps->arr[ps->top - 1];
}
//栈的有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;//直接返回top即可
}
int main()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
while (!STEmpty(&st))
{
int top = STTop(&st);
printf("%d ", top);
STPop(&st);
}
STDestroy(&st);
return 0;
}
四、栈的简单应用之有效的括号
题目链接：有效的括号
先来看看题目描述:
这道题目要求我们根据给出的字符串来判断它是否是有效的括号，这个字符串中只包含括号，如果括号可以一一匹配那么就说明它是有效的括号，这道题就可以用上我们刚刚写过的栈，我们一起来看看思路
思路1
我们要使用栈，就要明白栈的规则先进后出（后进先出），它跟我们的括号的匹配类似，前面的括号和后面的括号匹配，类似于先进后出
在上图演示的思路中，我们可以看出来括号的匹配和栈先进后出（后进先出）的特点相似，所以我们就可以想办法利用栈来做这个题，具体思路如下：
1.我们先来看括号匹配的情况：首先创建一个栈，如果碰到左括号就入栈，碰到右括号就检查栈顶元素是否和对应的右括号匹配，如果匹配就出栈，如果最后遍历了整个字符串后，发现栈为空，那么这个字符串就是一个括号匹配字符串，如图：
2.接着我们来看括号匹配失败的情况：
（1）首先就是如果我们遍历到了右括号，但是栈是空的，说明前面没有对应的左括号了，那么字符串肯定就不满足括号匹配的条件，直接返回false
（2）然后就是，我们遍历到了右括号，但是栈顶元素和这个右括号不匹配，也能说明出现了不匹配的括号，不满足条件，直接返回false
（3）最后就是，我们遍历完了整个字符串，出了循环结果发现栈里面还不为空，这也说明出现了不匹配的括号，也要返回false
（4）**注意：**题目没有提供栈，我们需要复制我们写的栈过去，以后学了C++就可以直接使用栈了，不用自己写，现在我们暂时先使用我们写的栈，还有就是我们在返回结果前，要把栈销毁掉，以免造成内存泄漏
那么括号匹配成功的情况和失败的情况我们都分析完了，条理清晰，接着我们就可以照着思路直接写代码了，题解如下（自行将栈的实现拷贝到题目，这里为了简洁就直接只给出了函数的实现）：
bool isValid(char* s)
{
ST st;
STInit(&st);
while(*s != '\0')//遍历字符串，走到'\0'就终止循环
{
if(*s == '(' || *s == '[' || *s == '{')
{
//碰到左括号入栈
STPush(&st,*s);
}
else
{
//走到这里说明遇到了右括号
//如果栈为空，说明没有右括号匹配，返回false
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
//如果栈不为空，就进行匹配
//取出栈顶元素进行匹配,不匹配返回false
char top = STTop(&st);
if((top == '(' && *s != ')')
|| (top == '[' && *s != ']')
|| top == '{' && *s != '}')
{
STDestroy(&st);
return false;
}
//走到这里说明栈顶元素和右括号匹配
//将栈顶元素出栈，继续比较下一个
STPop(&st);
}
s++;
}
//查看栈是否为空，为空说明是匹配的，否则不是匹配的
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
思路2
刚刚我们的思路1是查看取出的栈顶元素和右括号是否匹配，因此我们需要判断条件，但是那个判断条件很复杂，有没有办法简化一下呢？我们想到在Ascll码表中，数字和字母挨得很近，左右括号应该也不会很远
所以我们思路2就是利用字符底层存储的是它的Ascll码值来解决，我们先来看看Ascll码表中左右括号相隔的距离：
我已经在图中标注了几个括号的位置，我们不用去记每个括号的Ascll码值，只需要记得它们之间的相对位置，小括号之间是紧紧挨着的，中大括号中间隔了一个元素，所以我们的条件可以用或连接起来
我们再大致总结一下思路，首先判断是否遍历到了左括号，遍历到了就直接入栈，如果碰到右括号首先判断栈是否为空，为空直接返回假
如果不为空取出栈顶的括号，查看当前左括号+1或者+2后是否是遍历到的右括号，如果是的话说明括号匹配成功了，直接让栈顶的括号出栈，否则就没有匹配上，然后直接返回假，最后出循环后再判断一下栈是否为空就大功告成了，题解如下：
bool isValid(char* s)
{
ST st;
STInit(&st);
while(*s != '\0')//遍历字符串，走到'\0'就终止循环
{
if(*s == '(' || *s == '[' || *s == '{')
{
//碰到左括号入栈
STPush(&st,*s);
}
else
{
//走到这里说明遇到了右括号
//如果栈为空，说明没有右括号匹配，返回false
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
char top = STTop(&st);
if(top + 1 == *s || top + 2 == *s)
{
STPop(&st);
}
else
{
STDestroy(&st);
return false;
}
}
s++;
}
//查看栈是否为空，为空说明是匹配的，否则不是匹配的
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
这道题说了只会输入括号，所以我们才能这样做，如果题目存在其它符号就不一定能够使用这个方法，谨慎使用哦~
那么今天的栈就到这里了，bye~~