前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

4.1 初始栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许再一端进行插入操作、而在另一端进行删除操作的线性表

4.2 栈的定义

4.2.1 栈的定义

栈的结构类似与弹夹中的子弹，先进去的后出来，后进去的先出来。这就是数据结构中的栈。

生活中，栈这种后进先出数据结构的应用是非常普遍的。像常用的浏览器后面都会有后退键，你点击后可以按访问顺序的逆序加载浏览过的网页。

还有常用的Office都会有撤销的操作。不同软件具体实现代码会有所不同，原理都差不多

栈（stack）是限定仅在表位进行插入和删除操作的线性表

把允许插入和删除的一端称为栈顶(top), 另一端称为栈底(bottom), 不 含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构

1.一些要注意的点

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹

栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹

4.2.2 进栈出栈变化形式

最先进栈的元素，是不是就只能是最后出栈呢?

答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

举例来说，如果现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢?

第一种: 1、2、3进，再3、2、1出。这是最简单的最好理解的一种，出栈 次序为321

第二种: 1进，1出，2进, 2出，3进，3出。也就是进一个就出一个，出 栈次序为123

第三种: 1进，2进，2出，1出，3进，3出。出栈次序为213

第四种: 1进，1出，2进，3进，3出，2出。出栈次序为132

第五种: 1进，2进，2出，3进，3出，1出。出栈次序为231

有没有可能是312这样的次序出栈呢?答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2一定是在1的上面，就是更接近栈顶，那么出栈只可能是321,不然不满足123依次进栈的要求，所以此时不会发生1比2先出栈的情况。

4.3栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop,英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT栈(stack)
 Data
     同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
 Operation
     InitStack (*s):初始化操作，建立一个空栈S。
     DestroyStack(*s) :若栈存在，则销毁它。
     ClearStack (*s) :将栈清空。
     StackEmpty(s) :若栈为空，返回true,否则返回false。
     GetTop(s,*e) :若栈存在且非空，用e返回S的栈顶元素。
     Push(*s,e):若栈S存在，插入新元素e到栈S中并成为栈顶元素。
     Pop(*S,*e) :删除栈S中栈顶元素，并用e返回其值。
     StackLength(s) :返回栈S的元素个数。
 endADT

由于栈本身就是一个线性表，那么上一章讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。