数据结构及应用算法教程（修订版） 第4章 栈和队列.ppt

《数据结构及应用算法教程（修订版） 第4章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容4.1栈4.2栈的应用举例4.3队列4.4队列的应用举例栈和队列是软件设计中最常用的两种数据结构,它们的逻辑结构与线性表相同,其特点是运算受到限制:栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称它们是运算受限制的线性表。4.1栈4.1.1栈的结构特点和操作1.定义栈是限定仅在表的一端(表尾)进行插入和删除操作的线性表。栈中允许插入和删除的一端叫栈顶top，表尾称为栈顶；栈中不允许插入和删除的一端叫栈底bottom，表头称为栈底；不含数据元素的空表称为空栈。栈的插入操作称为进栈或入栈，栈的删除操作称为出栈或退栈。每次入栈的元

2、素总放在原栈顶元素之上成为新的栈顶，而每次出栈的元素总是当前栈中的最新的元素，也就是最后进栈的元素。栈又称为先进后出或后进先出表。（FILO或LIFO）。2.栈的基本操作1）InitStack(&S)将S初始化为空栈2）DestroyStack(&S)将栈S销毁3）ClearStack(&S)将栈S置成空栈4）StackEmpty(S)若栈S为空栈返回TRUE否则返回FALSE5）StackFull(S)若栈S已满返回TRUE，否则返回FALSE6）StackLength(S)栈S存在则返回S的元素个数,即栈的长度7）GetTop(S,&e)栈S存在且

3、非空则返回S的栈顶元素8）Push(&S,e)栈S存在且不满则插入元素e为新的栈顶元素9）Pop(&S,&e)栈S存在且非空则删除S的栈顶元素并用e返回其值，GetTop(S,&e)与Pop(&S,&e)不同在于GetTop(S,&e)不改变栈顶的位置。a1a2an……a1a2ane……10）StackTraverse(S)栈S存在且非空则从栈底到栈顶依次输出栈S中的每个数据元素4.1.2栈的表示和实现栈的存储方式：顺序栈和链栈1.顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。通常用to

4、p=-1表示空栈。//---顺序栈的存储表示---a1a2anan-1……constSTACK_INIT_SIZE=100;constSTACKINCREMENT=10;typedefstruct{SElemType*elem;inttop;intstacksize;intincrement;}SqStack;1).初始化栈voidInitStack(SqStack&S,intmaxsize=STACK_INIT_SIZE,intincresize=STACKINCREMENT){S.elem=newSElemType[STACK_INIT_SIZE];

5、S.top=-1;S.stacksize=maxsize;S.increment=incresize;}//InitStack2).得到栈顶元素boolGetTop(SqStackS,SElemType&e){if(S.top==-1)returnfalse;e=S.elem[S.top];returntrue;}//GetTop3).让栈顶元素出栈boolPop(SqStack&S,SElemType&e){if(S.top==-1)returnfalse;e=S.elem[S.top];S.top--;returntrue;}//Pop4).入栈一个

6、元素voidPush(SqStack&S,SElemTypee){if(S.top==S.stacksize-1){S.stacksize=S.stacksize+STACKINCREMENT;SElemType*elem=newSElemType[S.stacksize];for(inti=0;i<=S.top;i++)elem[i]=S.elem[i];delete[]S.elem;S.elem=elem;}S.top++;S.elem[S.top]=e;}//Push5).输出栈中的元素voidStackTraverse(SqStackS){for

7、(inti=0;i<=S.top;i++)cout<

8、next;}LNode,*LinkList;typedefLinkListLin