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

第三章栈和队列 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离散事件模拟

S 3.1栈 3.1.1抽象数据类型栈的定义 >定义：栈 （Stack)是限定只能在表得一端进行插入和删除 操作的线性表，又称限定性线性表结构 栈顶(Top)、栈底(Bottom),先入后出(LIFO) 出栈an·a4 进栈a14,…a, a ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 2 中国科学技术大学 3.1栈 3.1.1抽象数据类型栈的定义 ➢ 定义：栈（Stack）是限定只能在表得一端进行插入和删除 操作的线性表，又称限定性线性表结构 栈顶(Top)、栈底(Bottom),先入后出(LIFO)

栈的ADT描述 ADT Stack{ 数据对象：D={alai∈ElemSet,.i-l,2,.n,n≥0} 数据关系：Rl={a-l,a∈D,i=2,3,.n} 基本操作： InitStack (&S) GetTop(S,&e) DestroyStack(&S) Push (&S,e) ClearStack(&S) Pop(&S,&e) StackEmpty (S) StackTraverse(S) StackLength (S) }ADT Stack ypb@ustc.edu.cn 3 中国科学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学 栈的ADT描述 ADT Stack{ 数据对象:D={ai |aiElemSet,i=1,2,…n,n≥0} 数据关系:R1={| 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)

S 3.1.2栈的表示和实现 > 顺序栈 #define STACK INIT SIZE 100 #define STACKINCREMENT 10 Typedef struct SElemtype *base, SElemtype *top; int stacksize; }SqStack; ypb@ustc.edu.cn 4 中国科学技术大学

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栈的表示和实现

一栈的表示和实现 顺序栈一 维数组sM] 或先分配二个基本容量，逐 段扩大 栈满 栈空 top top 5 top F top 4 top E 4 top 4 top D 3 top 3 D top c top top B top top top A top base 栈空 进栈 出栈 栈顶指针top,指向实际栈顶 设数组维数为M 后的空位置，初值为base. top=base栈空，此时出栈，则下溢(underflow) base保持不变 top-base=M,栈满，此时入栈，则上溢(overflow)

– 栈的表示和实现 顺序栈 一维数组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

S 相关的操作实现 Status InitStack_Sq(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK INIT SIZE;return OK; }//InitStack Sq Status GetTop_Sq(SqStack S,SelemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1);returnOK; Status Push_Sq(SqStack &S,SelemType e){ 栈满、栈空？ *S.top++=e;… Status Pop_Sq(SqStack &S,SelemType &e){ e=*--S.top;... ypb@ustc.edu.cn 6 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 Status InitStack_Sq(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } //InitStack_Sq Status GetTop_Sq(SqStack S,SelemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1);return OK; } Status Push_Sq(SqStack &S ,SelemType e) { … *S.top++=e; … } Status Pop_Sq(SqStack &S ,SelemType &e){ … e=*--S.top; … } 相关的操作实现 栈满、栈空？

链栈 data next typedef LinkList LinkStack; 顶 InitStack L(LinkStack &S) Push L(LinkStack &S ,SelemType e) Pop_L(LinkStack &S ,SelemType &e) 找底 Status GetTop_L(Linkstack S,SElemType &e){ if(!S)return ERROR: e=S->data; return OK: ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 ➢ 链栈 typedef LinkList LinkStack; InitStack_L(LinkStack &S) Push_L(LinkStack &S ,SelemType e) Pop_L(LinkStack &S ,SelemType &e) Status GetTop_L(Linkstack S,SElemType &e){ if(!S) return ERROR; e=S->data; return OK; }

3.2栈的应用 1.数制转换 N=a.dn+an-1.d-1+...+a.d+ao 计算过程·入栈 打印过程- 出栈 例把十进制数159转换成八进制数 8159 余7 -top 819 余3 top 82 余2 top 3 0 7 237 (159)10=(237)8 ypb@ustc.edu.cn 8 树片放中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 3.2栈的应用 1.数制转换 N=an .d n+an-1 .d n-1+…+a1 .d+a0 计算过程 － 入栈 打印过程 － 出栈 例 把十进制数159转换成八进制数 (159)10=(237)8 8 159 8 19 8 2 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2

3.2.2括号匹配检验 {[O]}等括号的匹配* 3.2.3行编辑程序 -算法void LineEdit(O 3.2.4迷宫求解 入口 78 出口 ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 3.2.2括号匹配检验 {[()]}等括号的匹配* 3.2.3行编辑程序 – 算法 void LineEdit() 3.2.4迷宫求解

typedef struct{int r,c;}PosType; 步序，坐标，方向 typedef struct{int ord;Postype seat;int di}SElemType; Typedef int MazeType[MAXR][MAXC]; Status Pass(MazeType maze,PosType CurPos); void FootPrint(MazeType &maze,PosType CurPos); void MarkPrint(MazeType &maze,PosType CurPos); PosType NextPos(PosType CurPos,int Dir); Status MazePath(MazeType &maze,PosType start, PosType end); ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 typedef struct{int r,c;} PosType; typedef struct{int ord;Postype seat;int di} SElemType; Typedef int MazeType[MAXR][MAXC]; Status Pass(MazeType maze, PosType CurPos); void FootPrint(MazeType &maze, PosType CurPos); void MarkPrint(MazeType &maze, PosType CurPos); PosType NextPos(PosType CurPos, int Dir); Status MazePath(MazeType &maze, PosType start, PosType end) ; 步序，坐标，方向