有一天晚上轮到我洗碗，过后跟一个同学打了个电话，我说今晚我洗个碗总感觉有种淡淡的忧伤。他马上来一句是哪个dan？哦不对，你长得这么丑应该没有权力忧伤才得啊！我说我顶你个，我不是这个意思啊，我意思是洗个碗洗出了数据结构。你又猜对了，今天我讲的还是线性表，只不过是个特殊的线性表，叫做栈（Stack）。
栈这个词在历史上应该算是很有名的，大汉王朝汉高祖刘邦出关中时用的策略就是“明修栈道，暗渡陈仓”，相传是张良在刘邦就任汉中王的时候给了一个锦囊，说如果哪一天哪条友仔对于出关中对上了锦囊上的策略，就是可以帮你夺得天下的人，要封他为天下兵马大元帅，刘大爷也没想到啊，来了个受过跨下之辱的韩信，要是你也不敢相信了是吧，好像又扯远了，不过为什么提到韩信，那是因为他在下一篇将会登场，提前剧透一下而已。有的同学不禁要问了，刘邦修栈道的栈跟我们讲的栈是一样的吗？我说一点哪nèng都没有会不会被打，纯属凑个字数呗。那为什么洗个碗就能想到栈，如果每天洗一两次碗是不是就能学好数据结构的话还要老师干嘛，这话好像在哪里见过了吧，对了就是在F4版的《流星花园》里：道歉有用的话还要警察来干嘛。该是要言归正传了，要不然真成了懒婆娘的裹脚了，你不会连懒婆娘的裹脚都不知道吧……
讲了一些废话，是因为栈是一处特殊的线性表，线性表我们已经讲了两篇，今天只需要讲栈它的特殊性在哪里以及它有些什么操作就算完成任务了。那就先说栈的官方定义：栈是限定仅能在表的一端进行插入和删除操作的线性表。看到了吧，从语文的角度来说，去掉定语是不影响语义的，栈的定义去掉定语之后就剩下“栈是线性表”，既然是线性表就有线性的性质，有前驱元素有后继元素，除第一个元素外都有前驱，除最后一个元素外都有后继。那栈的特殊性在哪里呢？就是在它的定语上，毕竟她是女人和她是王的女人是不一样的。栈限定仅能在表的一端进行插入和删除操作也就是说有一端它是封闭的，封闭的这一端我们叫它栈底，可以进行插入和删除操作的一端我们叫它栈顶，插入元素叫进栈或者压栈，删除元素叫出栈或者退栈，看到这里好像还不明白特殊性在哪里又跟洗碗有什么关系是吧。好吧，我摊牌了，既然有一端是开口一端封闭，那就是先进栈的元素只能最后出栈，专有名词叫LIFO（lastinfirstout后进先出）也叫先进后出。先进后出或者说后进先出这种东西有什么用？就像我们洗好的碗摞在一起，最先洗好的那个碗是不是要等摞在上面碗拿走它才能拿走？还有我们把螺母拧到螺钉上，如果有多个螺母，先拧进去的螺母是不是要等后面的螺母先拧出来才到它？还有普通人不常见阿Sir把子弹压进弹夹，先压进去的最后才被打出去。常用办公软件的人应该会用到“撤销”，经常上网的人应该会用到“后退”，这撤销和后退的实现原理就是用到了栈，真是生活无处不数据结构啊。
由于栈是一种特殊的线性表，所以线性表的有些操作并不合适栈，所以我们只讨论栈的进栈和出栈操作，同样也有两个存储结构：顺序存储结构和链式存储结构，顺序存储结构具体实现可以用数组，链式存储结构具体实现可以用链表。
（1）初始化栈
有好多数据结构的书本在初始化栈的时候，并不设置记录栈长度的参数，个人觉得是有必要的，比如枪支弹夹里面还有多少发子弹，在紧急情况下阿Sir怎么会一直记得还剩有多少发呢，如果有个数字直接显示余量，那不是很好吗？不过也有个问题啊，电影里老大想黑某个反判的二五仔时通常是给他一把没有子弹的枪，然后我们就可以脑补二五仔不断扣动扳机要干掉老大时情形。
既然栈是线性表则有顺序和链式存储两种结构，如果采用顺序存储结构实现，我们一般使用数组来实现栈，默认初始化空栈时把栈顶位置指针记录为-1，为什么要用-1而不用0呢，因为数组下标是从0开始的，防止混淆引起不必要的麻烦。如果用链式存储结构实现，初始化时创建一个头结点并把指向下一个结点的指针设为空（NULL）即可。
（2）入栈
入栈也叫进栈、压栈，因为栈的特性是只能从一头进出栈，这一头就叫栈顶，不能进出栈的另一头则叫栈底，也不是最下面的碗是栈底，上面的碗是栈顶，所以入栈的时候只需要从栈顶操作。如果是顺序存储结构实现则把栈顶位置指针先自增1，再压栈，所以知道栈为空的时候为什么记录为-1了吧，就是为了保持与数组的下标一致；如果是链式存储结构则用线性表的头插入法，把新增结点插入头结点（不放值）的后面，每一次压栈都插入头结点的后面，所以就达到了插入的最优情况（不需要一个一个移动指针到栈底再插入），也达到了先入栈的被甩得更远，那出栈的时候是不是就只能在后面了？
（3）出栈
出栈也是弹栈、退栈，出栈只能从栈顶位置出栈，就像弹夹打出的子弹只能是最上面的一颗，螺母也只能先扭出最上面的一颗，不会有愤青说拿碗可以先拿下面的吧，就算是这样拿是不是也要先移开上面的碗呢？如果是顺序存储结构实现则直接取栈顶位置，然后栈顶指针再自减1，出完后又变回-1了，这时候就是空栈。如果是链式存储结构则把头结点（不放值）的指针指到头结点后面的结点的后面结点，是不是有点拗口了？就像一根腾上的七个葫芦娃，老大生出来了，下一个是不是就是老二排第一了？只不过它没有头结点的概念，那我们把葫芦娃妈妈看成头结点好了。
（4）清空和删除栈
清空栈只是把栈的内容清除，并没有把栈给销毁掉，删除栈则是要把栈销毁掉，释放掉内存。如果是顺序存储结构实现则直接把栈顶位置设为-1即可，这时候其实并没有清除里面的内容，只不过再进栈的时候根据移动栈顶位置会把原来的内容覆盖了而已。如果是链式存储结构实现则要把所有的结点释放掉内存，清空操作的话只留下头结点，删除操作则全释放。
还要再啰嗦一下，栈是特性的线性表，所以基本的操作与线性表的操作类似，只要记住栈是LIFO（lastinfirstout后进先出）也叫先进后出。
纯属个人见解，如有不对，欢迎指正。
预览时标签不可点收录于话题#个上一篇下一篇