资源描述：
《stack数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章栈和队列掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。学习提要课前思考1.什么是线性结构？2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？栈和队列是两种常用的数据类型栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性D
2、S，栈必须按"后进先出"的规则进行操作，而队列必须按"先进先出"的规则进行操作只能在表的“端点”插入和删除进行的线性表，栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删除。3.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾对应栈顶，表头对应栈底，不含元素的空表称空栈。往栈顶插入元素的操作为“入栈”，称删除栈顶元素的操作为“出栈”。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种"后进先出"的结构特点：先进后出（FILO）或后
3、进先出（LIFO）栈（stack）ana1a2……...栈底栈顶...出栈入栈栈s=(a1,a2,……,an)铁路调度站形象地表示栈的这个特点想一想：若要从栈中取出a1，该如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！思考题：铁道进行火车调度时，总把站台设成栈式（1）设有编号为1，2，3，4的四辆列车，顺序进入栈内，问可能得到哪些出栈顺序？1,2,3,41,2,4,31,3,2,41,3,4,21,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,3,13,2,1,43,2,4,13,4,2,14,3,2,1共14种结论：当输入元素
4、数目为n,即输入序列为1,2,…,n时，经过栈的运算后可获得的输出序列的个数由尤.卡塔南数决定为：(2n)!/n!n!(n+1)（2）若进栈顺序为1,2,3,4,5,6问能否得到4,3,5,6,1,2;3,2,5,6,4,1;1,5,4,6,2,3;1,3,5,4,2,6的出栈顺序，为什麽？讨论1：栈是什么？它与一般线性表有什么不同？答：栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出
5、(LIFO)“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)ADTStack{数据对象：D＝{ai
6、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R＝{
7、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，
8、则返回TRUE，否则FALE。栈的抽象数据类型的定义：基本操作：（续）StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack栈的顺序存储结构简称为顺序栈，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指向实际栈顶后的空位置。顺序栈a
9、1a2……an顺序栈Sai……表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an+1弹出(POP):e=S[--top]低地址高地址S[i]a1a2aian……顺序表S……an+1以线性表S=(a1,a2,….,an-1,an)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top顺序表和顺序栈的操作区别顺序栈的类型定义如下：#defineSTACK__INIT__SIZE100;//存储空间初始分配量#defineLISTINCREMENT10；//存储空间分配增量typedefstructure{S
