栈（数据结构）

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️

一，栈

• 栈：一种特殊的线性表（操作受限的线性表），其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

• 总结：栈就是一个线性表，元素的逻辑顺序是连续的，每一个元素都只有唯一的前置节点和后置节点，但是物理上不一定连续，所以依然可以用数组或者链式这两种存储数据的方式来实现栈，但是栈是操作受限的线性表，没有正常线性表所谓的头插删，尾插删，pos节点的插删，栈只能对一端进行操作，操作的这一端被称为栈顶，在栈插入操作被称为入栈，压栈，栈删除操作称为出栈

• 总结：线性表只规定了逻辑上节点前后只有唯一节点，所以数据存储空间方式有产生了顺序存储（顺序表）和链式存储（链表），而普通的线性表是可以在任意位置操作数据的也就是普通线性表，但是有些线性表却只能在一端操作，或者只能在两端，这种就是受限线性表，也就是栈和队列,受限的线性表依然是线性表，只规定了逻辑上节点前后只能有唯一节点，但是物理上依然有数组存储数据（连续）和链式存储数据（不连续），两种存储数据的模式

二，栈的实现方式

• 栈是线性表，只要逻辑上线性即可，物理上不管，所以实现栈可以用数组和链式的两种物理上存储数据的模式，数组和链式来实现顺序栈和链式栈

1 顺序栈

• 定义：顺序栈采用一段连续的内存空间（数组）存储栈中元素，同时搭配一个栈顶指针（整型变量）记录当前栈顶元素的位置，是最经典、最常用的栈实现形式。

• 约定一：top指向栈顶元素的下标，所以空栈状态的时候top为-1，代表非数组起始下标，所以为空栈，所以top对应的位置就是元素的位置，所以入栈的时候要先top++,让top走到下一个空位置才能存放数据。所以top代表的下标+1就是元素的存储个数

• 约定二：top指向栈顶元素的下一个空位的下标，所以当top为0的时候，存数据的位置在下标为-1的位置，-1下标为无效的，所以top为0代表空栈，存两个元素，个数是2，如果下标对应元素位置，那下标为1，但是约定二中的top指的是元素下一个位置，所以下标为2，所以top就和顺序表中的size很像，top就等于栈中元素的总数

• 静态顺序栈存储空间的数组容量是固定好的，不可改变，元素存储个数锁死，但是动态顺序栈的数组本质上就是realloc开辟的连续的内存空间，当空间不够可以随意扩容

2 链式栈

• 定义：链式栈是基于单链表实现的栈结构，行业标准做法是将栈顶设置在链表头部，所有插入、删除操作都在链表头部完成，无需遍历链表。

• 总结：受限线性表：栈，在物理上的存储数据的方式如果采用链式结构，就叫做链式栈，而链式结构的特点就是空间不连续，以节点的方式链接存储数据，但是链式结构分多种，有带头不带头，循环不循环，双向不双向的链式结构，而最常见的链式栈，就是基于单链表这种链式结构实现的链式栈

• 链式栈几乎统一采用单链表实现，核心原因是栈的操作特性与单链表的能力完全匹配，其他链表的额外功能对栈而言全是冗余，只会增加空间开销和实现复杂度，没有任何收益。

• 总结：单链表可以进行头删头插和尾删尾插，但是链式栈规定了只能在一端，也就是栈顶进行插入删除操作，那我们要选择单链表的头插头删还是尾删尾插呢，我们选择的是头删和头插，因为如果选择尾删和尾插，由于单链表是单向的每一次进行尾插和尾删的操作都需要从头节点遍历到尾节点，这样时间复杂度就变成了O(n),但是如果把栈顶定义在单链表头部，那只需要进行头删头插，不需要遍历链表，因为链表的起点就是头部，时间复杂度就变成了O(1)。

• 单链表的能力刚好覆盖栈的全部操作需求，时间复杂度已经达到理论最优，没有进一步优化的空间也就是说功能更多的链式结构比如循环双向等链表，不能对单链式结构的栈进一步优化，虽然多了功能，但是对于实现栈而言，单链表就能满足栈的所有需求了，以及复杂度最优，其他更复杂的链式结构并不能优化栈的需求，所以最优的选择就是基于单链表实现栈

三， 顺序栈和链式栈的选择

• 不存在绝对的 “谁更优”，二者是不同设计取舍下的产物；但在绝大多数工程实践和刷题场景中，顺序栈是更主流、综合表现更好的选择。二者的核心差异，本质是「连续数组 vs 离散链表」的底层差异在栈结构上的体现。

