资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 栈和队列,主讲:戚玉涛,主要内容,3.1,栈,3.2,栈的应用举例,3.3,栈与递归的实现,3.4,队列,引言,本章我们将学习两种重要而特殊的线性数据结构:,栈和队列,从逻辑结构角度看:,它们是线性表,从运算角度看:,它们的基本运算是线性表运算的子集,是操作受限的线性表,引言,通常称,栈和队列是限定,插入和删除只能,在表的,“,端点,”,进行的线性表。,线性表 栈 队列,Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x),1in+1,Delete(L,i,)Delete(S,n,)Delete(Q,1,),1in,栈和队列是两种常用的数据类型,3.1,栈,栈的定义,限定仅在表尾进行插入或删除操作的线性表。,S=(a,1,a,2,a,n,),栈底,(Bottom),:表头端称为栈底。,栈顶,(Top),:表尾端称为栈顶。,进栈,(,入栈,),:栈的插入操作。,出栈,(,退栈,),:删除操作。,空栈,:不含元素的空表。,栈底元素,:,a,1,;,栈顶元素,:,a,n,栈的抽象数据类型定义,ADT Stack,数据对象:,D,a,i,|,a,i,ElemSet,i=1,2,.,n,n0,数据关系:,R1,|a,i-1,a,i,D,i=2,.,n,约定,a,n,端为栈顶,,a,1,端为栈底。,ADT Stack,基本操作:,栈的特点,“很窄的死胡同”,后进先出,(Last In First Out),,简称,LIFO,结构。,栈又称后进先出线性表。,栈的基本运算,初始化,InitStack(&S,),。构造一个空栈,入栈,Push(&S,e),。栈,S,已经存在,插入,e,为新的栈顶元素,出栈,Pop(&S,&e),。,栈,S,存在且非空,删除栈顶元素,,e,返回,读栈顶元素,GetTop(S,&e),。,栈,S,存在且非空,用,e,返回栈顶元素,判栈空,StackEmpty(S,),。栈,S,存在,若为空栈,返回真,否则假,栈的表示和实现,线性表,顺序表,链表,单链表,双链表,循环链表,双向,单向,栈,顺序栈,链栈,顺序栈,顺序栈:栈的顺序存储结构,是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。,设置指针,top,指向栈顶元素在顺序栈中的位置,/-,栈的顺序存储表示,-,#define,STACK_INIT_SIZE 100;,#define,STACKINCREMENT 10;,typedef,struct,SElemType,*,base;,SElemType,*,top;,int,stacksize,;,SqStack,;,顺序栈的类型定义,typedef,struct,SElemType,*base;/,栈底指针,SElemType,*top;/,栈顶指针,int,stacksize,;/,栈已分配的空间大小,SqStack,;,/,动态分配,typedef,struct,SElemType,dataMAXSIZE,;,int,top;,SqStack,;,/,静态分配,顺序栈的动态分配和静态分配,SqStack,S;,栈结构不存在,S.base,=NULL;,空栈,S.base,=,S.top,;,栈满,S.top,S.base,=,S.stacksize,;,空栈,top=0;,栈满,top=MAXSIZE;,空栈,A,B,C,base,top,栈中有三个元素,A,B,C,base,top,D,E,满栈,top=base,顺序栈中的进栈和出栈,栈仅在表的一端进行操作;,top,指针始终指向栈顶元素的,下一位置,。,例,在栈中插入元素,A,和,B,top=base,初始,A,base,top,=,top,+1,插入,A,插入,A,插入,A,插入,B,B,top,=,top,+1,例,删除栈顶元素,B,和,A,删除,B,base,A,B,top,top,=,top,-,1,插入,A,删除,A,top=base,e=B,e=A,插入,A,删除,C,ERROR,顺序栈,初始化栈:,Status,InitStack,(,SqStack,&,S),/,构造一个空栈,S,S.base=(,ElemType,*),malloc,(STACK_INIT_SIZE,*,sizeof,(ElemType,);,if,(!,S.base),exit,(OVERFLOW);,/,存储分配失败,S.top=S.base,;,S.stacksize,=STACK_INIT_SIZE;,return,OK;,入栈操作,Status,Push(,SqStack,&S,SElemType,e),if,(S.top-S.base=,S.stacksize,),/,栈满,追加存储空间,S.base=(,ElemType,*),realloc,(S.base,(,S.stacksize,+STACKINCREMENT)*,sizeof,(,ElemType,);,if,(!S.base)exit(OVERFLOW);,/,存储分配失败,S.top=S.base+,S.stacksize,;,S.stacksize,+=STACKINCREMENT;,*S.top+=e;,return,OK;,a,3,出栈操作,Status,Pop(,SqStack,&S,SElemType,&e),/,若栈不空,则删除,S,的栈顶元素,,/,用,e,返回其值,并返回,OK,;,/,否则返回,ERROR,if,(S.top=S.base),return,ERROR;,e=*-S.top;,return,OK;,读栈顶元素,GetTop(SqStack,S,SElemType&e,),if,(,S.top,=,S.base,),return ERROR;,e=*(,S.top,1);,return,OK;,链栈,链栈:,栈的链式表示,优点:,没有容量限制,在内存允许的范围内不会出现溢出,typedef,struct,STNode,SElemType,data;,struct,STNode,*next;,STNode,*,LinkStack,;,初始化,InitStack,(,LinkStack,&S),S=NULL;,return,OK;,读栈顶元素,GetTop(LinkStack,S,SElemType&e,),if,(S=NULL),return,ERROR;,e=S-data;,return,OK;,入栈,Push(,LinkStack,&S,SElemType,e),p=(,LinkStack,),malloc,(,sizeof,(,STNode,);,if,(!p,),exit(OVERFLOW,);,p-data=e;,p-next=S;,S=p;,return,OK;,出栈,Pop(LinkStack,&S,SElemType,&e),if,(S=NULL),return,ERROR;,e=S-data;,p=S;,S=S-next;,free(p,);,return,OK;,栈总结,栈是一种具有线性结构的数据结构,是操作受限的线性表;,栈的特点是后进先出,只能在栈顶进行插入和删除操作,分别称为入栈和出栈;,顺序栈中,栈空标志:,S.top,=,S.base,;,栈满标志:,S.top,S.base,=,S.stacksize,;,链栈中,不设头结点,头指针就是栈顶指针,栈空,S=NULL,。,练习:,1.,设一个栈的输入序列为,A,B,C,D,则借助一个栈所得到的输出序列不可能是,。,(A)A,B,C,D(B)D,C,B,A,(C)A,C,D,B(D)D,A,B,C,答,:,可以简单地推算,得容易得出,D,A,B,C,是不可能的,因为,D,先出来,说明,A,B,C,D,均在栈中,按照入栈顺序,在栈中顺序应为,D,C,B,A,出栈的顺序只能是,D,C,B,A,。,所以本题答案为,D,。,练习:,2.,已知栈的输入序列为,1,2,3,n,。输出序列为,a,1,a,2,a,n,,若,a,1,=n,,问,a,i,=?,a,i,=n-i+1,3.I,表示入栈,,O,表示出栈,若元素入栈顺序为,1234,,为了得到,1342,的出栈顺序,相应的,I,和,O,的操作串是什么?,I,1,O,1,I,2,I,3,O,3,I,4,O,4,O,2,4.,设,n,个元素进栈序列是,1,2,3,n,其输出序列是,p,1,p,2,p,n,若,p,1,=3,则,p,2,的值,。,(A),一定是,2(B),一定是,1,(C),不可能是,1 (D),以上都不对,答,:,当,p,1,=3,时,说明,1,2,3,先进栈,立即出栈,3,然后可能出栈,即为,2,也可能,4,或后面的元素进栈,再出栈。因此,p,2,可能是,2,也可能是,4,n,但一定不能是,1,。所以本题答案为,C,。,双栈共享一个栈空间,typedef,struct,SElemtype,*base2;,SElemtype,*top2;,int,stacksize,;,DSqStack,;/,双向栈类型,作业:,3.3,3.4,
展开阅读全文