当前课程知识点：数据结构 > 第3章 栈和队列 > 3.1 栈的定义及ADT > 讲解
同学们好，本章我们来学习栈和队列
本章分为以下六部分内容
先来看第一部分：栈的定义及ADT。先来看一下栈的定义
栈
实际上是我们前面讲的线性表的一种
操作受限的形式
如果我们规定，只能在线性表的一端进行插入和删除
这时候的线性表，实际上就变成了一个栈
而允许插入、删除元素的那一端
我们称为栈顶
另一端称为栈底
我们来看一个图
这个图
描述了一个开口向上的容器
注意，这个图不是内存
因为，我们现在是在讲栈的逻辑结构
没有涉及到计算机和内存
就跟我们现实生活当中的容器一样
我们只能在开口端，往容器里面放东西
从容器当中拿东西的时候
我们也是从开口端拿的
上面的东西没有拿出来
之前，压在下面的东西，是不可能拿出来的
而栈就描述了这样的一种数据结构
在图当中
4个元素
a1
a2、a3、a4，先后被插入到线性表当中
删除的时候
必须先删除a4，才能再删除a3，一直到a1
所以，上面的这个限制，使得栈具有后进先出的特性，就如同弹夹一样
后压入的子弹，总是先被发射出去
第一次压入的子弹，是最后被发射出去的
为了区别于线性表的插入、删除元素
我们把栈的插入
叫做入栈
英文叫Push
栈的删除元素
我们称为出栈，英文叫Pop
现在，我们来看一下，栈的抽象数据类型定义
我们主要看操作部分，init，初始化
一个栈，栈从无到有
所以，前面有引用参数；销毁一个栈，释放栈所占用的内存
判断栈S是否为空
我们将是否为空的结果，放到empty这个参数里面
getTop，得到栈S的栈顶元素
把它放到e里面
push
将元素e压入到S的栈顶位置
pop，将栈S的栈顶元素弹出来，放到e里面
需要注意，getTop和pop的区别
getTop仅仅是获得栈顶元素
它不会修改栈
而pop
是把栈顶元素删除
也就是出栈
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
