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

《栈栈的应用队列优先队列.ppt》由会员分享，可在线阅读，更多相关《栈栈的应用队列优先队列.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n n栈n n栈的应用n n队列 n n优先队列a1a2a3a4a5a6插入 xi删除 xj插入删除栈栈(Stack)栈和队列 都是特殊的线性表 限定性的线性表 操作受限的线性表一、栈限定只在表的一端访问的线性表元素只能从栈顶插入和删除先进后出 后进先出 例 羊肉串 子弹夹 货 栈 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 Dt

2、op B A C Dtop 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&item);T Pop(void);void ClearStack(void)

3、;T Peek(void)const;/gettop int StackEmpty(void)const;int StackFull(void)const;/initialize stack top.templateStack:Stack(void):top(-1)/push item on the the stacktemplatevoid Stack:Push(const T&item)/if stacklist is full,terminate the program if(top=MaxStackSize-1)cerr Stack overflow!endl;exit(1);/inc

4、rement top and copy item to stacklist top+;stacklisttop=item;/pop the stack and return the top elementtemplateT 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

5、the value at the top of the stacktemplateT 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 stacktemplateint Stack:StackEmpty(void)const /return the logical value top=-1 return top=

6、-1;/test for a full stacktemplateint Stack:StackFull(void)const /test the position of top return top=MaxStackSize-1;/clear all items from the stacktemplatevoid Stack:ClearStack(void)top=-1;#endif /STACK_CLASS链栈栈的链式表示线性链表类的定义#include node.htemplate class LinkedList Node*front,*rear,*prevPtr,*currPtr;

7、int size;int position;Node*GetNode(const T&item,Node*ptrNext=NULL);void FreeNode(Node*p);void CopyList(const LinkedList&L);public:LinkedList(void);LinkedList(const LinkedList&L);LinkedList(void);LinkedList&operator=(const LinkedList&L);int ListSize(void)const;int ListEmpty(void)const;void Reset(int

8、pos=0);void Next(void);int EndOfList(void)const;int CurrentPosition(void)const;void InsertFront(const T&item);void InsertRear(const T&item);void InsertAt(const T&item);void InsertAfter(const T&item);T DeleteFront(void);void DeleteAt(void);T&Data(void);void ClearList(void);链栈类的定义#ifndef STACK_CLASS#d

9、efine STACK_CLASS#include#include#include link.htemplate class Stack LinkedList stackList;public:Stack(void);/constructor void Push(const T&item);T Pop(void);T Peek(void);int StackEmpty(void)const;void ClearStack(void);/constructortemplate Stack:Stack(void)/uses the LinkedList method/ClearList to cl

