软件技术基础概论 教学课件 作者 吕林涛第3章 栈和队列.ppt

《软件技术基础概论 教学课件 作者 吕林涛第3章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*第3章栈和队列*第3章栈和队列栈和队列都是操作受限的线性表栈：先进后出队列：先进先出*本章主要内容:栈的定义及基本运算栈的存储结构和运算实现队列的定义及基本运算队列的存储结构和运算实现第3章栈和队列*3.1栈的定义及基本运算栈的定义栈的基本操作*栈的定义栈是限定仅在一端进行操作的线性表栈顶（top）：允许进行插入和删除元素操作的一端栈底（bottom）：固定不变的另一端空栈：不含元素的栈满栈：存储空间被用完的栈先进后出*3.1栈的定义及基本运算栈的定义栈的基本操作*栈的基本操作栈初始化Init_Stack(s)：生成

2、一个空栈s判栈空Empty_Stack(s)：若栈s为空则返回1，否则返回0入栈Push_Stack(s,x)：在栈s的顶部插入一个新元素x，使x成为新的栈顶元素，栈变化出栈Pop_Stack(s,x)：在栈s非空的情况下，操作结果是将栈s的顶部元素从栈中删除，并由x返回栈顶元素值，即栈中少了一个元素，栈变化读栈顶元素Top_Stack(s,x)：在栈s非空的情况下，操作结果是将栈s的顶部元素读到x中，栈不变化*本章主要内容:栈的定义及基本运算栈的存储结构和运算实现队列的定义及基本运算队列的存储结构和运算实现第3章栈和

3、队列*3.2栈的存储结构和运算实现顺序栈两个顺序栈共享连续空间链栈*顺序栈顺序栈：栈的顺序存储结构利用一组地址连续的存储单元来依次存放由栈底到栈顶的所有元素，附加一个top指针来指示栈顶元素在顺序栈中的位置typedefstruct{datatypedata[MAXSIZE];//栈中元素存储空间inttop;//栈顶指针}SeqStack;顺序栈的类型定义*顺序栈顺序栈操作示意图*顺序栈顺序栈基本操作：初始化栈voidInit_SeqStack(SeqStack**s){*s=(SeqStack*)malloc(si

4、zeof(SeqStack));//在主调函数中申请栈空间(*s)->top=-1;//置栈空标志}*顺序栈顺序栈基本操作：判断栈是否为空intEmpty_SeqStack(SeqStack*s){if(s->top==-1)//栈为空时返回1值return1;elsereturn0;//栈不空时返回0值}*顺序栈顺序栈基本操作：入栈voidPush_SeqStack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)printf("Stackisfull!");//栈已满els

5、e{s->top++;//先使栈顶指针top增1s->data[s->top]=x;//再将元素x压入栈*s中}}*顺序栈顺序栈基本操作：出栈voidPop_SeqStack(SeqStack*s,datatype*x){//将栈*s中的栈顶元素出栈并通过参数x返回给主调函数if(s->top==-1)printf("Stackisempty!");//栈为空else{*x=s->data[s->top];//栈顶元素出栈s->top--;//栈顶指针top减1}}*顺序栈顺序栈基本操作：取栈顶元素voidTop_

6、SeqStack(SeqStack*s,datatype*x){if(s->top==-1)printf("Stackisempty!");//栈为空else*x=s->data[s->top];//取栈顶元素值赋给*x}*3.2栈的存储结构和运算实现顺序栈两个顺序栈共享连续空间链栈*两个顺序栈共享连续空间利用栈底位置相对不变这一特点，两个顺序栈可以共享一个一维数据空间来互补余缺。实现方法是将两个栈的栈底分设在一维数据空间的两端，让其各自的栈顶由两端向中间延伸*两个顺序栈共享连续空间多个栈共享一维数据空间的问题就比

7、较复杂，因为一个存储空间只有两端是固定的，需要：设置栈顶指针和栈底指针。这种情况下，当某个栈发生上溢时，如果整个一维数据空间未被占满，则必须移动某些（或某个）栈来腾出空间解决所发生的上溢*3.2栈的存储结构和运算实现顺序栈两个顺序栈共享连续空间链栈*链栈链栈是指以链式存储结构存储的栈链栈是动态分配元素存储空间的，所以操作时无需考虑顺序栈容易出现的上溢问题，这样，多个栈的共享问题也就迎刃而解了typedefstructnode{datatypedata;structnode*next;}StackNode;链栈的定义：*

8、链栈链栈的基本操作：初始化链栈voidInit_LinkStack(StackNode**s){*s=NULL;//置栈顶指针*s为空}*链栈链栈的基本操作：判断链栈是否为空intEmpty_LinkStack(StackNode*s){if(s==NULL)return1;//栈为空时返回1值elsereturn0;//栈不空时