文章目录一、栈的基本概念1.1 概念1.2入栈出栈顺序二、栈的顺序存储2.1静态顺序栈和动态顺序栈结构2.2动态顺序栈实现一、栈的基本概念1.1 概念线性表(linear list)是相同类型的n(n0)个数据元素的有限序列若用L命名为线性表则一般表示为 L(a1,a2,…,ai,ai1,…,an)栈(stack)是限定仅在一端进行插入或删除操作的线性表。因此对栈来说进行插入删除数据的这一端称为栈顶(top)另一端称为栈底(bottom)不含元素的空表称为空栈。栈中的数据元素遵循后进先出(LIFO Last In First Out)的特性。栈插入和删除数据都在栈顶端插入数据一般叫做入栈/进栈删除数据一般叫做出栈。1.2入栈出栈顺序假设入栈顺序为a1,a2,a3,a4,a5那么出栈顺序是什么呢大家最容易想到的是所有数据都入栈以后再出栈就是a5,a4,a3,a2,a1实际上有多种出栈顺序比如每个数据入栈以后马上出栈所以另一种出栈顺序也可以是a1,a2,a3,a4,a5还可以是a1,a2,a3入栈出a3,a2再入栈a4,a5再出栈a5,a4,a1也就是说出栈顺序为a3,a2,a5,a4,a1通过分析我们可以看到因为出栈时机的不同可以有很多种出栈顺序。二、栈的顺序存储栈是只允许在一端进行元素插入和删除操作的特殊线性表。而线性表有顺序和链式两种存储结构故栈也有顺序和链式两种存储结构。2.1静态顺序栈和动态顺序栈结构跟顺序表类似栈的顺序存储实现可以使用静态数组我们称为静态顺序栈也可以使用堆上动态申请数组实现我们称为动态顺序栈。静态顺序栈的缺陷跟静态顺序表类似只适用于确定知道最多需要多少空间的场景那么我们后续重点讲解动态数组实现的版本。静态栈结构定义#defineMAX_SIZE10typedefintSTDataType;typedefstruct{STDataType arr[MAX_SIZE];inttop;// 标记栈顶}Stack;动态栈结构定义typedefintSTDataType;typedefstruct{STDataType*arr;// 指向栈数组空间的指针inttop;// 栈顶位置intcapacity;// 容量}Stack;2.2动态顺序栈实现有了前面学习顺序表的基础这里我们实现动态顺序栈简直小菜一碟。相比而言这里的入栈和出栈操作还要更简单一些。需要注意-1还是top0的是栈结构中初始化时toptop-1 代表top指向栈顶元素那么入栈时要先top再把入栈数据放到top位置。top0 代表top指向栈顶元素的下一个位置那么入栈时要先把入栈数据放到top位置再top。其他接口函数处理细节也要对应调整。这两种方式没有优劣之分大家任选一种即可为何初始化时top0不能代表top指向栈顶元素呢那我们要思考栈为空和栈只有一个数据时top都是0如何区分呢栈的实现voidStackInit(Stack*s){assert(s);s-arr(STDataType*)malloc(4*sizeof(STDataType));if(NULLs-arr){printf(StackInit: 申请空间失败!!!\n);exit(-1);}// 初始化时, top 0, 表示top指向的是栈顶元素的下一个位置// 初始化时, top -1, 表示top指向的是栈顶元素// 两种方式都可以, 选择哪一种后面的逻辑都对应调整即可s-top 0;s-capacity4;}voidStackDestroy(Stack*s){assert(s);if(s-arr){free(s-arr);s-arrNULL;s-top0;s-capacity0;}}// x元素入栈(进栈)void StackPush(Stack* s, STDataType x) {assert(s);if(s-tops-capacity){STDataType*tmp(STDataType*)realloc(s-arr,sizeof(STDataType)*s-capacity*2);if(tmpNULL){printf(StackPush: 扩容空间失败!!!\n);exit(-1);}s-arrtmp;s-capacity*2;}//扩容s-arr[s-top] x;s-top;}// 将栈顶元素出栈, 并用返回栈顶元素STDataType StackPop(Stack* s) {assert(s);assert(!StackEmpty(s));STDataType xs-arr[s-top-1];s-top--;returnx;}// 获取栈顶元素并返回STDataType StackTop(Stack* s) {assert(s);assert(!StackEmpty(s));returns-arr[s-top-1];}// 获取栈中有效元素个数int StackSize(Stack* s) {assert(s);returns-top;}// 检测栈是否为空, 如果是空返回真, 否则返回假bool StackEmpty(Stack* s) {assert(s);returns-top0;}