中国科学技术大学：《数据结构》课程教学课件（PPT讲稿）第3章 栈和队列

第3章栈和队列3.1栈的基本概念3.2栈的表示与实现3.3栈的应用3.4队列的基本概念3.5队列的表示与实现3.6队列的应用3.7递归应用示例中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 1 中国科学技术大学 第3章 栈和队列 3.1栈的基本概念 3.2栈的表示与实现 3.3栈的应用 3.4队列的基本概念 3.5队列的表示与实现 3.6队列的应用 3.7递归应用示例

3.1栈的基本概念>定义：栈（Stack）是限定只能在表得一端进行插入和删除操作的线性表，又称限定性线性表结构>栈的结构特点和操作栈顶（Top）、栈底(Bottom)，先入后出(LIFO)>栈的ADT描述ADT Stack (StackEmpty (S)D={a;la;eElemSet,i=1,2,...n,n≥0)StackLength (S)R=[<ai-1,a>lai-1,a;eD,i=2,3...n)GetTop (S, &e)基本操作：Push (&S,e)InitStack (&S)Pop(&S,&e)DestroyStack(&S)StackTraverse(S)ClearStack(&S)EndADTStack2ypb@ustc.edu.cn中国科学技术大学

ypb@ustc.edu.cn 2 中国科学技术大学 3.1栈的基本概念 ➢ 定义：栈（Stack）是限定只能在表得一端进行插入和 删除操作的线性表，又称限定性线性表结构 ➢ 栈的结构特点和操作 栈顶(Top)、栈底(Bottom),先入后出(LIFO) ➢ 栈的ADT描述 ADT Stack｛ D={ai |aiElemSet,i=1,2,.n,n0} R={<ai-1 ,ai>|ai-1 ,aiD,i=2,3.n} 基本操作： InitStack（&S） DestroyStack(&S) ClearStack(&S) StackEmpty（S） StackLength（S） GetTop(S,&e) Push(&S, e) Pop(&S,&e) StackTraverse(S) }End ADT Stack

出栈ama2,a进栈a,a，ana,:a2a3中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 3 中国科学技术大学

3.2栈的表示和实现>顺序栈Const STACK INIT SIZE=-1000:Const STACKINCREMENT=10:Typedef struct*elem,SelemtypeInttop,an-ltop=n-1Intstacksize;Intincrement:SqStack;a2top=0 ai1中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 4 中国科学技术大学 ➢ 顺序栈 Const STACK_INIT_SIZE=1000; Const STACKINCREMENT=10; Typedef struct{ Selemtype *elem; Int top; Int stacksize; Int increment; }SqStack; 3.2栈的表示和实现 a1 a2 . an-1 top=n-1 top=0

相关操作实现STACK INIT SIZE, intInitStack Sq(SqStack &S,int maxsize=incresmentize= STACKINCREMENT)GetTop_ Sq(SqStack S,SelemType &e)Push Sq(SqStack &S ,SelemType e)Pop Sq(SqStack S ,SelemType &e)IncrementStacksize(SqStack &S)SElemtype *a,a-new SElemType[S.stacksize+S. increment];for(i-0;i<=S.top;i++)a[i]=S.elem[i]delete [l S.elem;S.elem=a;S.stacksize+=S.increment:5ypb@ustc.edu.cn中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 InitStack_Sq(SqStack &S,int maxsize= STACK_INIT_SIZE, int incresmentize= STACKINCREMENT) GetTop_Sq(SqStack S,SelemType &e) Push_Sq(SqStack &S ,SelemType e) Pop_Sq(SqStack S ,SelemType &e) IncrementStacksize(SqStack &S){ SElemtype *a; a=new SElemType[S.stacksize+S. increment]; for(i=0;i<=S.top;i++)a[i]=S.elem[i]; delete [] S.elem; S.elem=a; S.stacksize+=S.increment; } 相关操作实现