资源描述：
《SUN数据结构第3章栈和队列(第8-10讲).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、绪言从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。13.1栈栈，也叫堆栈，是最常用也是最重要的数据结构之一。栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。举例：栈操作的特点：后进先出，先进后出。因此，栈称为后进先出表（LIFO,
2、LastInFirstOut）。2anan-1a2a1……栈顶入栈出栈进栈出栈示意图栈底3初始化栈InitStack(S)设置一个空栈S。压栈Push(S,x)将元素x插入栈S中，使x成为栈S的栈顶元素。出栈Pop(S,x)当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素取栈顶元素GetTop(S,x)若栈S不空，则由x返回栈顶元素。判栈空Empty(S)若栈S为空栈，结果为1，否则结果为0。2．栈的基本运算在栈顶插入元素在栈顶删除元素43.1.2栈的顺序存储结构和基本运算的实现栈有两种存储
3、表示方法:顺序存储和链式存储（1）栈的顺序存储结构采用顺序存储结构的栈简称为顺序栈。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设整型变量top指示栈顶元素在顺序栈中的位置。5顺序栈数据类型的C语言描述如下：top:栈顶指针。取值范围为0～MaxSize-1。top==-1表示栈空，top==MaxSize-1表示栈满。#defineMaxSize100typedefcharSElemType;typedefstruct{SElemTypedata[MaxSize];int
4、top;}STACK;6顺序栈的几种状态（最大长度MaxSize为4）①栈空；②压栈；③栈满；④出栈。7栈的基本运算在顺序存储结构的实现初始化栈InitStack(S)intInitStack(STACK*S){S->top=-1;return1;}8intPush(STACK*S,SElemTypex){if(S->top==MaxSize-1){printf("Stackisfull!");exit(1);}S->top++;S->data[S->top]=x;return1;}压栈前应
5、先判断是否栈满且注意压栈顺序：（1）top指针加1；（2）元素压入压栈Push(S,x)9intEmpty(STACK*S){return(S->top==-1?1:0);}判栈空EmptyStack(S)10intPop(STACK*S,SElemType*x){if(EmptyStack(S)){printf("Stackisfree!");exit(1);}*x=S->data[S->top];—记住要删除的元素值S->top--;return1;}传址自定义函数一次只能有一个返回值出
6、栈Pop(S,x)11SElemTypeGetTop(STACK*S){SElemTypex;if(Empty(S)){printf("Stackisfree!");return0;}x=S->data[S->top];returnx；}取栈顶元素GetTopStack(S,x)exit(1);12课堂练习1.栈和队列都是（）。A.顺序存储的线性结构B.限制存取点的线性结构C.链接存储的线性结构D.限制存取点的非线性结构B132.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top
7、作为栈顶指针，则当出栈时，top变化为。A.top不变Ｂ.top＝-nC.top＝top-1D.top=top+1C课堂练习14C课堂练习3.若进栈序列为1,2,3,4,进栈过程中可以出栈，则不可能是一个出栈序列。A.3,4,2,1B.2,4,3,1C.1,4,2,3D.3,2,1,44、假设以S和X分别表示进栈和退栈操作，则对输入序列1,2,3,4,5进行一系列栈操作SXSSXSSXXX之后，得到的输出序列为。13542试找出所有可能的出栈序列共14种15课堂练习5.若已知一个栈的入栈序列是1
8、,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若p1=n，则pi为()。A.iB.n-i+1C.n-iD.不确定B16课堂练习6.判定一个栈ST（MaxSize=n）为空的条件是()。Ａ．ST->top!=-1Ｂ．ST->top==-1Ｃ．ST->top!=nＤ．ST->top==nB17栈的链式存储结构和基本运算的实现（1）栈的链式存储结构通常将采用链式存储的栈称为链栈。链栈结构示意图：top栈顶指针，惟一的确定一个链栈。链栈通常带有一个表头结点，所以top->next才指示栈顶元
