数据结构 第 3 章 栈和队列

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

1、栈和队列1、栈和队列的定义及特点；2、栈的顺序存储表示；3、队列的顺序存储表示；队列的链接存储表示；4、栈和队列的应用举例。教学内容限定仅在表尾进行插入或删除操作。3.1栈3.1.1抽象数据类型栈的定义栈的定义a1a2an-1an…栈顶(top)栈底(bottom)出栈进栈栈底元素栈顶元素栈(stack)：线性表后进先出(LIFO结构)。栈的抽象数据类型的定义ADTStack{数据对象：D＝{ai

2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

3、ai-1

4、,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件

5、：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//数组指针，指示线性表的基地址intlength;//

6、当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;3.1.2栈的表示和实现顺序栈顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。SelemType*base;//栈底指针，它始终指向栈底的位置。SelemType*top;//栈顶指针。intstacksize;//当前分配的栈可使用的最大存储容量。Sqstack;topbaseAtopBtopCtopDtopEtop

7、注：base的值为NULL，表明栈结构不存在。空栈若再进行元素“出栈”操作，将产生“下溢”。top栈满若再进行元素“入栈”操作，将产生“上溢”。#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT10//栈存储空间的分配增量栈的基本操作在顺序栈中的实现#definemaxs9;main(){intstack[maxs];inttop=0;while(top

8、nte;e=stack[top-1];while(top>0)e=stack[top-1];top-=1;}InitStackPushPoptop12toptoptop2topGetTop21▲StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE

9、;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINcrement)*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.t

10、op++=e;returnOK;}//PushStatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}//GetTopStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop3.2栈的应用举例3.2.1数制转换十进制数N和其他d进制数M的转换是计算