数据结构课件-栈和队列

第三章栈和队列本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端进行。只能在一端进行的-----栈分别在两端进行的-----队列•重点本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。•知识点顺序栈、链栈、循环队列、链队列１.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？２.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？栈和队列是在程序设计中被广泛使用的两种线性数据结构．栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。插入删除线性表：Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)栈：Insert(L,n+1,x)Delete(L,n)队列：Insert(L,n+1,x)Delete(L,1)第三章栈和队列3.1栈1、栈（stack)：是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。栈顶（top)：插入、删除的一端；栈底（bottom)：固定不动的一端；入栈（push)：又称压入，即插入一个元素；出栈（pop)：又称弹出，即删除一个元素；一、抽象数据类型栈的定义2、说明：设（a1,a2,a3,…,an）是一个栈（a1,a2,...,ai-1,ai,ai+1,…,an）栈底栈顶进栈出栈1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素;2）在表尾插入元素的操作称进栈操作，在表头删除元素的操作称为出栈操作;3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶,第一个出栈的元素为栈顶元素；栈的示意图栈特点：由于限制了插入删除只能在一端进行，那么元素的操作顺序有“先进后出”或“后进先出”的特点(LastInFirstout-LIFOFirstInLastout---FILO)第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素课堂练习假设有A，B,C,D四个元素；它们入栈次序为A一＞B一＞C一＞D出栈次序任意，请问不可能得到下面哪些出栈序列？(1)ABCD(2)DBCA(3)CDBA(4)CBAD(5)ACBD(6)DBAC(7)ADCB(8)CABD3、栈的基本操作1）初始化操作InitStack(&S)功能：构造一个空栈S；2）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈;3）置空栈操作ClearStack(&S)功能：将栈S置为空栈;4）判空栈操作StackEmpty(S)功能：若栈为空栈，返回TRUE，否则FALSE5）取长度操作StackLength(S)功能：返回栈S的元素个数6）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回;7）进栈操作Push(&S,e)功能：元素e进栈;8）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回;7）栈遍历StackTraverse(S)功能：从栈底到栈顶依次调用函数visit().4、栈的ADT描述栈的抽象数据类型定义为：ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶,a1端为栈底。基本操作：…….}ADTStack二栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间。顺序存储方式：同一般线性表的顺序存储结构完全相同。是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。实际是栈中元素的个数顺序栈类型的定义//结构定义：typedefstruct{ElemType*base;//存储空间基址inttop;//栈顶指针intstacksize;//允许的最大存储空间}Stack;栈顶指针总是指在栈顶元素的后面一个位置上top=0123450栈空top123450进栈Atop出栈栈满BCDEF设数组维数为stacksizetop=0,栈空，此时出栈，则下溢（underflow)top=stacksize,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptop特点：简单、方便，但易产生溢出。上溢（Overflow)栈已经满，又要压入元素；下溢（Underflow)栈已经空，还要弹出元素；注：上溢是一种错误，使问题的处理无法进行下去；而下溢一般认为是一种结束条件，即问题处理结束。#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT10//栈存储空间的分配增量typedefstruct{SElemType*base;//栈空间基址称为栈底指针，指向栈底位置SElemType*top//栈顶指针,约定栈顶指针指向栈顶元素的//下（后面）一个位置；intstacksize;//当前分配的栈空间大小//（以sizeof(SElemType)为单位）}SqStack;//SqStack:：结构类型名顺序栈的存储表示nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZE初始化操作图示顺序栈基本操作的算法1）初始化操作InitStack_Sq(SqStack&S)参数：S是存放栈的结构变量；功能：建一个空栈S；StatusInitStack_Sq(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//为顺序栈动态分配存储空间if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack_SqStatusDetroyStack_Sq(SqStack&S){If(!S.base)returnERROR;//若栈未建立（尚未分配栈空间）free(S.base);//回收栈空间S.base=S.top=null;S.stacksize=0;returnOK;}//DetroyStack_Sq2）销毁栈操作DestroyStack_Sq(SqStack&S)功能：销毁一个已存在的栈;S.top=nullS.stacksizeS.base=null0nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE销毁前销毁后销毁栈操作图示3）置空栈操作ClearStack_Sq(SqStack&S)功能：将栈S置为空栈算法StatusClearStack_Sq(SqStack&S){If(!S.base)returnERROR;//若栈未建立（尚未分//配栈空间）S.top=S.base;returnOK;}//ClearStack_Sqnn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEnn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a2a1置空栈操作图示S.base=S.top表明栈为空置空前置空后StatusGetTop_Sq(SqStackS,SelemType&e){//若栈不空，则用e返回S的栈顶元素，并返回//OK；否则返回ERRORif(S.top==S.base)returnERROR;//若栈为空e=*(S.top-1);returnOK;}//GetTop_Sq4）取栈顶元素操作GetTop_Sq(SqStackS,SElemType&e)功能：取栈顶元素，并用e返回;nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEean取栈顶元素操作图示5）进栈操作Push(SqStack&S,SElemTypee)功能：元素e进栈;进栈操作主要步骤：1）S是否已满，若栈满，重新分配存储空间；2）将元素e写入栈顶；3）修改栈顶指针，使栈顶指针指向栈顶元素的下（后面）一个位置；nn-1i-1i-20n+1nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEeanaiai-1a1anaiai-1a1S.topS.stacksizeS.baseSTACK_INIT_SIZEe进栈前e进栈后进栈操作图示StatusPush(SqStack&S,SElemTypee){//将元素e插入栈成为新的栈顶元素,要考虑上溢情况if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//元素e插入栈顶，修改栈顶指针returnOK;}//Push进栈操作算法：StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值并返回OK//否则返回ERRORif(S.top==S.base)returnERROR;//栈空，返回ERRORe=*--S.top;//删除栈顶元素，用e返回其值，并修//改栈顶指针returnOK;}//Pop6）出栈操作Pop(SqStack&S,SElemType&e)功能：栈顶元素退栈，并用e返回;S.topS.stacksizeS.basenn-1i-1i-20anaiai-1a1STACK_INIT_SIZE出栈操作前nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a1出栈操作后ane出栈操作图示链栈链栈即为栈的链式存储结构。链栈的结点结构和单链表中的结点结构相同。由于栈只在栈顶作插入和删除操作，因此链栈中不需要头结点，但是链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。•链栈中结点的定义：•链栈结构定义：typedefstructLNode{ElemTypedata;structLNode*next;}*SLink;typedefstruct{SLinktop;//栈顶指针intlength;//栈中元素个数}LStack;链栈的基本操作和顺序栈操作基本相同，只需修改两处：１．初始化时不需要maxsize的参数２．在进行入栈操作时不需要顾忌栈的空间是否已经被填满。voidInitStack(LStack&S){//构造一个空栈SS.top=NULL;//设栈顶指针的初值为空S.length=0;//空栈中元素个数为0}//InitStackvoidPush(LStack&S,ElemTypee){//在栈顶之上插入元素e为新的栈顶元素p=(LNode*)malloc(sizeof(LNode);//建新的结点if(!p)exit(1);//存储分配失败p-data=e;p-next=S.top;//链接到原来的栈顶S.top=p;//移动栈顶指针++S.length;//栈的长度增1}//Push