栈栈的应用队列优先队列.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,栈,栈的应用,队列,优先队列,第四章 栈和队列,a1,a2,a3,a4,a5,a6,插入 x,i,删除 x,j,插入,删除,栈(Stack),栈和队列 都是特殊的线性表,限定性的线性表,操作受限的线性表,return count=MaxQSize;,case:S.,MathOperator opr1,opr2;,opr2.,void Calculator:Compute(char op),case-:OperandStack.,Push(operand2+operand1);break;,madam im adam is a palindrome,template,void Calculator:Compute(char op),cerr Calling QDelete for an empty queue!endl;,/maximum size of the priority queue array,cerr Missing operand!endl;,InvalidInput=4;,/constructor,if(stackList.,一、栈,限定只在表的一端访问的线性表,元素只能从栈顶插入和删除,先进后出 后进先出,例 羊肉串,子弹夹,货 栈,top,top,A B C D,top,A,B C D,顺序栈的模型,top,B,A,C D,top,C,B,A,D,top,D,C,B,A,top,C,B,A,D,top,B,A,C D,top,A,B C D,top,A B C D,top,top,A B C D,top,A,B C D,top,B,A,C D,top,B,A,C D,top,A B,C D,top,A B,C,D,top,A B,D,C,top,D A B,C,top,C D A B,顺序栈栈类的顺序表示,#ifndef STACK_CLASS,#define STACK_CLASS,#include,#include,const int MaxStackSize=50;,template class Stack,T stacklistMaxStackSize;,int top;,public:,Stack(void);,void Push(const T,T Pop(void);,void ClearStack(void);,T Peek(void)const;/gettop,int StackEmpty(void)const;,int StackFull(void)const;,;,/initialize stack top.,template,Stack:Stack(void):top(-1),/push item on the the stack,template,void Stack:Push(const T&item),/if stacklist is full,terminate the program,if(top=MaxStackSize-1),cerr Stack overflow!endl;,exit(1);,/increment top and copy item to stacklist,top+;,stacklisttop=item;,/pop the stack and return the top element,template,T Stack:Pop(void),T temp;,/if stack is empty,terminate the program,if(top=-1),cerr Attempt to pop an empty stack!endl;,exit(1);,temp=stacklisttop;/record the top element,top-;,return temp;,/return the value at the top of the stack,template,T Stack:Peek(void)const,/if the stack is empty,terminate the program,if(top=-1),cerr Attempt to peek at an empty stack!endl;,exit(1);,return stacklisttop;,/test for an empty stack,template,int Stack:StackEmpty(void)const,/return the logical value top=-1,return top=-1;,/test for a full stack,template,int Stack:StackFull(void)const,/test the position of top,return top=MaxStackSize-1;,/clear all items from the stack,template,void Stack:ClearStack(void),top=-1;,#endif /STACK_CLASS,链栈,栈的链式表示,线性链表类的定义,#include node.h,template,class LinkedList,Node*front,*rear,*prevPtr,*currPtr;,int size;,int position;,Node*GetNode(const T,void FreeNode(Node*p);,void CopyList(const LinkedList,public:,LinkedList(void);,LinkedList(const LinkedList,LinkedList(void);,LinkedList,int ListSize(void)const;,int ListEmpty(void)const;,void Reset(int pos=0);,void Next(void);,int EndOfList(void)const;,int CurrentPosition(void)const;,void InsertFront(const T,void InsertRear(const T,void InsertAt(const T,void InsertAfter(const T,T DeleteFront(void);,void DeleteAt(void);,T,void ClearList(void);,链栈类的定义,#ifndef STACK_CLASS,#define STACK_CLASS,#include,#include,#include link.h,template class Stack,LinkedList stackList;,public:,Stack(void);/constructor,void Push(const T,T Pop(void);,T Peek(void);,int StackEmpty(void)const;,void ClearStack(void);,;,/constructor,template,Stack:Stack(void),/uses the LinkedList method/ClearList to clear the stack,template,void Stack:ClearStack(void),stackList.ClearList();,/use the LinkedList method/InsertFront to push item,template,void Stack:Push(const T&item),stackList.InsertFront(item);,/use the LinkedList method DeleteFront to pop stack,template,T Stack:Pop(void),/check for an empty linked list,if(stackList.ListEmpty(),cerr Popping an empty stack endl;,exit(1);,/delete first node and return its data value,return stackList.DeleteFront();,/returns the data value of the first first item on the stack,template,T Stack:Peek(void),/check for an empty linked list,if(stackList.ListEmpty(),cerr Calling Peek for an empty stack endl;,exit(1);,/reset to the front of linked list and return value,stackList.Reset();,return stackList.Data();,/use the LinkedList method/ListEmpty to test for empty stack,template,int Stack:StackEmpty(void)const,return stackList.ListEmpty();,#endif /STACK_CLASS,二、栈的应用,回文验证,数制转换,表达式求值,括号匹配检验,行编辑程序,递归实现,回文验证palindrome回文的例子,dad,madam,sees,madam im adam,a man a plan a canal panama,#include,#pragma hdrstop,#include astack.h,/creates a new string with all blank characters removed,void Deblank(char*s,char*t),/loop through expression until NULL character is found,while(*s!=NULL),/if character is a non-blank,copy to new string,if(*s!=),*t+=*s;,s+;/move to next character,*t=NULL;/append NULL to new string,void main(void),const int True=1,False=0;,Stack S;/stack elements are characters,char palstring80,deblankstring80,c;,int i=0；,int ispalindrome=True;/assume string is a palindrome,cin.getline(palstring,80,n);/read in the full-line string,/remove blanks from string and put result in deblankstring,Deblank(palstring,deblankstring);,/push the chars of deblanked expression on the stack,i=0;,while(deblankstringi!=0),S.Push(deblankstringi);i+;,i=0;,while(!S.StackEmpty(),c=S.Pop();/get next character from stack,if(c!=deblankstringi),ispalindrome=False;break;,i+;,if(ispalindrome)cout palstring is a palindrome endl;,else cout palstring is not a palindrome endl;,/*,madam im adam,madam im adam is a palindrome,a man a plan a canal panama,a man a plan a canal panama is a palindrome,palindrome,palindrome is not a palindrome,*/,数制转换输入十进制数，以其他进制输出,#include,#pragma hdrstop,#include astack.h,/print integer num in base B,void MultibaseOutput(long num,int B),/stack holds base B digits left to right,Stack S;,/extract base B digits right to left and push on stack S,do,S.Push(int(num%B);/convert to int and push on stack,num/=B;/remove right most digit,while(num!=0);/continue until all digits computed,while(!S.StackEmpty()/flush the stack,cout S.Pop();,void main(void),long num;/decimal number,int B;/base,/read 3 positive numbers and the desired base 2=B=9,for(int i=0;i 3;i+),cout Enter non-negative decimal number and base,(2=B num B;,cout num base B is;,MultibaseOutput(num,B);,cout endl;,/*Enter non-negative decimal number and base(2=B=9):72 4,72 base 4 is 1020,Enter non-negative decimal number and base(2=B=9):53 2,53 base 2 is 110101,Enter non-negative decimal number and base(2=B=9):3553 8,3553 base 8 is 6741,*/,表达式求值,中缀表达式,a+b*c,a+b*(c-d)+e/f,(b*b-4*a*c)/(2*a),后缀表达式,abc*+,abcd-*+ef/+,bb*4a*c*-2a*/,/后缀表达式求值/calc.h,#include,#include,#pragma hdrstop,enum Boolean False,True;,#include astack.h,class Calculator,Stack S;/holds operands,void Enter(double num);,Boolean GetTwoOperands(double,void Compute(char op);,public:,Calculator(void);,/evaluate an expression and clear calculator,void Run(void);,void Clear(void);,;,/store data value on the stack,void Calculator:Enter(double num),S.Push(num);,Boolean Calculator:GetTwoOperands(double&opnd1,double&opnd2),if(S.StackEmpty()/check for presence of operand,cerr Missing operand!endl;,return False;,opnd1=S.Pop();/fetch right-hand operand,if(S.StackEmpty(),cerr Missing operand!endl;,return False;,opnd2=S.Pop();/fetch left-hand operand,return True;,void Calculator:Compute(char op),Boolean result;double operand1,operand2;,result=GetTwoOperands(operand1,operand2);,if(result=True)switch(op),case+:S.Push(operand2+operand1);break;,case-:S.Push(operand2-operand1);break;,case*:S.Push(operand2*operand1);break;,case/:if(operand1=0.0),cerr Divide by 0!c,c!=)/read until=(Quit),switch(c),case+:case-:case*:case/:case:,Compute(c);break;,default:/not operator,must be operand;put char back,cin.putback(c);/read the operand and store it on the stack,cin newoperand;Enter(newoperand);break;,if(!S.StackEmpty()cout S.Peek()=opr1)opr2=OperatorStack.,stacklisttop=item;,if(isdigit(ch)|ch=.,rear=0;,/print integer num in base B,int B;/base,Stack(void);,else if(ch=rightparenthesis)opr1=MathOperator(ch);while(!OperatorStack.,InsertRear(elt);,#ifndef QUEUE_CLASS,优先级队列/apqueue.,/operator.,opr2.,Push(operand2/operand1);break;,void Calculator:Clear(void),S.ClearStack();,#include calc.h,void main(void),Calculator CALC;,CALC.Run();,/*,8 8*6 6*+.5 =,10,3 4+*,Missing operand!,3 4+8*=,56,1 0/=,Divide by 0!,*/,中缀表达式求值,定义表达式等级,为表达式中每个元素赋一个等级,表达式的累计等级必须为0或1,整个表达式的等级为1,项,等级,数,1,正负+-,0,运算+-*/,-1,左右括号（）,0,5+3*-6,读到负号时等级累计-1，出错,5+3-,最后等级0，出错,中缀表达式求值法,用两个栈：一个存放操作数,一个存放运算符,2+3-4*5=,3,2,+,操作数,读入“-”,弹出两个,-优先级与+相同,操作数运算得到结,运算符,弹出+,果6入栈,6,-,操作数,运算符,“-”入栈,5,4,*,6,-,操作数,4入栈,5入栈,“*”优先级高于“-”,运算符,“*”入栈,20,6,-,操作数,弹出“*”,20入栈,弹出5 4运算,运算符,20,6,-,操作数,弹出“-”,-14入栈,弹出20 6运算,运算符,-14,操作数,弹出结果-14,运算符,定义运算符优先级,icp 栈外优先级 in coming priority,isp 栈内优先级 in stack priority,运算符,icp,isp,等级,+-,1,1,-1,*/,2,2,-1,（,3,-1,0,）,0,0,0,#ifndef INFIX_MATH_OPERATIONS,#define INFIX_MATH_OPERATIONS,/list of constants specifying specific error messages,const int OperatorExpected=0,OperandExpected=1,MissingLeftParenthesis=2,MissingRightParenthesis=3,InvalidInput=4;,/labels designating the parentheses characters,const char leftparenthesis =(,rightparenthesis=);,/a class that handles operators on the operator stack,class MathOperator,char op;,int icp，isp;,public:,MathOperator(void);,MathOperator(char ch);,int operator=(MathOperator a)const;,void Evaluate(Stack,char GetOp(void);,;,/default constructor,MathOperator:MathOperator(void),MathOperator:MathOperator(char ch),op=ch;/assign operator,switch(op),case+:case-:icp=1;isp=1;,break;,case*:case/:icp=2;isp=2;,break;,case(:icp=3;isp=-1;,break;,case):icp=0;isp=0;break;,int MathOperator:operator=(MathOperator a)const,return isp=a.icp;,void MathOperator:Evaluate(Stack&OperandStack),float operand1=OperandStack.Pop();,float operand2=OperandStack.Pop();,switch(op)/select operation,case+:OperandStack.Push(operand2+operand1);,break;,case-:OperandStack.Push(operand2-operand1);,break;,case*:OperandStack.Push(operand2*operand1);,break;,case/:OperandStack.Push(operand2/operand1);,break;,/return operator associated/with current object,char MathOperator:GetOp(void),return op;,#endif/INFIX_MATH_OPERATIONS,#include,#include,#include /used for function isdigit,#pragma hdrstop,#include stack.h/include template-based stack class,#include mathop.h/defines the MathOperator class,/checks if character is an operator or parentheses,int isoperator(char ch),if(ch=+|ch=-|ch=*|,ch=/|ch=(),return 1;,else,return 0;,/checks if character is a /whitespace character,int iswhitespace(char ch),if(ch=|ch=t|ch=n),return 1;,else,return 0;,/error handling function,void error(int n),/table gives the different error messages,static char*errormsgs=,Operator expected,Operand expected,Missing left parenthesis,Missing right parenthesis,Invalid input;,cerr errormsgsn number;rank+;,if(rank 1)error(OperatorExpected);,OperandStack.Push(number);,/*process an operator *,else if(isoperator(ch),if(ch!=()rank-;,if(rank=opr1),opr2=OperatorStack.Pop();,opr2.Evaluate(OperandStack);,OperatorStack.Push(opr1);,/*process an operator *,else if(isoperator(ch),if(ch!=()/rank of(is 0,rank-;,if(rank=that of the current operator.,/push the current operator on the operator stack,opr1=MathOperator(ch);,while(!OperatorStack.StackEmpty()&,(opr2=OperatorStack.Peek()=opr1),opr2=OperatorStack.Pop();,opr2.Evaluate(OperandStack);,OperatorStack.Push(opr1);,/*process a right parenthesis *,else if(ch=rightparenthesis)opr1=MathOperator(ch);while(!OperatorStack.StackEmpty(),if(OperatorStack.StackEmpty()error(MissingLeftParenthesis);opr2=OperatorStack.Pop();/get rid of(,else if(!iswhitespace(ch)error(InvalidInput);,if(rank!=1)error(OperandExpected);,while(!OperatorStack.StackEmpty(),opr1=OperatorStack.Pop();,if(opr1.GetOp()=leftparenthesis),error(MissingRightParenthesis);,opr1.Evaluate(OperandStack);,cout The value is,OperandStack.Pop()endl;,/*,2.5+6/3*4-3=,The value is 7.5,(2+3.25)*4=,The value is 21,(4+3)-7)=,Missing left parenthesis,*/,三、队列,允许一端插入另一端取出的线性表,先进先出,队尾 插入端,队头 取出端,a,1,a,2,a,3,a,4,a,5,a,2,a,3,a,4,a,5,a,6,循环队列,a,1,a,2,a,3,a,4,a,5,a,3,a,4,a,5,a,6,a,7,a,8,a,3,a,4,a,5,a,6,a,7,front,rear,a,0,front,rear,a,0,a,1,front,rear,a,0,a,1,a,2,a,3,front,rear,a,1,a,2,a,3,front,rear,a,3,a,4,a,5,front,rear,a,3,a,4,a,5,a,6,front,rear,a,3,a,4,a,5,a,6,a,7,rear,front,a,8,a,3,a,4,a,5,a,6,a,7,rear,front,a,8,a,9,a,3,a,4,a,5,a,6,a,7,rear,front,循环队列-队列的顺序表示,#ifndef QUEUE_CLASS,#define QUEUE_CLASS,#include,#include,/maximum size of a queue list,const int MaxQSize=50;,templateclass Queue,int front,rear,count;,T qlistMaxQSize;,public:,Queue(void);,void QInsert(const T,T QDelete(void);,void ClearQueue(void);,T QFront(void)const;,int QLength(void)const;,int QEmpty(void)const;,int QFull(void)const;,;,/initialize queue front,rear,count,template,Queue:Queue(void):front(0),rear(0),count(0),/insert item into the queue,template,void Queue:QInsert(const T&item),if(count=MaxQSize),cerr Queue overflow!endl;,exit(1);,count+;,qlistrear=item;,rear=(rear+1)%MaxQSize;,/delete element from front of queue and return its value,template,T Queue:QDelete(void),T temp;,if(count=0),cerr Deleting from an empty queue!endl;,exit(1);,temp=qlistfront;,count-;,front=(front+1)%MaxQSize;,return temp;,/return value of the first entry,template,T Queue:QFront(void)const,return qlistfront;,/return number of queue elements,template,int Queue:QLength(void)const,return count;,/test for an empty queue,template,int Queue:QEmpty(void)const,/return the logical value count=0,return count=0;,/test for a full queue,template,int Queue:QFull(void)const,/return the logical value count=MaxQSize,return count=MaxQSize;,/clear the queue by resetting count,/front and rear to 0,void Queue:ClearQueue(void),count=0;,front=0;,rear=0;,#endif /QUEUE_CLASS,队列 Queue类的链式定义,#ifndef QUEUE_CLASS,#define QUEUE_CLASS,#include,#include,#include link.h,template,class Queue,LinkedList queueList;,public:,Queue(void);,void QInsert(const T,T QDelete(void);,T QFront(void);,int QLength(void)const;,int QEmpty(void)const;,void QClear(void);,;,/constructor,template,Queue:Queue(void),/LinkedList method ListSize/returns length of list,template,int Queue:QLength(void)const,return queueList.ListSize();,/LinkedList method ListEmpty/tests for empty queue,template,int Queue:QEmpty(void)const,return queueList.ListEmpty();,/LinkedList method ClearList/clears the queue,template,void Queue:QClear(void),queueList.ClearList();,/LinkedList method InsertRear/inserts item at rear,template,void Queue:QInsert(const T&elt),queueList.InsertRear(elt);,/LinkedList method DeleteFront/removes item from front,template,T Queue:QDelete(void),/test for an empty queue and terminate if true,if(queueList.ListEmpty(),cerr Calling QDelete for an empty queue!endl;,exit(1);,return queueList.DeleteFront();,/return the data value from the first item in the queue,template,T Queue:QFront(void),if(queueList.ListEmpty(),cerr Calling QFront for an empty queue!endl;,exit(1);,/reset to front of the queue and return data,queueList.Reset();,return queueList.Data();,#endif /QUEUE_CLASS,队列的应用,windows命令序列,打印命令序列,涉及排队的问题,基数排序,四、优先级队列,优先级最高的元素先出,Priority Queue,优先级队列/apqueue.h,#ifndef PRIORITYQUEUE_CLASS,#define PRIORITYQUEUE_CLASS,#include,#include,/maximum size of the priority queue array,const int MaxPQSize =50;,template,clas