第3章堆栈和队列

《第3章堆栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。栈在计算机的实现有多种方式：◆硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；◆软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。3.1栈3.1.1栈的基本概念1栈的概念栈(Stack)：是限制在表的一端进行插入和删除操

2、作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示

3、意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)2栈的抽象数据类型定义ADTStack{数据对象：D={ai

4、ai∈ElemSet,i=1,2,…,n，n≥0}数据关系：R={

5、ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、进栈、出栈、取栈顶元素等}ADTStack栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。◆静态顺序栈实现简单，但不能根据需要增大栈的存储

6、空间；◆动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。3.1.2栈的顺序存储表示采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。◆用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。◆用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。◆元素进栈(压栈)：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;3.1.2.1栈

7、的动态顺序存储表示◆元素出栈(弹栈)：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。图3-2是一个动态栈的变化示意图。图3-2(动态)堆栈变化示意图空栈bottomtop元素a进栈bottomtopa元素b，c进栈bottomtopabc元素c退栈bottomtopabbottomtopabdef元素d，e，f进栈基本操作的实现1栈的类型定义#defineSTACK_SIZE100/*栈初始向量大小*/#defineSTACKINCREMENT10/*存储空间分配增量*

8、/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*栈不存在时值为NULL*/ElemType*top;/*栈顶指针*/intstacksize;/*当前已分配空间，以元素为单位*/}SqStack;2栈的初始化StatusInit_Stack(void){SqStackS;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));if(!S.bottom)returnERR

9、OR;S.top=S.bottom;/*栈空时栈顶和栈底指针相同*/S.stacksize=STACK_SIZE;returnOK;}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)returnE

10、RROR;S.top=S.bottom+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;/*栈顶指针加1，e成为新的栈顶*/returnOK;}4弹栈(元素出栈)Statuspop(SqStackS,ElemType*e)/*弹出栈顶元素*/{if(S.top==S.bottom)returnERROR;/*栈空，返回失败标志*/S.top--;e=*S.top;returnOK;}采用静态一维数组来存储栈。栈底固定不变的，而栈