资源描述：
《数据结构与算法之栈与队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、01绪论02线性表03栈和队列04串和数组06图和广义表05二叉树和树数据结构及其应用算法数据结构与算法之栈和队列栈和队列栈的定义队列的定义栈是限定仅能在表尾一端进行插入、删除操作的线性表队列是限定仅能在表头进行删除，表尾进行插入的线性表。了解更多了解更多栈的定义（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。栈的定义出栈进栈栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元
2、素为栈顶元素最后一个出栈的元素为栈底元素栈的示意图栈顶栈底ana2a1队列的定义（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。队列的定义a1a2a3an队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素出队列栈的基本操作1）初始化操作InitStack(&S)功能：构造一个空栈S。2）销毁栈操作DestroyStack(&S)功能
3、：销毁一个已存在的栈。3）置空栈操作ClearStack(&S)功能：将栈S置为空栈。4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回。5）进栈操作Push(&S,e)功能：元素e进栈。6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回。7）判空操作StackEmpty(S)功能：若栈S为空，则返回True，否则，栈不空返回False。栈的顺序存储和实现1一、栈的顺序存储结构#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT1
4、0//空间的分配增量typedefstruct{ElemType*base;//栈空间基址ElemType*top;//栈顶指针intstacksize;//当前分配的栈空间大小}SqStack;栈的顺序存储和实现1一、栈的顺序存储结构顺序栈的图示S.stacksizeS.topS.base10099nn-1n-210a2a1约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等如何实现？？anan-1栈的顺序存储和实现1一、栈的顺序存储结构topbasebasetopABCDE空栈bas
5、etopAA进栈BCDE进栈basetopABEDC出栈称为：栈满空栈top=base栈满top-base=stacksize(无可分配空间)不可扩充栈的操作212340ABCDEtop=012340栈空栈顶指针top，指向实际栈顶后的空位置，初值为basetop进栈A栈满BCDE设数组大小为Mtop=M，栈满，此时入栈，则上溢(overflow)toptoptoptoptoptoptoptoptoptop栈空top==base，栈空，此时出栈，则下溢(underflow)top12340出栈可扩充栈的操作212340ABCD
6、E栈顶指针top，指向实际栈顶后的下一个位置，初值为top=basetop进栈A出栈栈当前空间不足，需扩充BCDE设栈的初始分配量为Stacksize=STACK_INIT_SIZE。若top==Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充STACK_INCREMENT；若无可利用的存储空间，则上溢(overflow)。toptoptoptoptoptoptoptoptoptop栈空若top==base,栈空，此时出栈，则下溢(underflow)base栈空topbasebasetop1234012340栈的
7、基本操作算法1Chapter栈的基本操作算法1）初始化操作InitStack(SqStack&S)参数：S是存放栈的结构变量功能：建一个空栈SS.stacksizeS.topS.base10099nn-1n-210StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//为顺序栈动态分配存储空间if(!S.base)exit(OVERFLOW);//分配失败S.top=S.base;S.sta
8、cksize=STACK_INIT_SIZE;returnOK;}//InitStack栈的基本操作算法2）销毁栈操作DestroyStack(SqStack&S)功能：销毁一个已存在的栈99nn-1n-210anan-1a2a1S.stacksizeS.topS.base1
