第三章栈和队列3.1栈3.2栈的应用*3.3栈与递归的实现3.4队列*3.5离散事件模拟中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第三章 栈和队列 3.1栈 3.2栈的应用 *3.3栈与递归的实现 3.4队列 *3.5离散事件模拟
3.1栈3.1.1抽象数据类型栈的定义>定义：栈（Stack）是限定只能在表得一端进行插入和删除操作的线性表，又称限定性线性表结构栈顶（Top)、栈底(Bottom)，先入后出(LIFO)出栈a4进栈4a,aa:42a中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 3.1栈 3.1.1抽象数据类型栈的定义 ➢ 定义：栈（Stack）是限定只能在表得一端进行插入和删除 操作的线性表，又称限定性线性表结构 栈顶(Top)、栈底(Bottom),先入后出(LIFO)
栈的ADT描述ADT Stack!数据对象:D={a;|aieElemSet,i-1,2..n,n>0数据关系:R1=[<ai-1,a;> ai-1,a; ED,i=2,3,..n)基本操作：InitStack （&s)GetTop (S, &e)Push(&S, e)DestroyStack(&S)ClearStack(&S)Pop(&S,&e)StackEmpty (S)StackTraverse(S)StackLength (S) ADT Stack3中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 栈的ADT描述 ADT Stack{ 数据对象:D={ai |aiElemSet,i=1,2,.n,n≥0} 数据关系:R1={<ai-1 ,ai>| ai-1 ,ai D,i=2,3,.n} 基本操作: }ADT Stack InitStack（&S） DestroyStack(&S) ClearStack(&S) StackEmpty（S） StackLength（S） GetTop(S,&e) Push(&S, e) Pop(&S,&e) StackTraverse(S)
3.1.2栈的表示和实现>顺序栈#define STACK INIT SIZE 100#define STACKINCREMENT 10Typedef struct:*base,SElemtype*top,SElemtypeintstacksize;}SqStack;中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 ➢ 顺序栈 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 Typedef struct{ SElemtype *base; SElemtype *top; int stacksize; }SqStack; 3.1.2栈的表示和实现
一栈的表示和实现顺序栈一维数组s[M] 或先分配一个基本容量，逐栈满栈空段扩大toptoptopF555toptopEtop444toptopD33toptopC222Btoptoptoptoptop0A00base栈空进栈出栈设数组维数为M栈顶指针top，指向实际栈顶top==base栈空，此时出栈，则下溢（underflow)后的空位置，初值为basetop-base==M,栈满,此时入栈，则上溢（overflow)base保持不变
– 栈的表示和实现 顺序栈 一维数组s[M] 或先分配一个基本容量，逐 段扩大 栈顶指针top,指向实际栈顶 后的空位置，初值为base. base保持不变 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组维数为M top==base栈空，此时出栈，则下溢（underflow) top-base==M,栈满,此时入栈，则上溢（overflow) top top top top top 1 2 3 4 5 A 0 B C D E top F top top top top top 栈空 top top 1 2 3 4 5 0 栈空 base