10、ear the stacktemplate void Stack:ClearStack(void)stackList.ClearList();/use the LinkedList method/InsertFront to push itemtemplate void Stack:Push(const T&item)stackList.InsertFront(item);/use the LinkedList method DeleteFront to pop stacktemplate T Stack:Pop(void)/check for an empty linked list if(

11、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 stacktemplate T Stack:Peek(void)/check for an empty linked list if(stackList.ListEmpty()cerr Calling Peek f

12、or 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 stacktemplate int Stack:StackEmpty(void)const return stackList.ListEmpty();#endif /STACK_CLASS二、二、栈的应用回文验证数制转换表达式求值括号匹配检

13、验行编辑程序递归实现回文验证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 removedvoid Deblank(char*s,char*t)/loop through expression until NULL character is found while(*s!=NULL)/if character is a non

14、-blank,copy to new string if(*s!=)*t+=*s;s+;/move to next character *t=NULL;/append NULL to new stringvoid 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,8

15、0,n);/read in the full-line string /remove blanks from string and put result in deblankstringDeblank(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 i

16、f(c!=deblankstringi)ispalindrome=False;break;i+;if(ispalindrome)cout palstring is a palindrome endl;else cout palstring is not a palindrome endl;/*madam im adammadam im adam is a palindromea man a plan a canal panamaa man a plan a canal panama is a palindromepalindromepalindrome is not a palindrome*

17、/数制转换输入十进制数，以其他进制输出#include#pragma hdrstop#include astack.h/print integer num in base Bvoid 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 r

18、ight 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;c

19、out num base B is;MultibaseOutput(num,B);cout endl;/*Enter non-negative decimal number and base(2=B=9):72 472 base 4 is 1020Enter non-negative decimal number and base(2=B=9):53 253 base 2 is 110101Enter non-negative decimal number and base(2=B=9):3553 83553 base 8 is 6741*/表达式求值表达式求值中缀表达式a+b*c a+b*(

20、c-d)+e/f(b*b-4*a*c)/(2*a)后缀表达式abc*+abcd-*+ef/+bb*4a*c*-2a*/后缀表达式求值/calc.h#include#include#pragma hdrstopenum Boolean False,True;#include astack.hclass CalculatorStack S;/holds operands void Enter(double num);Boolean GetTwoOperands(double&opnd1,double&opnd2);void Compute(char op);public:Calculator(vo

21、id);/evaluate an expression and clear calculator void Run(void);void Clear(void);/store data value on the stackvoid 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 Fal

22、se;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

23、(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 ope

24、rand and store it on the stack cin newoperand;Enter(newoperand);break;if(!S.StackEmpty()cout S.Peek()endl;void Calculator:Clear(void)S.ClearStack();#include calc.hvoid main(void)Calculator CALC;CALC.Run();/*8 8*6 6*+.5 =103 4+*Missing operand!3 4+8*=561 0/=Divide by 0!*/中缀表达式求值定义表达式等级为表达式中每个元素赋一个等级表

25、达式的累计等级必须为0或1整个表达式的等级为1 项等级数1正负+-0运算+-*/-1左右括号（）0 5+3*-6读到负号时等级累计-1，出错5+3-最后等级0，出错 中缀表达式求值法用两个栈：一个存放操作数 一个存放运算符2+3-4*5=32+操作数读入“-”弹出两个-优先级与+相同操作数运算得到结运算符弹出+果6入栈6-操作数运算符“-”入栈54*6-操作数4入栈5入栈“*”优先级高于“-”运算符“*”入栈206-操作数弹出“*”20入栈弹出5 4运算运算符206-操作数弹出“-”-14入栈弹出20 6运算运算符-14操作数弹出结果-14运算符定义运算符优先级icp 栈外优先级 in com

26、ing priorityisp 栈内优先级 in stack priority运算符icpisp等级+-11-1*/22-1（3-10）000#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;/lab

27、els designating the parentheses characters const char leftparenthesis =(,rightparenthesis=);/a class that handles operators on the operator stackclass MathOperator char op;int icp，isp;public:MathOperator(void);MathOperator(char ch);int operator=(MathOperator a)const;void Evaluate(Stack&OperandStack)

28、;char GetOp(void);/default constructorMathOperator: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

29、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;c

30、ase/: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/de

31、fines the MathOperator class/checks if character is an operator or parenthesesint isoperator(char ch)if(ch=+|ch=-|ch=*|ch=/|ch=()return 1;else return 0;/checks if character is a /whitespace characterint iswhitespace(char ch)if(ch=|ch=t|ch=n)return 1;else return 0;/error handling functionvoid error(i

32、nt n)/table gives the different error messages static char*errormsgs=Operator expected,Operand expected,Missing left parenthesis,Missing right parenthesis,Invalid input;cerr errormsgsn endl;exit(1);void main(void)Stack OperatorStack;Stack OperandStack;MathOperator opr1,opr2;int rank=0;float number;c

33、har ch;/process the expression until=is read while(cin.get(ch)&ch!=)/*process a floating point operand *if(isdigit(ch)|ch=.)cin.putback(ch);cin number;rank+;if(rank 1)error(OperatorExpected);OperandStack.Push(number);/*process an operator *else if(isoperator(ch)if(ch!=()rank-;if(rank=opr1)opr2=Opera

34、torStack.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=OperatorSt

35、ack.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()&(opr2=OperatorStack.Peek()=opr1)opr2=OperatorStack.Pop();opr2.Evaluate(OperandStack);if(Ope

36、ratorStack.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.Evalu

37、ate(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*/三、队列允许一端插入另一端取出的线性表先进先出队尾 插入端队头 取出端 a1a2a3a4a5a2a3a4a5a6循环队列a1a2a3a4a5a3a4a5a6a7 a8a3a4a5a6a7 frontrear a0 frontrear a0 a1 frontrear a0 a1 a2 a3frontr

38、ear a1 a2 a3frontrear a3a4a5frontrear a3a4a5a6frontrear a3a4a5a6 a7rearfront a8 a3a4a5a6 a7rearfront a8 a9 a3a4a5a6 a7rearfront循环队列循环队列-队列的顺序表示队列的顺序表示#ifndef QUEUE_CLASS#define QUEUE_CLASS#include#include/maximum size of a queue listconst int MaxQSize=50;templateclass Queue int front,rear,count;T ql

39、istMaxQSize;public:Queue(void);void QInsert(const T&item);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,counttemplateQueue:Queue(void):front(0),rear(0),count(0)/insert item into the queue templ

40、atevoid 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 valuetemplateT Queue:QDelete(void)T temp;if(count=0)cerr Deleting from an empty queue!endl;exit(1);temp=qlistfront;cou

41、nt-;front=(front+1)%MaxQSize;return temp;/return value of the first entry templateT Queue:QFront(void)const return qlistfront;/return number of queue elementstemplateint Queue:QLength(void)const return count;/test for an empty queuetemplateint Queue:QEmpty(void)const /return the logical value count=

42、0 return count=0;/test for a full queuetemplateint Queue:QFull(void)const /return the logical value count=MaxQSize return count=MaxQSize;/clear the queue by resetting count,/front and rear to 0void Queue:ClearQueue(void)count=0;front=0;rear=0;#endif /QUEUE_CLASS 队列 Queue类的链式定义#ifndef QUEUE_CLASS#def

43、ine QUEUE_CLASS#include#include#include link.htemplate class Queue LinkedList queueList;public:Queue(void);void QInsert(const T&elt);T QDelete(void);T QFront(void);int QLength(void)const;int QEmpty(void)const;void QClear(void);/constructortemplate Queue:Queue(void)/LinkedList method ListSize/returns

44、 length of listtemplate int Queue:QLength(void)const return queueList.ListSize();/LinkedList method ListEmpty/tests for empty queuetemplate int Queue:QEmpty(void)const return queueList.ListEmpty();/LinkedList method ClearList/clears the queuetemplate void Queue:QClear(void)queueList.ClearList();/Lin

45、kedList method InsertRear/inserts item at reartemplate void Queue:QInsert(const T&elt)queueList.InsertRear(elt);/LinkedList method DeleteFront/removes item from fronttemplate T Queue:QDelete(void)/test for an empty queue and terminate if true if(queueList.ListEmpty()cerr Calling QDelete for an empty

46、 queue!endl;exit(1);return queueList.DeleteFront();/return the data value from the first item in the queuetemplate 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();#e

47、ndif /QUEUE_CLASS队列的应用windows命令序列打印命令序列涉及排队的问题基数排序四、优先级队列四、优先级队列优先级最高的元素先出Priority Queue优先级队列优先级队列/apqueue.h#ifndef PRIORITYQUEUE_CLASS#define PRIORITYQUEUE_CLASS#include#include/maximum size of the priority queue arrayconst int MaxPQSize =50;templateclass PQueue int count;T pqlistMaxPQSize;public:P

48、Queue(void);void PQInsert(const T&item);T PQDelete(void);void ClearPQ(void);int PQEmpty(void)const;int PQFull(void)const;int PQLength(void)const;/initialize priority queue counttemplatePQueue:PQueue(void):count(0)/insert item into the priority queuetemplatevoid PQueue:PQInsert(const T&item)if(count=

49、MaxPQSize)cerr Priority queue overflow!endl;exit(1);/place item at the rear of the list and increment count pqlistcount=item;count+;templateT PQueue:PQDelete(void)T min;int i,minindex=0;if(count 0)min=pqlist0;for(i=1;i count;i+)if(pqlisti min)min=pqlisti;minindex=i;pqlistminindex=pqlistcount-1;count

50、-;else cerr Deleting from an empty priority queue!endl;exit(1);return min;/return number of list elementstemplateint PQueue:PQLength(void)const return count;/test for an empty priority queuetemplateint PQueue:PQEmpty(void)const return count=0;/test for a full priority queuetemplateint PQueue:PQFull(