• / 65
  • 下载费用:10 金币  

栈和队列.ppt

关 键 词:
栈和队列.ppt
资源描述:
第4章 栈和队列,4.1 栈及其基本运算 4.2 队列及其基本运算 注意:栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是运算规则较线性表有更多的限制 。,4.1 栈及其基本运算,1.什么是栈,,在栈中,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。,,栈(stack ) 是限定在一端进行插入与删除的线性表。,在图4-1中,栈元素是以a1,a2,…,an 的顺序进栈,而出栈(退栈)的次序却是 an,an-1 , … ,a2,a1。也就是说栈是“先进后出”或,,“后进先出”的线性表。通常用整型变量top (也称top为栈顶指针或栈顶指示器)来指示当前栈顶的位置。,往栈中插入一个元素称为进栈(入栈)运算。从栈中删除一个元素(即删除栈顶元素)称为退栈(出栈)运算。栈顶指针top 动态地反映了栈中元素的变化情况。图4-2说明了在顺序栈中进栈和退栈时栈中元素和TOP的关系。,,2.栈的顺序存储及其基本运算栈的顺序结构通常用一个一维数组和一个整形变量来实现。利用数组来存储栈中的所有元素,利用整形变量指示栈顶元素的下标位置。顺序栈的类型可定义如下:,栈这种数据结构在日常生活中经常见到。例如,学生军训时使用的自动步枪子弹夹,就是一种栈的结构,最先压入子弹夹中的子弹最后才能射出。,#define MaxSize 100 /*设预分配的栈空间最多为100个元素*/ typedef char ElemType; /*设栈元素的数据类型为字符型*/ typedef struct {ElemType stack[MaxSize];int top;/*top指示栈顶元素的位置*/ }SeqStack;,设s是SeqStack类型的指针变量,在顺序栈中,一般用s-top==0表示空栈,但用C语言描述时,由于约定数组的下标从0开始,故用s-top==-1表示空栈;向栈中插入一个元素时(进栈),首先使s-top加1以指示新的栈顶位置,然后再把元素赋值到这个位置。当从栈中删除一个元素时(出栈),首先取出栈顶元素,然后使s-top减1以指示新的栈顶位置。当s-top已经指向了MaxSize-1表示栈满。向一个满栈插入元素和从一个空栈删除元素会产生上溢或下溢。上溢是一种出错状态应该避免,下溢则常用来作为程序控制转移的条件。,栈的五种基本运算是:构造一个空栈、判断栈是否为空、进栈、退栈与读栈顶元素。下面介绍相应的算法。,1)构造空栈构造空栈是指栈的初始化即给s-top赋值-1,算法如下: void InitStack(SeqStack *s) {s-top=-1; },2)判断栈是否为空判断栈是否为空是指判断s-top是否等于-1,若是,则表示栈空返回1;否则返回0,算法如下: int StackEmpty(SeqStack *s)/*int可省略不要*/ {return s-top==-1; },3) 进栈,进栈也称入栈或压栈,是指在栈顶位置插入一个新元素。操作时,首先将栈顶指针s-top 加1以指示新的栈顶位置,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置(即s-top==MaxSize-1)时,说明栈空间已满。向一个满栈插入元素会产生“上溢”错误,算法如下:,void push(SeqStack *s,ElemType x) { /* 插入一个值为x的新元素*/if(s-top==MaxSize-1){printf(“\n 栈已满,上溢!“);exit(1);}++s-top; /*栈顶指针加1*/s-stack[s-top]=x; /*值为x的新元素进栈*/ },4)出栈出栈也称退栈,是指删除栈顶元素。操作时,首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针s-top 减1。当栈顶指针为s-top==-1时,说明栈空。此时进行出栈操作会产生“下溢”错误,算法如下:,,ElemType pop(SeqStack *s) {if(StackEmpty(s)){ /*调用判断空栈函数若栈空则下溢!*/printf(“\n 栈已空,下溢!“);exit(1);}return s-stack[s-top--]; /*返回栈顶元素,栈顶指针减1*/},5)读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意,这个运算不删除栈顶元素只是将它的值赋给一个变量,因此在这个运算中栈顶指针不会改变。但当栈为空时,就读不到栈顶元素了,算法如下:,,ElemType GetTop(SeqStack *s) {if(StackEmpty(s)){printf(“\n 栈已
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:栈和队列.ppt
链接地址:https://www.weizhuannet.com/p-10071073.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开