数据结构@3 栈和队列ppt课件.ppt

《数据结构@3 栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列学习提要掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。第3章栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an

2、是栈顶元素。a1a2….an进栈出栈栈顶栈底3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，

3、而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：（1）初始化栈InitStack(S)（2）入栈Push(S,item)（3）出栈Pop(S,item)（4）获取栈顶元素内容GetTop(S,item)（5）判断栈是否为空StackEmpty(S)栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=010S[4]2310bases[top

4、]=xtop=top+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=0top栈满top=stacksize10253040S[4]2310top=4base3.1.2栈的存储结构顺序栈、链栈a2a1a1a2top顺序栈：用顺序存储结构表示的栈。顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。·进栈算法#definestatcksize100intpush(int

5、s[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4987654321a10top·进栈算法#definestatcksize100intpush(ints[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize){printf(“

6、overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4a5987654321a10top·进栈算法#definestatcksize100intpush(ints[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/r

7、eturn(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4a5987654321a10top栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#defineMAX_STACK10//栈的最大数据元素数目typedefstructstack{StackEntryitem[MAX_STACK];//存放栈中数据元素的存储单元inttop;//栈顶指针}STACK;基本操作算法：1.初始化栈SvoidInItStack(STACK*S){s->top=-1;}通常的习惯做法是以To

8、p=0表示空栈，鉴于C语言中数组的下标从0开始，则当以C语言来描述时，如此设定会带来很大的不方便，因此可以设Top=-1来表示空栈。2.入栈voidP