🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
前言：本篇文章，我们继续来看顺序表和链表相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的栈和队列部分内容啦。
再次提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。
因此，不同的场景我们选择不同的数据结构。
目录正文
一、栈
（一）栈的概念与结构
1、栈的概念
2、栈的结构
（二）栈结构的实现（用数组实现）
1、初始化
2、销毁
3、入栈——栈顶
4、判断栈是否为空
5、出栈——栈顶
6、取栈顶元素
7、栈结构实现（数组）的完整代码
（1）List.h：
（2）List.c：
（3）test.c：
（三）栈的应用
结尾
正文一、栈（一）栈的概念与结构1、栈的概念 概念：栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
栈有点类似于水杯，杯口进水喝水，杯底即栈底。
我们在栈顶插入删除数据，数据的插入删除都只在一端——栈顶——完成。
即：
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。
注：出数据也在栈顶。
LIFO：Last In First Out，“后进先出”或者说“先进后出”。
理解：当我们往收纳箱里面放东西，先放进去的东西会在箱底，会放进去的东西会在箱顶，我们之后取出来的时候是先取出上面的东西，最后再取出最先放进去的东西。
2、栈的结构 逻辑结构：是线性的；
物理结构：不一定，取决于你是用数组实现的还是用链表实现的，如果是用数组实现的，数组是连续存放，元素地址都是连续的，此时是线性结构，用链表实现则不是线性结构。
对于栈我们是用数组实现还是用链表来实现？
（二）栈结构的实现（用数组实现）1、初始化（1）List.h：
代码语言：javascript复制#pragma once
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
STDataType size;//定义栈中有效的数据个数
STDataType capacity;//栈的空间大小
}ST;
//初始化
void STInit(ST* ps);（2）List.c：
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}（3）test.c：
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
}
int main()
{
test01();
return 0;
}
现在初始化完了，我们就有了一个空栈，有了空栈我们就可以去实现栈相关的一系列操作。
2、销毁我们先来实现一下销毁，和初始化类似。
List.c：
代码语言：javascript复制//销毁
void STDestory(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}test.c：
代码语言：javascript复制#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
STDestory(&st);
}
int main()
{
test01();
return 0;
}3、入栈——栈顶 栈顶插入数据，栈顶对于数组来说就是数组的尾部，栈顶插入数据即在数组尾部插入数据。
List.c：
代码语言：javascript复制//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->top == ps->capacity)
{
//增容
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
int* 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;
}test.c：
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STDestory(&st);
}
int main()
{
test01();
return 0;
} 如果再加一个数据，我们来观察一下【监视】中capacity的值有什么变化——
代码语言：javascript复制 STPush(&st, 5); 【监视】栏capacity的值发生了变化——
4、判断栈是否为空List.c：
代码语言：javascript复制//栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}5、出栈——栈顶List.c：
代码语言：javascript复制//出栈——栈顶
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}test.c：
代码语言：javascript复制#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);
STPop(&st);
STDestory(&st);
}
int main()
{
test01();
return 0;
} 运行一下——
6、取栈顶元素 我们要取top-1的位置，不能取top，top指向的是一个无效的数据。
List.c：
代码语言：javascript复制//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}test.c：
代码语言：javascript复制#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
printf("size:%d\n", STSize(&st));
//STPop(&st);
while (!STEmpty(&st))
{
//取栈顶
STDataType top = STTop(&st);
printf("%d ", top);
//出栈
STPop(&st);
}
printf("\n");
STDestory(&st);
}
int main()
{
test01();
return 0;
} 运行一下——
7、栈结构实现（数组）的完整代码 到这里，栈相关的结构我们都实现完了，是不是比前面的顺序表和链表都要简单？
（1）List.h： 代码语言：javascript复制#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;//定义栈中有效的数据个数
int capacity;//栈的空间大小
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestory(ST* ps);
//入栈——栈顶
void STPush(ST* ps, STDataType x);
//出栈——栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);（2）List.c：代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void STDestory(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->top == ps->capacity)
{
//增容
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
int* 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 STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//出栈——栈顶
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}（3）test.c：代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void test01()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
printf("size:%d\n", STSize(&st));
//STPop(&st);
while (!STEmpty(&st))
{
//取栈顶
STDataType top = STTop(&st);
printf("%d ", top);
//出栈
STPop(&st);
}
printf("\n");
STDestory(&st);
}
int main()
{
test01();
return 0;
} 注意：ps不能传空！
（三）栈的应用链接：20.有效的括号
博主的题解： 借助数据结构——栈——解决经典例题【有效的括号】
题目描述：
这道题博主会放到博主的专栏【LeetCode代码强化刷题】 里面，本文不会详解。
题目链接和力扣题解博主放在大标题下面了，大家可以去浏览一下，做一做。
代码演示：
代码语言：javascript复制//定义栈的结构
typedef char STDataType;
typedef struct Stack
{
STDataType* arr;
int top;//定义栈中有效的数据个数
int capacity;//栈的空间大小
}ST;
//初始化
void STInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void STDestory(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否足够
if (ps->top == ps->capacity)
{
//增容
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 STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//出栈——栈顶
void STPop(ST* ps)
{
assert(!STEmpty(ps));
ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(!STEmpty(ps));
return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//-----------------------以上是栈结构定义和常见方法-------------------------
bool isValid(char* s)
{
//借助数据结构——栈
ST st;
STInit(&st);
char* pi = s;
while(*pi != '\0')
{
//左括号入栈
if(*pi == '(' || *pi == '[' || *pi == '{')
{
STPush(&st,*pi);
}
else
{
//右括号——取栈顶，比较，匹配则出栈，不匹配直接返回false
//栈不为空才能取栈项
if(STEmpty(&st))
{
STDestory(&st);
return false;
}
char top = STTop(&st);
if((top == '(' && *pi != ')')
||(top == '[' && *pi != ']')
||(top == '{' && *pi != '}'))
{
STDestory(&st);
return false;
}
//本次是匹配的——出栈
STPop(&st);
}
pi++;
}
//判断栈是否为空，为空有效，非空无效
// if(STEmpty(&st))
// {
// STDestory(&st);
// return true;
// }
// STDestory(&st);
// return false;
//写成三目表达式
bool ret = STEmpty(&st) ? true : false;
STDestory(&st);
return ret;
}复杂度：时间复杂度：O(N) ，空间复杂度：O(1)。
结尾往期回顾：
【数据结构与算法】数据结构初阶：详解顺序表和链表（五）——双向链表
【数据结构与算法】数据结构初阶：详解顺序表和链表（四）——单链表（下）
【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）
本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。
大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：
【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）
结语：本篇文章到这里就结束了，对数据结构的单链表知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！