《栈的性质、栈的基本操作.ppt》由会员分享，可在线阅读，更多相关《栈的性质、栈的基本操作.ppt（22页珍藏版）》请在三一办公上搜索。
1、,首页,遇到困难时,请发挥集体的智慧!,有所收获,教案,主要内容,栈的概念 栈的基本操作 栈的存储 顺序栈的实现,引例,在日常生活中，有一些这样的例子。例1：食堂师傅把洗好的饭盒按顺序放好，最后洗的饭盒总是放在一叠饭盒的最上面。同学们到食堂就餐时，拿饭盒总是按照由上到下的顺序拿，即总是拿一叠饭盒中最顶上的一个。例2：有一个盒子，我们在里头放了一叠书。当我们要用书的时候，只能从第一本开始拿；当我们要把书本放进去时，总是放在最上面。请问：上面的例子中有什么共同的特点？,后放进去的，先拿出来。,栈的概念和特点,什么是栈？栈是一种特殊的线性表，它只在线性表的一端进行插入和删除操作。栈中允许插入、删除的
2、这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈的特点“先进后出”（First In Last Out）或“后进先出”（Last In First Out）,返回,栈的基本操作,栈主要有建栈、入栈、出栈和销毁栈四个基本操作。建栈：新建一个空栈，向操作系统申请一组存储单元，用于存储栈中的元素。入栈：将元素压入栈内，存储在栈顶。出栈：从栈中取出栈顶元素，也称为弹出栈。销毁栈：把存储单元归还给操作系统。为了实时了解栈的情况，还需要有输出栈这样的操作。输出栈：显示栈的内容。,返回,栈的存储,回顾：前面介绍的线性表是采用什么方式存储数据的？栈与前面介绍过的线性表一样，也可以采用顺序存储
3、结构（数组）或者链式存储结构（链表）。,顺序栈,链栈（单链表）,栈的表示 可以用一个栈顶指针（top）来指示栈顶元素存放的位置，用一个栈底指针（bottom）来指示栈底元素的存放位置。由于栈底位置相对不变，通常不用bottom。,顺序栈的示意图,链栈的示意图,返回,顺序栈的实现,【例】先建栈，然后输入一个整型元素后入栈，显示栈的内容。接下来进行出栈操作，再显示栈的内容。最后销毁栈。数据结构描述顺序栈的类型描述如下：#define MAXSIZE 200 struct seqstack Elemtype dataMAXSIZE;int top;定义一个指向顺序栈的指针：struct seqsta
4、ck*s;源程序,运行程序(10_1),看源程序(10_1),建栈,分析 首先申请栈空间，然后初始化栈顶指针。流程图 源程序,运行程序(10_1),看源程序(10_1),入栈,流程图 源程序int push_seqstack(struct seqstack*s,Elemtype x)s-datas-top=x;s-top+;return 1;,思考：如果不断入栈，会出现什么情况？(10_2),上溢出,检查栈是否满的子函数,源程序/*/*函 数 名：full_seqstack*/*函数功能：检查栈是否满*/*入口参数：s栈*/*返 回 值：栈满返回1，否则返回0*/*/int full_seqs
5、tack(struct seqstack*s)if(s-top=MAXSIZE)return 1;else return 0;,改进后的入栈,分析 为了防止上溢发生，在入栈前先检查栈是否满。若未满，则进行入栈操作，否则进行溢栈处理或溢栈报告。流程图 源程序,运行程序(10_1),看源程序(10_1),出栈,流程图 源程序int pop_seqstack(struct seqstack*s,Elemtype*x)s-top-;*x=s-datas-top;return 1;,思考：如果不断出栈，会出现什么情况？(10_2),下溢出,检查栈是否为空的子函数,源程序/*/*函 数 名：empty_s
6、eqstack*/*函数功能：检查栈是否为空*/*入口参数：s栈*/*返 回 值：栈空返回1，否则返回0*/*/int empty_seqstack(struct seqstack*s)if(s-top=0)return 1;else return 0;,改进后的出栈,分析 为了防止下溢发生，在出栈前先检查栈是否为空。若不空，则进行出栈操作，否则进行溢栈处理或溢栈报告。流程图 源程序,运行程序(10_1),看源程序(10_1),显示栈,源程序 void display_seqstack(struct seqstack*s)int i;if(empty_seqstack(s)printf(目前栈
7、为空!n);return;printf(目前栈的内容为：);for(i=0;itop-1;i+)printf(%d,s-datai);printf(n);,销毁栈,分析 只要释放建栈时所申请的空间即可。源程序/*/*函 数 名：destroy_seqstack*/*函数功能：销毁栈*/*入口参数：s栈*/*返 回 值：无*/*/void destroy_seqstack(struct seqstack*s)free(s);,清除栈,有的情况下只需要清除栈，而不销毁栈。清除栈：只是将栈内元素清空，栈的存储空间仍保留。清除栈的源程序/*/*函 数 名：clear_seqstack*/*函数功能：清除栈*/*入口参数：s栈*/*返 回 值：无*/*/void clear_seqstack(struct seqstack*s)s-top=0;,运行程序(10_3),看源程序(10_3),本次课总结,栈的概念 栈的特点 栈的主要操作 栈的存储 顺序栈的实现,栈是一种特殊的线性表。,特殊在什么地方？,后进先出,入栈、出栈,顺序存储、链式存储,顺序栈,链栈,下课,Thank You！,The End.,
