中国科学技术大学：《数据结构及算法》课程教学资源（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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; } 相关操作实现

S > 链栈 栈顶 typedef LinkList LinkStack; InitStack L(LinkStack &S) Push L(LinkStack &S ,SelemType e) 栈底 Pop_L(LinkStackS ,SelemType &e) Bool GetTop L(Linkstack S,SElemType &e){ if(!S)return FALSE: e=S->data; return TRUE; ypb@ustc.edu.cn 6 中国科学技术大学

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

3.3栈的应用 >例3.1数制转换 -算法3.11 void conversion0 N=a'dn+ad1+...+ard+ao >例3.2括号匹配检验 -算法3.12 bool match(0 a >例3.3背包问题求解 -算法3.13 void knapsack() -若可以w[n-l]>T,则应在pop前加入if(!StackEmpty(S) -外循环结束条件是：I(StackEmpty(S)&&k=n) >例3.4后缀表达式求值 -算法3.l4 void calculate(0 ypb@ustc.edu.cn 量树片做中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 3.3栈的应用 ➢ 例3.1数制转换 – 算法3.11 void conversion() N=an d n+an-1 d n-1+…+a1 d+a0 ➢ 例3.2括号匹配检验 – 算法3.12 bool match() ➢ 例3.3 背包问题求解 – 算法3.13 void knapsack() – 若可以w[n-1]>T，则应在pop前加入 if(!StackEmpty (S)) – 外循环结束条件是：!(StackEmpty(S)&&k==n) ➢ 例3.4 后缀表达式求值 – 算法3.14 void calculate()

原表达式转化为后缀表达式 3.15 void transform(char suffix[],char exp[]) wrPt幻灯片放 规则 1)设立运算符栈，预设栈底为“#”，表达式的结束符为 "# 2)若当前字符是操作数，直接发送后缀表达式 3)若当前运算符是“(”，直接进栈，若当前运算符是“)” 从栈顶起依次退出栈顶运算符发送给后缀表达式，直至 栈顶相应运算符为"(”，“（不发送 4)若当前字符是运算符，且优先级大于栈顶运算符，则入 栈，否则退出栈顶运算符发送给后缀表达式，重复此过 程直至当前运算符优先级大于栈顶元素可以入栈，#不 入栈。 算法3.16：结合了算法3.14和3.15，直接运算中缀表达式> ypb@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 算法3.15 void transform(char suffix[],char exp[]) 规则 1)设立运算符栈，预设栈底为“#” ,表达式的结束符为“#” 2)若当前字符是操作数，直接发送后缀表达式 3)若当前运算符是“(” ，直接进栈，若当前运算符是“)” ， 从栈顶起依次退出栈顶运算符发送给后缀表达式，直至 栈顶相应运算符为“(” ， “(”不发送 4)若当前字符是运算符，且优先级大于栈顶运算符，则入 栈，否则退出栈顶运算符发送给后缀表达式，重复此过 程直至当前运算符优先级大于栈顶元素可以入栈，#不 入栈。 算法3.16：结合了算法3.14和3.15，直接运算中缀表达式。 原表达式转化为后缀表达式

3.4队列的基本概念 定义：队列(Queue)是限定只能在表得一端进 行插入在表的另一端进行删除操作的线性表 >队列的结构特点和操作 队列头(font)、队列尾(rear),先入先出(FIFO) >队列的ADT描述 ADT Queue D=aja;EElemSet,i=1,2,...n,n>0) QueueEmpty(Q) R={<a1,ala1,a∈D,i=2,3..n} QueueLength(Q) 基本操作： GetHead(Q,&e) InitQueue(&Q) EnQueue(&Q,e) DestroyQueue (&Q) Dequeue(&Q,&e) ClearQueue(&Q) QueueTraverse(Q) End ADT Queue ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 3.4队列的基本概念 ➢ 定义：队列（Queue）是限定只能在表得一端进 行插入在表的另一端进行删除操作的线性表 ➢ 队列的结构特点和操作 队列头(front)、队列尾(rear)，先入先出(FIFO) ➢ 队列的ADT描述 ADT Queue｛ D={ai |aiElemSet,i=1,2,…n,n0} R={|ai-1 ,aiD,i=2,3…n} 基本操作： InitQueue(&Q) DestroyQueue (&Q) ClearQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) Dequeue(&Q,&e) QueueTraverse(Q) }End ADT Queue

3.5队列的表示和实现 >顺序（循环）队列：队列首尾相接 表示结构 Q.rear M-1 typedefstruct{ Qelemtype *elem; int front; int rear, int queuesize; int incrementsize; Q.front }SqQueue; 空队列判断 不可用用首尾指针相等来判断队列的空 解决办法：1：增加标志位2：少用一个元素 ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 ➢ 顺序(循环)队列：队列首尾相接 –表示结构 typedefstruct { Qelemtype *elem; int front; int rear; int queuesize; int incrementsize; }SqQueue; –空队列判断 不可用用首尾指针相等来判断队列的空 解决办法：1：增加标志位 2：少用一个元素 0 M-1 1 Q.front Q.rear …... 3.5队列的表示和实现