四， 顺序栈的实现

1 Test.c

#define_CRT_SECURE_NO_WARNINGS1#include"Stack.h"intmain(){ST s;STInit(&s);STPush(&s,1);STPush(&s,2);STPush(&s,3);STPush(&s,4);STPush(&s,5);ST*ps=&s;while(!STEmpty(&s)){inttop=STTop(&s);printf("%d ",top);STPop(&s);}STDesTroy(&s);return0;}

2 Stack.h

#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>typedefintSTDataType;typedefstructstack{STDataType*a;inttop;//栈顶下标，同时等于栈有效元素个数intcapacity;//栈的空间大小}ST;//栈初始化voidSTInit(ST*ps);//栈销毁voidSTDesTroy(ST*ps);//入栈voidSTPush(ST*ps,STDataType x);//出栈voidSTPop(ST*ps);//取栈顶元素STDataTypeSTTop(ST*ps);//栈元素个数intSTSize(ST*ps);//判断空栈boolSTEmpty(ST*ps);

3 Stack.c

#define_CRT_SECURE_NO_WARNINGS1#include"Stack.h"//栈初始化voidSTInit(ST*ps){assert(ps);ps->a=NULL;ps->top=0;ps->capacity=0;}//栈销毁voidSTDesTroy(ST*ps){assert(ps);free(ps->a);ps->a=NULL;ps->top=ps->capacity=0;}//入栈voidSTPush(ST*ps,STDataType x){assert(ps);if(ps->top==ps->capacity){intnewcapacity=ps->capacity==0?4:2*ps->capacity;STDataType*tmp=(STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc:");return0;}ps->a=tmp;ps->capacity=newcapacity;}ps->a[ps->top++]=x;}//出栈voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));ps->top--;}//取栈顶STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps->a[ps->top-1];}//栈元素个数intSTSize(ST*ps){assert(ps);returnps->top;}//判断空栈boolSTEmpty(ST*ps){assert(ps);returnps->top==0;}

五， 顺序栈的解析

1 Test.c解析

#define_CRT_SECURE_NO_WARNINGS1#include"Stack.h"intmain(){ST s;STInit(&s);STPush(&s,1);STPush(&s,2);STPush(&s,3);STPush(&s,4);STPush(&s,5);ST*ps=&s;while(!STEmpty(&s)){inttop=STTop(&s);printf("%d ",top);STPop(&s);}STDesTroy(&s);return0;}

• 解析：用栈的结构体类型创建一个结构体变量，ST s，然后在主函数中使用栈初始化函数，先给栈结构体初始化，再对栈进行操作，如果需要打印栈元素的话，使用while循环打印栈元素，while循环的判断条件为栈是否为为空栈，一旦为空栈说明栈内元素已经全部打印完成，循环体中先拿出栈顶元素，打印完成以后去除栈顶元素，因为栈是后进先出，所以我们打印的顺序是从栈顶开始。最后一步要对栈进行销毁

2 Stack.h解析

#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>//栈初始化voidSTInit(ST*ps);//栈销毁voidSTDesTroy(ST*ps);//入栈voidSTPush(ST*ps,STDataType x);//出栈voidSTPop(ST*ps);//取栈顶元素STDataTypeSTTop(ST*ps);//栈元素个数intSTSize(ST*ps);//判断空栈boolSTEmpty(ST*ps);

• 解析：写入所以栈操作函数和需要用到的库函数，最后Test.c包含Stack.h就能拿到所以栈操作函数对栈进行操作了，Stack.c函数包含Stack.h就能拿到栈结构体类型，就可以在操作函数就能识别栈结构体类型

