数据结构笔记6栈（《大话数据结构》学习笔记）

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

【1】栈的定义

就是类似弹夹中的子弹一样先进去,却要后出来,而后进的,反而可以先出来的数据结构一一栈。

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

我们把允许插入和删除的 一端称为栈顶 ( top） ,另一端称为栈低（bottom ） ,不含任何数据元素的栈称为空栈。栈又称为后进先出 ( Last InFilrst Out)的线性表,简称 LlFO 结构 。

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

它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底 。栈的插入操作,叫作进栈,也称压栈、人栈 。 类似子弹入弹夹。

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

【2】栈的抽象数据类型

【3】栈的顺序存储结构及实现

栈的结构定义：

若现在有一个栈, StackSize 是 5 ,则栈普通情况、空栈和栈满的情况示意图：

【4】栈的顺序存储结构一一进栈操作

对于栈的插入,即进栈操作。

【5】栈的顺序存储结构一一出栈操作

【6】栈的链式存储结构及实现

栈的链式存储结构,简称为链栈。

链栈的结构代码如下 :

【7】栈的链式存储结构一一进栈操作

对于链栈的进栈 push 操作,假设元素值为 e 的新结点是 S , p 为栈顶指针,示意图如图：

【8】栈的链式存储结构一一出栈操作

至于链栈的出栈 pop 操作,也是很简单的 三句操作 . 假设变量 p 用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放 p 即可。

对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为 O(1) 。对于空间性能, 顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样, 如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。