当前课程知识点：数据结构 > 第3章 栈和队列 > 3.1 栈 > 3.1栈
同学们，大家好，我是云南大学信息学院教师孔兵
这一章我们讨论栈和队列
上一章，我们讨论的线性表
这一章讨论的栈和队列都被称为操作受限的线性表
栈和队列就数据元素及它们之间的关系来说
就是一个线性表，也就是说它还是一个序列
但是，栈和队列在插入和删除操作上受到了限制
所限制的是插入和删除的位置
我们在线性表中讨论过插入和删除操作
线性表中如果有n个元素
在线性表中插入的时候呢
合法的插入位置是1，2到n+1
合法的插入位置共有n+1个
删除的时候，合法的删除位置是1，2到n
合法的删除位置共有n个
栈和队列呢，他们的插入和删除位置是受到限制的
就栈而言，合法的删除位置只有一个
就是线性表的第n个元素，也就是线性表最后一个元素
合法的插入位置呢，也只有一个
就是第n+1个位置
队列呢，合法的删除位置是只有第1个位置
就是a1这个位置
合法的插入位置也只有一个
是第n+1个位置
因为插入和删除的位置受到了限制
所以，栈和队列有一些不同于普通线性表的特征
栈是限定仅在表尾进行插入和删除的线性表
为了讨论的方便，我们把表尾这一端称为栈顶
就是an这端，把表头这一端称为栈底
从栈的受限来看
插入和删除操作的位置都是在栈顶这一端
栈中没有元素的时候呢，我们成为空栈
下面结合示例，我们讨论一下栈的特征
栈是一个线性表，在描述上可以写成一个序列
a1,a2,…,an
称a1为栈底元素，an为栈顶元素
因为插入和删除都是在栈顶进行
这样的限制
使栈具有了普通线性表没有的特征
它主要的特征是所谓后进先出
后进先出，就是后插入的，先删除
我们把栈的插入操作称为入栈
栈的删除操作称为出栈
画栈的时候，我们一般把序列画成竖的样子
如图所示，a1这端在下部，an这端在上部
因为栈的插入受限
栈中元素的次序体现了元素插入的次序
如果栈中元素是a1,a2,…,an
那么元素入栈的次序就是a1先入
其次a2，最后an
出栈也是受限的
出栈的次序也会受到影响
下面通过一个例子
看看入栈序列和出栈序列的特征
假设占初始的时候为空栈
我们的入栈序列是1234
按照这个次序插入到栈中
允许入栈和出栈的操作交替进行
那么现在我们来考虑，在限制之下
可能的出栈序列和不可能的出栈序列
以出栈序列1234为例
可以这样获得这个出栈序列
1入栈，1出栈，2入栈，2出栈
3入栈，3出栈，4入栈，4出栈
我们就可以获得1234这样的出栈序列
从上述操作来看
所有的插入和删除操作都是在栈顶
这就是一个在限制下可能的一个出栈序列
再看，1342,可以这样获得
1入栈，1出栈，2,3连续入栈
3出栈，4入栈，42连续出栈
这样合法的出栈序列还有多个
同学们可以自己试一下
但是，同样因为受限
有的组合序列是不可能出现的
以出栈序列3412为例
因为出栈序列中第1个出栈的是3
因删除的限制，此时3应该是栈顶元素
那么，根据入栈次序
栈中应该是1,2,3，3位于栈顶
3出栈后，4入，4出，我们获得出栈序列34
栈中元素是1,2,2位于栈顶
根据出栈位置的限制
下一个出栈的必须是2
所以，我们不可能获得3412这样的出栈序列
再看一个不可能的出栈序列4231
4第1个出栈
按入栈的次序1234已经入栈
4位于栈顶，4出栈后
同样是出栈位置的限制
下一个出栈的只能是3
不能获得4231这样的出栈序列
对不可能的出栈序列我们可以总结一下它的特点
如果有后入栈的元素先出栈
如上例中的4是后入栈的
那么，在它前面入栈的元素
不可能出现同入栈次序相对位置相同的序列
如上例中的
23
这样的情况只要出现一个
就是不可能的出栈序列
关于栈的的特征
我们就讨论到这
下面看一下栈的抽象数据类型定义
在抽象数据类型占的定义当中
数据对象和数据关系这两部分
我们可以看到和线性表实际没有什么差异
就是说从数据结构来看
栈本身就是个线性表
在这做了一个简单的约定
约定an这一端栈顶，a1这端为栈底
下面简单看一下几个栈的操作
第1个是判断栈空的操作
栈为空返回真，非空返回假
Push是入栈的操作
实际上也就是插入的操作
涉及到两个参数
一个是要插入的对象栈S
一个是要插入的元素e
从插入操作来看
和线性表的插入操作的参数比较
少了一个插入位置的参数i
线性表的插入操作当中i指的是要插入的序列中的位置
而这里呢，因为栈中已经限定了插入的位置只能是n+1
所以这个关于位置插入位置的参数也就不需要了
Pop是删除操作
和插入操作类似，也有两个参数
一个是要删除的对象栈S
一个是一个引用e，用来带回删除的数据元素
同样也不需要指出删除的位置了
第4个基本操作是getTop
它的意思是取出栈顶元素
用引用e带回所取元素
取栈顶点元素并不涉及到对栈的删除
只是取出栈顶元素即可
同学们
关于栈的基本概念和特征我们就讨论到这儿
下节课再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结