typedefintSTDataType;typedefstructstack{STDataType*a;inttop;//栈顶下标，同时等于栈有效元素个数intcapacity;//栈的空间大小}ST;

• 解析：创建栈结构体类型，a为栈元素存放的内存空间的起始地址，也就是realloc开辟的动态内存空间的起始地址，用a这个指针变量接收，而栈的元素类型重命名为STDataType方便使用，然后设置int top 作为栈顶下标，a[top-1]就可以用下标引用操作符通过栈顶元素下一个位置下标找到栈顶元素，同时设置的top初始化为0，也就是指向栈元素的下一个元素位置，这时候top的值等于栈有效的元素个数，最后设置capacity记录栈空间的大小，如果栈空间不够则进行扩容

3 Stack.c解析

1 栈初始化

//栈初始化voidSTInit(ST*ps){assert(ps);ps->a=NULL;ps->top=0;ps->capacity=0;}

• 解析：断言ps，传入的必须是栈结构体地址，不能为NULL，将a初始化为NULL，top和capacity初始化为0，这时候的top既代表了栈顶元素的下一个位置的下标，也代表了栈内有效元素的个数

2 栈销毁

//栈销毁voidSTDesTroy(ST*ps){assert(ps);free(ps->a);ps->a=NULL;ps->top=ps->capacity=0;}

• 解析：断言栈地址是否有效，不能为NULL，是否ps->a中的动态开辟的地址，然后把a置为NULL，然后把top和capacity置为0

3 入栈

//入栈voidSTPush(ST*ps,STDataType x){assert(ps);if(ps->top==ps->capacity){intnewcapacity=ps->capacity==0?4:2*ps->capacity;STDataType*tmp=(STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc:");return0;}ps->a=tmp;ps->capacity=newcapacity;}ps->a[ps->top++]=x;}

• 解析：入栈就是在栈顶插入元素，就是在数组中按下标顺序放置栈元素即可，在顺序表中就是尾插操作，只对尾部进行操作，先判断ps是否为NULL，然后判断栈内空间是否够，如果不够则进行扩容，这段扩容操作不需要独立封装成一个扩容函数，因为栈操作中需要插入元素的操作只有入栈，插入元素就需要判断栈空间的大小是否够，如果空间不够则要进行栈空间的扩容再进行插入操作。满栈的判断条件就是top == capacity ,当栈内有效元素个数等于栈空间大小，则代表满栈，这时候就要进行扩容操作，capacity是记录栈空间大小的整形，扩容我们选用一次两倍扩容的方法，但是我们初始化的时候capacity为0，a为NULL，也就是说当栈仅仅被初始化，没有进行任何入栈操作的时候，栈此时为NULL，没有任何栈元素，capacity为0，如果对0进行2倍扩容，结果依然是0，所以我们要使用三目操作符进行判断，当ps->capacity为0的时候说明这时候栈是仅仅被初始化的，没有入栈，栈为空，我们就先给栈分配四个栈元素的空间，如果ps->capacity!=0，则说明栈不为NULL，可以直接进行二倍扩容操作，这时候我们通过了三目操作符就拿到了整形newcapacity，这时候通过newcapacity作为栈元素的个数，和sizeof(STDataType)相乘的大小作为realloc的第二个参数，就是realloc需要开辟的栈空间的字节数大小，而第一个参数就是动态内存空间的起始地址也就是a，当栈为空栈的时候，a 为 NULL，这时候的realloc就相当于malloc的作用，直接开辟动态内存空间，然后返回开辟的动态内存空间的起始地址，此时的起始地址是void*类型，我们需要强制类型转化为栈元素类型的地址，用tmp接收开辟好的空间的起始地址，判断是否为NULL,为NULL则代表开辟失败，perror打印错误信息，不为NULL则代表开辟成功，我们将开辟成功的栈空间的起始地址tmp赋给a，将newcapacity赋给capacity，到了这一步栈内存空间扩容的问题已经解决，需要进行入栈操作，将x放入下标为top的位置进行插入，插入完以后top++

4 出栈

//出栈voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));ps->top--;}

• 解析：之前就解析过，我们打印操作和读取操作都是通过top作为下标来进行，top作为下标指向的位置为栈顶元素的下一个位置，那么则代表top位置是没有有效元素的，所以只要top的位置发生变化，就可以修改可以访问栈元素的范围，所以出栈直接进行top–即可

5 取栈顶

//取栈顶STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps->a[ps->top-1];}

• 解析：取栈顶的返回值类型是STDataType类型，判断ps是否为NULL，再判断，栈是否为NULL,top是栈顶元素的下一个位置，那么top-1就是栈顶元素的下标，通过下标引用操作符找到top-1下标对应位置的元素返回即可

6 栈元素个数

//栈元素个数intSTSize(ST*ps){assert(ps);returnps->top;}

• 解析:top等于栈有效元素个数，直接返回即可

7 判断空栈

//判断空栈boolSTEmpty(ST*ps){assert(ps);returnps->top==0;}

• 解析：判断是否为空栈，返回判断表达式的结果即可，如果top == 0则代表栈中有效的元素个数为0，表达式为真，返回true,如果top ！= 0 则代表栈中有效元素个数不为0，表达式为假，返回false，true和false都是bool类型的值，所以返回值类型为bool类型

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️