《《数据结构严蔚敏》PPT课件》由会员分享，可在线阅读，更多相关《《数据结构严蔚敏》PPT课件（708页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 栈和队列栈和队列 栈和队列是两种应用非常广泛的数据结构栈和队列是两种应用非常广泛的数据结构，它们都，它们都来自线性表数据结构，来自线性表数据结构，都是都是“操作受限操作受限”的线性表的线性表。栈在计算机的实现有多种方式：栈在计算机的实现有多种方式： 硬堆栈硬堆栈：利用：利用CPU中的某些寄存器组或类似的硬中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；但速度很快； 软堆栈软堆栈：这类堆栈主要在内存中实现。堆栈容量：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有可以达到很大。在实
2、现方式上，又有动态方式动态方式和和静态静态方式方式两种。两种。 本章将讨论栈和队列的基本概念本章将讨论栈和队列的基本概念、存储结构存储结构、基本基本操作以及这些操作的具体实现操作以及这些操作的具体实现。 栈栈 栈的基本概念栈的基本概念1 栈的概念栈的概念 栈栈(Stack)：是限制在表的一端进行插入和删除操是限制在表的一端进行插入和删除操作的线性表。又称为后进先出作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出或先进后出FILO (First In Last Out)线性线性表。表。 栈顶栈顶(Top)：允许进行插入、删除操作的一端，又允许进行插入、删除操作
3、的一端，又称为表尾。用栈顶指针称为表尾。用栈顶指针(top)来指示栈顶元素来指示栈顶元素。 栈底栈底(Bottom)：是固定端，又称为表头。是固定端，又称为表头。 空栈空栈：当表中没有元素时称为空栈。当表中没有元素时称为空栈。 设栈设栈S=(a1，a2，an)，则，则a1称称为栈底元素，为栈底元素，an为栈顶元素，如图为栈顶元素，如图3-1所示。所示。 栈中元素按栈中元素按a1，a2，an的次序的次序进栈，退栈的第一个元素应为栈顶元进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则素。即栈的修改是按后进先出的原则进行的。进行的。图图3-1 顺序顺序栈示意图栈示意图a1a2aian
4、bottomtop进栈（进栈（push）出栈出栈(pop)2 栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack数据对象：数据对象：D = ai|aiElemSet, i=1,2,n，n0 数据关系：数据关系：R =|ai-1，aiD, i=2,3,n 基本操作：初始化、进栈、出栈、取栈顶元素等基本操作：初始化、进栈、出栈、取栈顶元素等 ADT Stack 栈的顺序存储结构简称为顺序栈，和线性表相类似，栈的顺序存储结构简称为顺序栈，和线性表相类似，用用一维数组一维数组来来存储栈存储栈。根据数组是否可以根据需要增大，。根据数组是否可以根据需要增大，又可分为又可分为静态顺序栈静态顺序栈和和
5、动态顺序栈动态顺序栈。 静态顺序栈静态顺序栈实现简单，但不能根据需要增大栈的实现简单，但不能根据需要增大栈的存储空间；存储空间； 动态顺序栈动态顺序栈可以根据需要增大栈的存储空间，但可以根据需要增大栈的存储空间，但实现稍为复杂。实现稍为复杂。 栈的顺序存储表示栈的顺序存储表示 采用采用动态动态一维数组一维数组来来存储栈存储栈。所谓动态，指的是栈。所谓动态，指的是栈的大小可以根据需要增加。的大小可以根据需要增加。 用用bottom表示栈底指针，栈底固定不变的；栈顶表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用则随着进栈和退栈操作而变化。用top( (称为栈顶指针称为栈顶指针)
6、)指示当前栈顶位置。指示当前栈顶位置。 用用top=bottom作为栈空的标记作为栈空的标记，每次，每次top指向栈顶指向栈顶数组中的下一个存储位置数组中的下一个存储位置。 结点进栈结点进栈：首先将数据元素保存到栈顶首先将数据元素保存到栈顶(top所指所指的当前位置的当前位置)，然后执行，然后执行top加加1，使，使top指向栈顶的下指向栈顶的下一个存储位置一个存储位置; 栈的动态顺序存储表示栈的动态顺序存储表示 结点出栈结点出栈：首先执行首先执行top减减1，使，使top指向栈顶元指向栈顶元素的存储位置，然后将栈顶元素取出素的存储位置，然后将栈顶元素取出。 图图3-2是一个动态栈的变化示意图
7、是一个动态栈的变化示意图。图图3-2 (动态动态)堆栈变化示意图堆栈变化示意图空栈空栈bottomtop元素元素a进栈进栈bottomtopa元素元素b，c进栈进栈bottomtopabc元素元素c退栈退栈bottomtopabbottomtopabdef元素元素d，e，f进栈进栈基本操作的实现基本操作的实现1 栈的类型定义栈的类型定义#define STACK_SIZE 100 /* 栈初始向量大小栈初始向量大小 */#define STACKINCREMENT 10 /* 存储空间分配增量存储空间分配增量 */#typedef int ElemType ;typedef struct sq
8、stack ElemType *bottom; /* 栈不存在时值为栈不存在时值为NULL */ElemType *top; /* 栈顶指针栈顶指针 */int stacksize ; /* 当前已分配空间，以元素为单位当前已分配空间，以元素为单位 */SqStack ;2 栈的初始化栈的初始化Status Init_Stack(void) SqStack S ;=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType);if (! ) return ERROR;= ; /* 栈空时栈顶和栈底指针相同栈空时栈顶和栈底指针相同 */S. stacksize=
9、STACK_SIZE; return OK ;3 压栈压栈(元素进栈元素进栈)Status push(SqStack S , ElemType e) if (=S. stacksize-1) =(ElemType *)realloc(S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType); /* 栈满，追加存储空间栈满，追加存储空间 */if (! ) return ERROR; =S.bottom+S. stacksize ;S. stacksize+=STACKINCREMENT ; *=e; + ; /* /* 栈顶指针加栈顶指针加1，e成为新的栈
10、顶成为新的栈顶 * */ /return OK;4 弹栈弹栈( (元素元素出栈出栈) )Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素弹出栈顶元素*/ if ( = ) return ERROR ; /* 栈空，返回失败标志栈空，返回失败标志 */- ; e=*S. top ; return OK ; 采用采用静态静态一维数组一维数组来来存储栈存储栈。 栈底固定不变的，而栈顶则随着进栈和退栈操作变栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，化的， 栈底固定不变的；栈顶则随着进栈和退栈操作而栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整
11、型变量变化，用一个整型变量top( (称为栈顶指针称为栈顶指针) )来指示当前来指示当前栈顶位置。栈顶位置。 用用top=0表示栈空的初始状态表示栈空的初始状态，每次，每次top指向栈顶指向栈顶在数组中的存储位置在数组中的存储位置。 结点进栈结点进栈：首先执行首先执行top加加1，使，使top指向新的栈指向新的栈顶位置顶位置，然后将数据元素保存到栈顶然后将数据元素保存到栈顶(top所指的当前所指的当前位置位置)。 栈的静态顺序存储表示栈的静态顺序存储表示 结点出栈结点出栈：首先首先把把top指向的栈顶元素取出指向的栈顶元素取出，然然后执行后执行top减减1，使，使top指向新的栈顶位置指向新的
12、栈顶位置。 若栈的数组有若栈的数组有Maxsize个元素个元素，则，则top=Maxsize-1时时栈满栈满。图。图3-3是一个大小为是一个大小为5的栈的变化示意图的栈的变化示意图。图图3-3 静态静态堆栈变化示意图堆栈变化示意图空栈空栈bottomtopTop=11个元素进栈个元素进栈bottomtopaTop=33个元素进栈个元素进栈bottomtopabcTop=4栈满栈满bottomtopabedTop=2元素元素c进栈进栈bottomtopab基本操作的实现基本操作的实现1 栈的类型定义栈的类型定义# define MAX_STACK_SIZE 100 /* 栈向量大小栈向量大小 *
13、/# typedef int ElemType ;typedef struct sqstack ElemType stack_arrayMAX_STACK_SIZE ;int top;SqStack ;2 栈的初始化栈的初始化SqStack Init_Stack(void) SqStack S ;=0 ; return(S) ;3 压栈压栈(元素进栈元素进栈)Status push(SqStack S , ElemType e) /* /* 使数据元素使数据元素e进栈成为新的栈顶进栈成为新的栈顶 * */ / if (S.top=MAX_STACK_SIZE-1) return ERROR;
14、/* 栈满，返回错误标志栈满，返回错误标志 */+ ; /* /* 栈顶指针加栈顶指针加1 */*/=e ; /* /* e成为新的栈顶成为新的栈顶 * */ /return OK; /* 压栈成功压栈成功 */4 弹栈弹栈( (元素元素出栈出栈) )Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素弹出栈顶元素*/ if ( S.top=0 )return ERROR ; /* 栈空，返回错误标志栈空，返回错误标志 */*e= ; - ; return OK ; 当栈满时做进栈运算必定产生空间溢出，简称当栈满时做进栈运算必定产生空间溢出，简称“上上溢溢
15、”。上溢是一种出错状态，应设法避免。上溢是一种出错状态，应设法避免。 当栈空时做退栈运算也将产生溢出，简称当栈空时做退栈运算也将产生溢出，简称“下溢下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。态都是空栈，所以下溢常用来作为控制转移的条件。1 栈的链式表示栈的链式表示 栈的栈的链式存储结构链式存储结构称为链栈，是运算受限的单链表。称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指
16、针没有必要像单链表那样附加头结点，栈顶指针top就是就是链表的头指针。图链表的头指针。图3-4是栈的链式存储表示形式是栈的链式存储表示形式。 栈的链式存储表示栈的链式存储表示空栈空栈top 非空栈非空栈top a4 a3 a1 a2图图图图3-4 3-4 链链链链栈存储形式栈存储形式链栈的链栈的结点类型说明如下：结点类型说明如下：typedef struct Stack_Node ElemType data ;struct Stack_Node *next ; Stack_Node ;2 链栈基本操作的实现链栈基本操作的实现(1) 栈的初始化栈的初始化Stack_Node *Init_Link_Stack(void) Stack_Node *top ;top=(Stack_Node *)malloc(sizeof(Stack_Node ) ;top-next=NULL ; return(top) ;(2) 压栈压栈(元素进栈元素进栈)Status push(Stack_Node *top , ElemType e) Stack_Node *p ;p=(Stack_Node *)mall
