资源描述：
《数据结构第三章栈和队列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第3章栈和队列本章学习线性表中两种特殊的线性表：栈和队列，其逻辑结构与前一章所学的线性表一样，均为线性结构，但它们是操作受限的线性表。当插入、删除操作只能在表的一端进行吋称为栈。当插入从表的一端进行，删除从表的另一端进行吋称为队列。栈和队列在递归、模拟现实过程中都有重要的作用，掌握它们的相关概念及运算是十分必要的。本章除了讨论栈和队列的定义、表示方法和实现外，还将给出一些应用的例子。3.1栈的基本概念3.1.1栈的自然语言定义栈(stack)是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端为变化的一端，
2、称为栈顶(top),不允许插入和删除的一端称为栈底(bottom)o如图3-1所示：图3-1栈结构的示意图向一个栈插入新元素的操作称为进栈或入栈(Push),它是把该元素放到栈顶元素的上面，使Z成为新的栈顶元索。从一个栈删除一个元素的操作称为出栈或退栈(Pop),它是把栈顶元素删除掉，使其下血的相邻元素成为新的栈顶元素。当栈中无数据元素吋，称为空栈。由栈的定义可知，后入栈的元素先于先入栈的元素出栈，因此，栈的运算特性是后进先出(LastInF'irstOutLIFO)或先进后岀(FirstInLastOutFILO)。在日
3、常生活屮，有许多类似栈的例子，如刷洗盘子时，把洗净的盘子一个接一个地向上放(相当于进栈)，取用盘子时，则从上面一个接一个地向下拿(相当于出栈)；又如向自动步枪的弹夹装子弹，子弹被一个接一个地压入(相当于进栈)，射击时总是后压入的先射出(相当于出栈)。3.1.2栈的ADT定义ADTStack{数据对象：D={aj
4、ai^ElemSet,i=l,2,•••,n,nNl}数据关系：Ri={
5、ai-i,a£D,i=2,3,•••,n}基本操作：InitStack(S):初始化操作，设定一个空栈S；EmptyStac
6、k(S)：判断栈S是否为空，若S为空栈，则函数返回1,否则返回0；Push(S,e)：入栈操作，在栈S顶部插入元素若栈满返回0,否则将e入栈，并返回1；Pop(S)：出栈操作，若S不空，则返回栈顶元素，并删除栈顶元素；否则返回0；GetTop(S)：取栈顶元素操作，返回栈顶元素；StackLength(S)：返回栈S屮当前元素的个数；ClearStack(S)：将S置为空栈；}ADTStack3.2栈的顺序存储结构及其运算3.2.1栈的顺序存储结构顺序存储结构的栈又称顺序栈，与第二章讨论的顺序表类似，可利用一组地址连续的存
7、储单元依次存放从栈底到栈顶的数据元素。因此，我们对以使用预设的足够长度的一维数组来实现。由于栈顶的位置经常变动，通常设一个指示器top指向栈顶元素所在的位置。当有新元素进栈时，栈顶指针向上移动，top加1。当有元素出栈时，栈顶指针向下移动,top减1。注意，在顺序栈中，top是整型变量，相当于数组的下标，top总是指向栈顶元素在栈中的位置。用C语言描述顺序栈的数据类型如下：#defineMAXSIZE100//栈允许存放元素个数的最大值typedefstruct{ElemTypedatas[MAXSIZE];//栈的存储空
8、间inttop;//栈顶指示器}SqStack;在这个描述中,用数组datas[MAXSIZE]作为栈的存储空间,datas[top]为栈顶元素，鉴于C语言中数组下标是从0开始的，我们约定当top=-l吋栈为空；当top=0吋，栈中有一个元素；当top二MAXSTZET时，表示栈满。图3-2说明了顺序栈中数据元素与栈顶指针的变化，(a)表示空栈状态；(b)表示有二个元素A,B相继入栈后的状态；(c)表示栈满；(d)是在图(c)之后，元素相继出栈，此时栈中还有3个元素。也许最近出栈的元素仍在原先的单元中存储着，但top已经指
9、向了新的栈顶，我们认为出栈的元素已经不在栈中了。图3-2栈的状态及栈顶指针示意图当top二-1,即栈为空时，从空栈屮再删除一个元素，栈将溢岀，称为“下溢”。当top二MAXSIZE-1,即栈满时,向栈中再插入一个元素,栈也将溢出,称为“上溢”。3.2.2顺序栈的基本操作1.初始化空栈操作voidInitStack(SqStack*S){S->top=-l;}//InitStack2.判栈空操作intEmptyStack(SqStack*S)//若栈空返回1；否则返回0{if(S->top~-l)return1;elsere
10、turn0;}//EmptyStack3.入栈操作intPush(SqStack*S,ElemTypee)//若栈满返回0；否则将e入栈，并返回1{if(S->top==MAXSIZE-l){printf(“栈满！”);return0;}else{S->top++;S->datas[S->top]=
