💕休对故人思故国，且将新火试新茶，诗酒趁年华💕
作者：Mylvzi
文章主要内容：详解链表OJ题
前言：
前面已经学习过顺序表，链表。他们都是线性表，今天要学习的栈也是一种线性表。那么，什么是栈呢？栈又是如何实现对数据的管理呢，下面进行讲解。
栈的定义：
栈就是一种只能在栈顶进行元素的添加删除的线性表。具有“后进先出”的特性，就是后面进入的元素反而首先被删除！所以栈的这种结构又被称为LIFO结构（Last In First Out）;
我们可以把栈理解为枪的的弹夹，试想，每次压子弹的时候是不是只能从一端插入？先插入的子弹会被先打出去，子弹装填的过程对应着数据的进入，被称为“入栈”，而子弹的射出，对应着数据的删除，被称为“出栈”！
栈的结构：
我们知道，栈的最大特点就是只能在一端进行数据的添加和删除，那栈应该使用哪种结构来实现呢？是数组，还是链表呢？其实，最常使用的应该是数组。因为数组进行尾部数据的删除更简单！（数组的尾部就相当于栈顶），如果使用单链表，我们要保存上一结点的地址；如果使用双向链表，其结构没有数组简单；而且，数组对缓存的利用率要高于链表！能提高效率！
栈的实现：
定义栈元素：
//定义栈元素 typedef int STDataType; typedef struct Stack { STDataType* a;//存储数据 int top;//栈顶 int capacity;//容量 }ST;
栈的初始化与删除：
//初始化栈 void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0;//代表栈顶下一个位置 ps->capacity = 0; } //删除栈 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
入栈和出栈
//入栈 void STPush(ST* ps, STDataType x) { assert(ps); //栈满要扩容 if (ps->top == ps->capacity) { //要考虑最开始top == capacity为0的情况 //使用了三目运算符:为0，则新的容量值为4；不为0，新的容量值为原来的2倍 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newcapacity); if (tmp == NULL) { perror("realloc"); exit(-1); } //重新赋值 ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } //出栈 void STPop(ST* ps) { assert(ps); //空 assert(ps->a); ps->top--;//不需要管原来数据，直接让栈顶向前移动 }
返回栈顶元素：
//返回栈顶元素 STDataType STTPop(ST* ps) { assert(ps); assert(ps->a); //设置的top位最后一个元素的下一个位置 return ps->a[ps->top - 1]; }
计算元素个数和判断是否为空栈
//计算有效值个数 int STSize(ST* ps) { assert(ps); //top就是栈内的数据个数 return ps->top; } //判断是否为空栈 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }
总结：
大家刚接触栈可能很疑惑栈的应用场景有哪些呢？举个例子，在我们上网时在某个网页遇到了一个吸引人的链接，你忍不住好奇心，点了进去，发现是不良网站，你想退到你原先浏览的界面，这是你就可以点击浏览器上方的后退键，就自动退回到原先的浏览界面。其实在这个过程中，一个一个的网页被“入栈”，你进去的不良网站就是栈顶元素，后退键其实是实现了“出栈”的一个过程；
再比如画图软件中的“撤销”操作，本质上也是进行了“出栈”的操作；所以，栈的应用还是很广泛的，其他应用还需要大家自己摸索！
