数据结构-栈和队列.

3栈和队列信息学院暑期培训栈和队列•学习目标•掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。•熟练掌握循环队列和链队列的基本操作实现算法。•理解递归算法执行过程中栈的状态变化过程。•重点和难点•栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点是掌握这两种结构的特点，以便能在应用问题中正确使用。•知识点•顺序栈、链栈、循环队列、链队列栈和队列•栈和队列是在程序设计中被广泛使用的两种线性数据结构。•与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。•线性表允许在表内任一位置进行插入和删除；•栈只允许在表尾一端进行插入和删除；•队列只允许在表尾一端进行插入，在表头一端进行删除。3栈和队列栈在计算机的实现有多种方式：◆硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；◆软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。3.1栈1栈的概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。3.1.1栈的基本概念3.1.1栈的基本概念设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)栈的示意图•特点•先进后出（FILO）•后进先出（LIFO）a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的逻辑结构例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况1：栈的逻辑结构栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况2：还有其他情况吗？3.1.1栈的基本概念2栈的抽象数据类型定义ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}数据关系：R={ai-1,ai|ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、进栈、出栈、取栈顶元素等}ADTStack栈的抽象数据类型定义•ADTStack{•数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}•数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}•基本操作：•InitStack(&S)操作结果：构造一个空栈S。•DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。栈的抽象数据类型定义ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S中元素个数，即栈的长度。栈的抽象数据类型定义GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。栈的抽象数据类型定义StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack3.1.2栈的顺序存储表示栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。◆静态顺序栈实现简单，但不能根据需要增大栈的存储空间；◆动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。3.1.2.1栈的动态顺序存储表示采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。◆用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。◆用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。3.1.2.1栈的动态顺序存储表示◆结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;空栈bottomtop元素a进栈bottomtopa元素b，c进栈bottomtopabc3.1.2.1栈的动态顺序存储表示◆结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。图3-2(动态)堆栈变化示意图元素c退栈bottomtopabbottomtopabdef元素d，e，f进栈3.1.2.1栈的动态顺序存储表示基本操作的实现1栈的类型定义#defineSTACK_SIZE100/*栈初始向量大小*/#defineSTACKINCREMENT10/*存储空间分配增量*/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*栈不存在时值为NULL*/ElemType*top;/*栈顶指针*/intstacksize;/*当前已分配空间，以元素为单位*/}SqStack;3.1.2.1栈的动态顺序存储表示2栈的初始化StatusInit_Stack(void){SqStackS;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));if(!S.bottom)returnERROR;S.top=S.bottom;/*栈空时栈顶和栈底指针相同*/S.stacksize=STACK_SIZE;returnOK;}3.1.2.1栈的动态顺序存储表示3压栈(元素进栈)Statuspush(SqStackS,ElemTypee){if(S.top-S.bottom=S.stacksize-1){S.bottom=(ElemType*)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));/*栈满，追加存储空间*/if(!S.bottom)returnERROR;S.top=S.bottom+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;/*栈顶指针加1，e成为新的栈顶*/returnOK;}3.1.2.1栈的动态顺序存储表示4弹栈(元素出栈)Statuspop(SqStackS,ElemType*e)/*弹出栈顶元素*/{if(S.top==S.bottom)returnERROR;/*栈空，返回失败标志*/S.top--;e=*S.top;returnOK;}3.1.2.2栈的静态顺序存储表示采用静态一维数组来存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，◆栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。◆用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。◆结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。3.1.2.2栈的静态顺序存储表示◆结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。图3-3静态堆栈变化示意图空栈bottomtopTop=11个元素进栈bottomtopaTop=33个元素进栈bottomtopabcTop=4栈满bottomtopabedTop=2元素c进栈bottomtopab3.1.2.2栈的静态顺序存储表示基本操作的实现1栈的类型定义#defineMAX_STACK_SIZE100/*栈向量大小*/#typedefintElemType;typedefstructsqstack{ElemTypestack_array[MAX_STACK_SIZE];inttop;}SqStack;3.1.2.2栈的静态顺序存储表示2栈的初始化SqStackInit_Stack(void){SqStackS;S.bottom=S.top=0;return(S);}3.1.2.2栈的静态顺序存储表示3压栈(元素进栈)Statuspush(SqStackS,ElemTypee)/*使数据元素e进栈成为新的栈顶*/{if(S.top==MAX_STACK_SIZE-1)returnERROR;/*栈满，返回错误标志*/S.top++;/*栈顶指针加1*/S.stack_array[S.top]=e;/*e成为新的栈顶*/returnOK;/*压栈成功*/}3.1.2.2栈的静态顺序存储表示4弹栈(元素出栈)Statuspop(SqStackS,ElemType*e)/*弹出栈顶元素*/{if(S.top==0)returnERROR;/*栈空，返回错误标志*/*e=S.stack_array[S.top];S.top--;returnOK;}3.1.2.2栈的静态顺序存储表示top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组大小为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空进栈：top加1出栈：top减13.1.2.2栈的静态顺序存储表示当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。当栈空时做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。3.1.3栈的链式存储表示1栈的链式表示栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。空栈top⋀非空栈topa4a3a1⋀a2图3-4链栈存储形式链栈的结点类型说明如下：typedefstructStack_Node{ElemTypedata;structStack_Node*next;}Stack_Node;3.1.3栈的链式存储表示2链栈基本操作的实现(1)栈的初始化Stack_Node*Init_Link_Stack