第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=[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 |aiElemSet,i=1,2,.n,n0} R={|ai-1 ,aiD,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; } 相关操作实现
G>链栈栈顶S-typedefLinkListLinkStack;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:6vpb@ustc.edu.cn中国科学技术大学
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 conversionON=a..dn+an-1 dn-1+... +ar.d+ao>例3.2括号匹配检验- 算法3.12 bool match()>例3.3背包问题求解-算法3.13 void knapsackO-若可以w[n-1]>T，则应在pop前加入if(!StackEmpty(S))一外循环结束条件是：!(StackEmpty(S)&&k==n)>例3.4后缀表达式求值-算法3.14voidcalculate0灯片放中国科学技术大学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 suffixl,char exp[)merPoint幻灯片放规则1)设立运算符栈，预设栈底为“#"表达式的结束符为“#2)若当前字符是操作数，直接发送后缀表达式3)若当前运算符是“("”，直接进栈，若当前运算符是")”从栈顶起依次退出栈顶运算符发送给后缀表达式，直至栈顶相应运算符为"("’，"（"不发送4)若当前字符是运算符，且优先级大于栈顶运算符，则入栈，否则退出栈顶运算符发送给后缀表达式，重复此过程直至当前运算符优先级大于栈顶元素可以入栈，#不入栈。算法3.16：结合了算法3.14和3.15，直接运算中缀表达式8中国科学技术大学ypb@ustc.edu.cn
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队列的基本概念>定义：队列（Oueue）是限定只能在表得一端进行插入在表的另一端进行删除操作的线性表>队列的结构特点和操作队列头(front)、队列尾(rear)，先入先出(FIFO)>队列的ADT描述ADT Queue {QueueEmpty(Q)D=(a;la;eElemSet,i=1,2,...n,n≥0)QueueLength(Q)R=[lai-1,a;eD,i=2,3...n)GetHead(Q,&e)基本操作：EnQueue(&Q,e)InitQueue(&Q)Dequeue(&Q,&e)DestroyQueue (&Q)QueueTraverse(Q)ClearQueue(&Q)EndADTOueue9ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 3.4队列的基本概念 ➢ 定义：队列（Queue）是限定只能在表得一端进 行插入在表的另一端进行删除操作的线性表 ➢ 队列的结构特点和操作 队列头(front)、队列尾(rear)，先入先出(FIFO) ➢ 队列的ADT描述 ADT Queue｛ D={ai |aiElemSet,i=1,2,.n,n0} R={|ai-1 ,aiD,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队列的表示和实现>顺序（循环)队列：队列首尾相接M-1-表示结构Q.reartypedef struct {*elem,Qelemtypeintfront;intrear,int queuesize,int incrementsize;Q.frontfSqQueue;-空队列判断不可用用首尾指针相等来判断队列的空解决办法：1：增加标志位2：少用一个元素10中国科学技术大学ypb@ustc.edu.cn
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队列的表示和实现