资源描述：
《数据结构3资料讲课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构3资料第三章栈和队列学习要点理解栈的逻辑结构定义及特点掌握栈的顺序存储结构的描述重点掌握顺序栈上的基本运算掌握栈的链式存储结构掌握描述链栈结构的方法掌握链栈上的基本运算了解栈的广泛应用理解队列的逻辑结构定义及特点掌握顺序队列存储结构及其描述方法掌握顺序队列上的基本运算第三章栈和队列理解栈和队列中“上溢”和“下溢”的概念理解顺序队列出现“假上溢”的原因及其解决方案掌握循环顺序队列的结构重点掌握循环队列的基本运算理解循环顺序队列消除“假上溢”的方法理解队列“满”和“空”的含义掌握顺序队列和循环队列判断“满”和“空”的条件掌握队列的链式存储结
2、构及其描述方法掌握队列的链队列的基本运算了解队列的广泛应用第三章栈和队列通常称栈和队列是限定插入和删除只能在表的“端点”进行的线性表线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈抽象数据类型栈的定义栈（stack）是限定在表尾一端进行插入或删除操作的线性表。在栈中，允许插入和删除操作的一端称为栈顶（top），而另一端称为栈底（base）。不含元素的栈称为空栈在栈的运算中
3、，栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。根据栈的定义，每一次进栈的元素都在原栈顶元素之上，并成为新的栈顶元素；每一次出栈的元素总是当前的栈顶元素，因此最后进栈的元素总是最先出栈，所以栈也称为后进先出（LastInFirstOut）线性表，简称为LIFO表。或先进后出FILO表,（FirstInLastOut）3.1栈ADTStack{数据对象：D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底基本操作：}
6、ADTStack3.1栈基本操作InitStack(&S) 操作结果：构造一个空栈S。DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则FALSEStackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度3.1栈GetTop(S,&e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空
7、栈3.1栈Push(&S,e)初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。ea1a2an……3.1栈Pop(&S,&e)初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值a1a2anan-1……3.1栈StackTravers(S,visit())初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对栈S的每个元素调用函数visit()。一旦visit()失败，则操作失败3.1栈栈的表示和实现顺序栈类似于线性表的顺序映象实现，指向表尾的指针top可以作为栈顶指针//-----栈的顺序存储表示-----#
8、defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;ElemType*top;//指向栈顶元素的后一个位置intstacksize;}SqStack;//顺序栈3.1栈StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;
9、//空栈的标志S.stacksize=STACK_INIT_SIZE;returnOK;}3.1栈StatusGetTop(SqStackS,SElemType&e){//若栈不空，则用e返回S的栈顶元素，并返回//OK；否则返回ERRORif(S.top>S.base){e=*(S.top-1);returnOK;}elsereturnERROR;}3.1栈StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){//栈满,追加存储空间S.base=(ElemType*)rea
10、lloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(
