资源描述：
《数据结构课件(栈和队列).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第三章栈和队列9/16/2021第三章栈和队列3.1栈栈和队列也是线性表，只不过是操作受限的线性表。栈是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶，表头端称栈底。如图。an...a2a1栈底栈顶出栈进栈栈顶（TOP）--允许插入和删除的一端。栈底(bottom)--不允许插入和删除的一端。空栈--表中没有元素。进栈---最先插入的元素放在栈的底部。退栈---最后插入的元素最先退栈。所以栈又称为后进先出的线性表（LIFO表，LastInFirstOut）3.1栈3.1.1栈的类型定义A
2、DTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否
5、则FALSE。3.1栈3.1.1栈的类型定义StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。 }ADTStack3.1栈3.1.2栈的表示和实现----顺序表示#defineSTACK_INIT_SIZE10
6、0//栈内存的初始分配量，以sizeof(ElemType)为单位#defineSTACKINCREMENT10//栈内存的分配增量，以sizeof(ElemType)为单位typedefstruct{SElemType*base;//存储空间的基址，数据元素的数据类型约定为SElemTypeSElemType*top;//表示栈顶，如果top==base，表示空栈intstacksize;//当前分配的存储容量，以sizeof(ElemType)为单位}SqStack3210Top=base空栈T
7、opbaseA3210TOPA进栈base3210DCBAB、C、D依次进栈TOPbase3210BATOPD、C依次退栈base3210B、A退栈baseTOP3.1栈3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusInitStack(SqStack&S){//为栈S分配存储空间，并置S为空栈S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.to
8、p=S.base;//置栈S为空栈S.stacksize=STACK_INIT_SIZE;returnOK; }//InitStack3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusGetTop(SqStackS,SElemType&e){//若栈不空，则用e返回S的栈顶元素并返回OK，否则返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK; }//GetTop3.1.2栈的表示和实现----顺序表示顺序栈基本
9、操作的实现StatusPush(SqStack&S,SElemTypee)//将e插入栈S中并使之成为栈顶元素if(S.top-S.base>=S.stacksize) {//栈满，追加存储空间S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.stacksize+=STACKINCREMENT; }*S.top++=
10、e;returnOK; }//Push3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusPop(SqStack&S,SElemType&e){//若栈S不空，则删除S的栈顶元素，用e返回其值并返回OK，否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK; }//Pop3.1.2栈的表示和实现----顺序表示顺序栈基本操作的实现StatusDestroyStack(SqStack&
