中国科学技术大学：《数据结构及算法》课程教学资源（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递归应用示例

S 3.1栈的基本概念 定义：栈(Stack)是限定只能在表得一端进行插入和 删除操作的线性表，又称限定性线性表结构 >栈的结构特点和操作 栈顶(Top)、栈底(Bottom),先入后出(LIFO) >栈的ADT描述 ADT Stack D={ala,∈ElemSet,i=l,2,.n,n≥0} StackEmpty (S) R=(<alarlail,aeD,i=2,3...n) StackLength (S) 基本操作： GetTop(S,&e) InitStack (&S) Push (&S,e) DestroyStack(&S) Pop(&S,&e) ClearStack(&S) StackTraverse(S) End ADT Stack ypb@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

出栈anm…a2,a1 进栈a1,2,…an an a a ypb@ustc.edu.cn 3 中国科学技术大学

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

3.2栈的表示和实现 顺序栈 Const STACK INIT SIZE=1000; Const STACKINCREMENT=10: Typedef struct{ Selemtype *elem; Int top, top=n-1 anL Int stacksize; Int increment; }SqStack; a top-0 a ypb@ustc.edu.cn A 中国科学技术大学

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

相关操作实现 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: ypb@ustc.edu.cn 5 中国科学技术大学

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; } 相关操作实现