栈和队列培训课件.ppt

1、12template class Stack public:Stack(int=10);/构造函数构造函数 void Push(const E&item);/进栈进栈 E Pop();/出栈出栈 E getTop();/取栈顶元素取栈顶元素 void makeEmpty();/置空栈置空栈 int IsEmpty()const;/判栈空否判栈空否 int IsFull()const;/判栈满否判栈满否3#include template class SeqStack:public Stack private:int top;/栈顶指针 E*elements;/栈元素数组 int maxSize

2、;/栈最大容量 void overflowProcess();/栈的溢出处理0 1 2 3 4 5 6 7 8 9 maxSize-1top()elements4 public:Stack(int sz=10);/构造函数 Stack()delete elements;void Push(E x);/进栈 int Pop(E&x);/出栈 int getTop(E&x);/取栈顶 void makeEmpty()top=-1;/置空栈 int IsEmpty()const return top=-1;int IsFull()const return top=maxSize-1;5 top空栈t

3、optoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出6topc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptoptopabdee 退栈c78顺序栈的操作template void SeqStack:overflowProcess()/私有函数：当栈满则执行扩充栈存储空间处理 E*newArray=new E2*maxSize;/创建更大的存储数组 for(int i=0;i=top;i+)newArrayi=elementsi;maxSize+=maxSize;delete elements;elements=newArray;/改

4、变elements指针;9template void SeqStack:Push(E x)/若栈不满,则将元素x插入该栈栈顶,否则溢出处理 if(IsFull()=true)overflowProcess();/栈满 elements+top=x;/栈顶指针先加1,再进栈;template bool SeqStack:Pop(E&x)/函数退出栈顶元素并返回栈顶元素的值 if(IsEmpty()=true)return false;x=elementstop-;/栈顶指针退1 return true;/退栈成功;10template bool Seqstack:getTop(E&x)/若栈不空

5、则函数返回该栈栈顶元素的地址 if(IsEmpty()=true)return false;x=elementstop;return true;11/栈顶指针相遇栈顶指针退到栈底12bool Push(DualStack&DS,E x,int i)if(DS.t0+1=DS.t1)return false;if(i=0)DS.t0+;else DS.t1-;DS.VDS.ti=x;return true;bool Pop(DualStack&DS,E&x,int i)if(DS.ti=DS.bi)return false;x=DS.VDS.ti;if(i=0)DS.t0-;else DS.t1

6、+;return true;131415链式栈(LinkedStack)类的定义#include#include“stack.h”template struct StackNode /栈结点类定义private:E data;/栈结点数据 StackNode*link;/结点链指针public:StackNode(E d=0,StackNode*next=NULL):data(d),link(next);16template class LinkedStack:public Stack /链式栈类定义 private:StackNode*top;/栈顶指针public:LinkedStack(

7、):top(NULL)/构造函数 LinkedStack()makeEmpty();/析构函数 void Push(E x);/进栈 bool Pop(E&x);/退栈17 bool getTop(E&x)const;/取栈顶 bool IsEmpty()const return top=NULL;void makeEmpty();/清空栈的内容 friend ostream&operator (ostream&os,LinkedStack&s);/输出栈元素的重载操作;18链式栈类操作的实现template LinkedStack:makeEmpty()/逐次删去链式栈中的元素直至栈顶指针为

8、空。StackNode*p;while(top!=NULL)/逐个结点释放 p=top;top=top-link;delete p;template void LinkedStack:Push(E x)/将元素值x插入到链式栈的栈顶,即链头 top=new StackNode(x,top);/创建新结点 assert(top!=NULL);/创建失败退出;19template bool LinkedStack:Pop(E&x)/删除栈顶结点,返回被删栈顶元素的值。if(IsEmpty()=true)return false;/栈空返回 StackNode*p=top;/暂存栈顶元素 top=t

9、op-link;/退栈顶指针 x=p-data;delete p;/释放结点 return true;20template bool LinkedStack:getTop(E&x)const if(IsEmpty()=true)return false;/栈空返回 x=top-data;/返回栈顶元素的值 return true;21template ostream&operator (ostream&os,LinkedStack&s)/输出栈中元素的重载操作 os “栈中元素个数=”s.getSize()endl;LinkNode*p=s.top;int i=0;while(p!=NULL)

10、os +i “:”data link;return os;思考：当进栈元素的编号为思考：当进栈元素的编号为1,2,n时，可能的出时，可能的出栈序列有多少种？栈序列有多少种？u中缀中缀(infix)表示表示 如如 A+B；u前缀前缀(prefix)表示表示 ，如如+AB；u后缀后缀(postfix)表示表示 ，如如 AB+；22A+B*(C-D)-E/Fr1r4r2r3r5中缀表达式中缀表达式 后缀表达式后缀表达式A+B*(C-D)-E/FABCD-*+EF/-232425r1r2r3r4r5r626步步 输入输入 类类 型型 动动 作作 栈内容栈内容 1 置空栈置空栈 空空 2 A 操作数操作

11、数 进栈进栈 A 3 B 操作数操作数 进栈进栈 AB 4 C 操作数操作数 进栈进栈 ABC 5 D 操作数操作数 进栈进栈 ABCD 6-操作符操作符 D、C 退栈退栈,计算计算 C-D,结果结果 r1 进栈进栈 ABr1 7*操作符操作符 r1、B 退栈退栈,计算计算 B*r1,结果结果 r2 进栈进栈 Ar2 8+操作符操作符 r2、A 退栈退栈,计算计算 A+r2,结果结果 r3 进栈进栈 r3 27步步 输入输入 类类 型型 动动 作作 栈内容栈内容 9 E 操作数操作数 进栈进栈 r3E 10 F 操作数操作数 进栈进栈 r3EF 11 操作符操作符 F、E 退栈退栈,计算计算

12、EF,结果结果 r4 进栈进栈 r3r4 12 G 操作数操作数 进栈进栈 r3r4G 13/操作符操作符 G、r4 退栈退栈,计算计算 r4/G,结果结果 r5 进栈进栈 r3r5 14-操作符操作符 r5、r3 退栈退栈,计算计算 r3-r5,结果结果 r6 进栈进栈 r6 28void Calculator:Run()char ch;double newoperand;while(cin ch,ch!=;)switch(ch)case+:case-:case*:case/:case :DoOperator(ch);break;/计算 default:cin.putback(ch);/将字

13、符放回输入流 cin newoperand;/读操作数 S.Push(newoperand);29void Calculator:DoOperator(char op)/从栈S中取两个操作数，形成运算指令并计算进栈 double left,right;bool result;result=Get2Operands(left,right);/退出两个操作数 if(!result)return;switch(op)case+:S.Push(left+right);break;/加 case-:S.Push(left-right);break;/减 case*:S.Push(left*right);

14、break;/乘 case/:if(right!=0.0)S.Push(left/right);break;else cout “除数为0!n”);exit(1);/除 case:S.Push(Power(left,right);/乘幂 30bool Calculator:Get2Operands(double&left,double&right)/从栈S中取两个操作数 if(S.IsEmpty()=true)cerr “缺少右操作数！”endl;return false;S.Pop(right);if(S.IsEmpty()=true)cerr “缺少左操作数！”endl;return fa

15、lse;S.Pop(left);return true;3132一般一般表达式的操作符有表达式的操作符有4种类型：种类型：1 算术操作符算术操作符 如双目操作符（如双目操作符（+、-、*、/和和%）以及单目操作符（）以及单目操作符（-）。）。2 关系操作符关系操作符 包括包括、=、。这些操作符主要用于比较。这些操作符主要用于比较。3 逻辑操作符逻辑操作符 如与如与(&)、或、或(|)、非、非(!)。4 括号括号(和和),它们的作用是改变运它们的作用是改变运算顺序。算顺序。33中缀表示 后缀表示先对中缀表达式按运算优先次序加上括号，再把操先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括

16、号的后面并以就近移动为原则，最作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。后将所有括号消去。如中缀表示如中缀表示 (A+B)*D-E/(F+A*D)+C，其转换为后，其转换为后缀表达式的过程如下：缀表达式的过程如下：(A+B)*D)(E/(F+(A*D)+C)后缀表示后缀表示 A B+D*E F A D*+/-C+34利用栈将中缀表示转换为后缀表示使用栈可将表达式的中缀表示转换成它的后使用栈可将表达式的中缀表示转换成它的后缀表示。缀表示。为了实现这种转换，需要考虑各操作符的优为了实现这种转换，需要考虑各操作符的优先级。先级。35各个算术操作符的优先级isp叫做栈内叫做栈内(i

17、n stack priority)优先级优先级icp叫做栈外叫做栈外(in coming priority)优先级。优先级。操作符优先级相等的情况只出现在操作符优先级相等的情况只出现在括号配括号配对对或或栈底的栈底的“;”号与输入流最后的号与输入流最后的“;”号配号配对对时。时。36中缀表达式转换为后缀表达式的算法操作符栈初始化，将结束符操作符栈初始化，将结束符;进栈。然后进栈。然后读入中缀表达式字符流的首字符读入中缀表达式字符流的首字符ch。重复执行以下步骤，直到重复执行以下步骤，直到ch=;，同时栈，同时栈顶的操作符也是顶的操作符也是;，停止循环。，停止循环。u若若ch是操作数直接输出，读

18、入下一个字是操作数直接输出，读入下一个字符符ch。u若若ch是操作符是操作符，判断，判断ch的优先级的优先级icp和和位位于栈顶于栈顶的的操作符操作符op的优先级的优先级isp：37u若若 icp(ch)isp(op)，令，令ch进栈，读入下一进栈，读入下一个字符个字符ch。u若若 icp(ch)isp(op)，退栈并输出。，退栈并输出。u若若 icp(ch)=isp(op)，退栈但不输出，若，退栈但不输出，若退出的是退出的是“(”号读入下一个字符号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式算法结束，输出序列即为所需的后缀表达式38步 输入 栈栈内内容容 语义 输出 动作 12

19、-;+*-*操操作作符符*退退栈栈输输出出 13 ;+-;操操作作符符-进进栈栈,读读字字符符 15 E;-E 操操作作数数E输输出出,读读字字符符 16/;-/-操操作作符符/进进栈栈,读读字字符符 17 F;-/F 操操作作数数F输输出出,读读字字符符 18;-/;/操操作作符符/退退栈栈输输出出 19 ;-;-操操作作符符-退退栈栈输输出出 20 ;=;配配对对,转转换换结结束束 3940递归的定义递归的定义 若一个对象部分地包含它自己，或用它自己若一个对象部分地包含它自己，或用它自己给自己定义给自己定义,则称这个对象是递归的；若一则称这个对象是递归的；若一个过程直接地或间接地调用自己个

20、过程直接地或间接地调用自己,则称这个则称这个过程是递归的过程。过程是递归的过程。以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。u 定义是递归的定义是递归的u 数据结构是递归的数据结构是递归的u 问题的解法是递归的问题的解法是递归的41定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);例如，阶乘函数例如，阶乘函数时时当当时时当当 1,)!1(0,1!nnnnn42求解阶乘 n!的过程 main:factorial(4)参数参数 4 计算计算 4

21、*factorial(3)返回返回 24参数参数 3 计算计算 3*factorial(2)返回返回 6参数参数 2 计算计算 2*factorial(1)返回返回 2参数参数 1 计算计算 1*factorial(0)返回返回 1参数参数 0 直接定值直接定值=1 返回返回 143例如，单链表结构例如，单链表结构一个结点，它的指针域为一个结点，它的指针域为NULL，是一个单，是一个单链表链表;一个结点，它的指针域指向单链表，仍是一一个结点，它的指针域指向单链表，仍是一个单链表。个单链表。数据结构是递归的f f 搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template

22、void Print(ListNode*f)if(f-link=NULL)cout data link);f f f f f a0a1a2a3a4递归找链尾4445问题的解法是递归的例，汉诺塔例，汉诺塔(Tower of Hanoi)问题的解法：问题的解法：如果如果 n=1，则将这一个盘子直接从，则将这一个盘子直接从 A 柱移到柱移到 C 柱上。否则，执行以下三步：柱上。否则，执行以下三步：用用 C 柱做过渡，将柱做过渡，将 A 柱上的柱上的(n-1)个盘子个盘子移到移到 B 柱上：柱上：将将 A 柱上最后一个盘子直接移到柱上最后一个盘子直接移到 C 柱上；柱上；用用 A 柱做过渡，将柱做过渡

23、，将 B 柱上的柱上的(n-1)个盘子个盘子移到移到 C 柱上。柱上。46#include void Hanoi(int n,char A,char B,char C)/解决汉诺塔问题的算法 if(n=1)cout move A to C endl;else Hanoi(n-1,A,C,B);cout move A to C -CA,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CA-BA-BA-CB-CC-BA-C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CB-CA-BB-AB-CA-C4849什么时候

24、运用递归？子问题应与原问题做同样的事情，且更为简单；子问题应与原问题做同样的事情，且更为简单；把一个规模比较大的问题分解为一个或若干规模把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。再综合它们的结果，从而得到原问题的解。分而治之策略（分治法）分而治之策略（分治法）这些比较小的问题的求解方法与原来问题的求解这些比较小的问题的求解方法与原来问题的求解方法一样。方法一样。50构成递归的条件不能无限制地调用本身，必须有一个出口，化简为不能无限制地调用本身，必须有一个出口，化简为非递归状

25、况直接处理。非递归状况直接处理。Procedure ()if()/递归结束条件 return(initial value);else /递归 return(parameter exchange);51递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反：递归调用递归调用 n!(n-1)!(n-2)!1!0!=1 返回次序返回次序主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用外部调用；递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用内部调用。它们返回调用它的过程的地址不同。它们返回

26、调用它的过程的地址不同。递归过程与递归工作栈 long Factorial(long n)int temp;if(n=0)return 1;else temp=n*Factorial(n-1);return temp;void main()int n;n=Factorial(4);RetLoc1RetLoc25253递归工作栈每一次递归调用时，需要为过程中使用的每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。记录，按后进先出的栈组织。递归递归

27、工作记录工作记录递归工作栈54函数递归时的活动记录.Function().调用块调用块函数块函数块计算计算Factorial时活动记录的内容时活动记录的内容递递归归调调用用序序列列0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1参数参数 返回值返回值 返回地址返回地址 返回时的指令返回时的指令return 4*6 /return 3*2 /return 1 /return 1*1 /return 2*1 /5556递归过程改为非递归过程递归过程简洁、易编、易懂递归过程简洁、易编、易懂递归过程效率低，重复计算多递归过程效率低，重复计

28、算多改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率单向递归单向递归和和尾递归尾递归可直接用迭代实现其可直接用迭代实现其非递归过程非递归过程其他情形必须借助其他情形必须借助栈栈实现非递归过程实现非递归过程计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)Fib(n)的定义的定义57求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n-2);1n2),Fib(n1)Fib(n0,1nn,)Fib(n如如 F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

29、调用次数调用次数 NumCall(k)=2*Fib(k+1)-1斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)5859单向递归用迭代法实现long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(int i=2;i=0)cout An=0)cout value An endl;n-;6162template class Queu

30、e public:Queue();/构造函数 Queue();/析构函数 virtual bool EnQueue(E x)=0;/进队列 virtual bool DeQueue(E&x)=0;/出队列 virtual bool getFront(E&x)=0;/取队头 virtual bool IsEmpty()const=0;/判队列空 virtual bool IsFull()const=0;/判队列满;63队列的抽象数据类型#include#include#include“Queue.h”template class SeqQueue:public Queue /队列类定义prote

31、cted:int rear,front;/队尾与队头指针 E*elements;/队列存放数组 int maxSize;/队列最大容量public:SeqQueue(int sz=10);/构造函数 队列的数组存储表示队列的数组存储表示 顺序队列顺序队列64 SeqQueue()delete elements;/析构函数 bool EnQueue(E x);/新元素进队列 bool DeQueue(E&x);/退出队头元素 bool getFront(E&x);/取队头元素值 void makeEmpty()front=rear=0;bool IsEmpty()const return fro

32、nt=rear;bool IsFull()const return rear=maxSize;int getSize()const return rear-front;65队列的进队和出队队列的进队和出队front rear空队列空队列front rearA进队进队Afront rearB进队进队A Bfront rearC,D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F GC D E F Gfront rearH进队进队,溢出溢出66n n n 解决假溢出的办法之一：将队列元素存放解决假

33、溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。数组首尾相接，形成循环（环形）队列。6768队列存放数组被当作首尾相队列存放数组被当作首尾相连连的表处理。的表处理。队头、队尾指针加队头、队尾指针加1时从时从maxSize-1直接进到直接进到0,可用语言的取模可用语言的取模(余数余数)运算实现。运算实现。队头指针进队头指针进1:front=(front+1)%maxSize;队尾指针进队尾指针进1:rear=(rear+1)%maxSize;队列初始化：队列初始化：front=rear=0;队空条件：队空条件：front=rear;队满条件：队满条件：(rear+1)%maxS

34、ize=front循环队列(Circular Queue)01234567front01234567front01234567frontrearAABCrearrear空队列空队列A进进队队B,C进进队队0123456701234567A退退队队B退退队队01234567D,E,F,G,H,I 进进队队frontBCrearA A AfrontB B BCrearfrontCrearDEFG HI6970循环队列操作的定义void MakeEmpty()front=rear=0;int IsEmpty()const return front=rear;int IsFull()const ret

35、urn(rear+1)%maxSize=front;template SeqQueue:SeqQueue(int sz):front(0),rear(0),maxSize(sz)/构造函数 elements=new EmaxSize;assert(elements!=NULL);71template bool SeqQueue:EnQueue(E x)/若队列不满,则将x插入到该队列队尾,否则返回 if(IsFull()=true)return false;elementsrear=x;/先存入 rear=(rear+1)%maxSize;/尾指针加一 return true;72templa

36、te bool SeqQueue:DeQueue(E&x)/若队列不空则函数退队头元素并返回其值 if(IsEmpty()=true)return false;x=elementsfront;/先取队头 front=(front+1)%maxSize;/再队头指针加一 return true;template bool SeqQueue:getFront(E&x)const/若队列不空则函数返回该队列队头元素的值 if(IsEmpty()=true)return false;/队列空 x=elementsfront;/返回队头元素 return true;73#include#include“

37、Queue.h”template struct QueueNode /队列结点类定义private:E data;/队列结点数据 QueueNode*link;/结点链指针public:QueueNode(E x=0,QueueNode *next=NULL):data(x),link(next);74链式队列类的定义template class LinkedQueue private:QueueNode*front,*rear;/队头、队尾指针public:LinkedQueue():rear(NULL),front(NULL)LinkedQueue();bool EnQueue(E x);

38、bool DeQueue(E&x);bool getFront(E&x);void makeEmpty();/实现与Queue()同 bool IsEmpty()const return front=NULL;7576template LinkedQueue:LinkedQueue()/析构函数 QueueNode*p;while(front!=NULL)/逐个结点释放 p=front;front=front-link;delete p;77template bool LinkedQueue:EnQueue(E x)/将新元素x插入到队列的队尾 if(front=NULL)/创建第一个结点 f

39、ront=rear=new QueueNode(x);if(front=NULL)return false;/分配失败 else /队列不空,插入 rear-link=new QueueNode(x);if(rear-link=NULL)return false;rear=rear-link;return true;78template/如果队列不空，将队头结点从链式队列中删去 bool LinkedQueue:DeQueue(E&x)if(IsEmpty()=true)return false;/判队空 QueueNode*p=front;x=front-data;front=front-l

40、ink;delete p;return true;template bool LinkedQueue:getFront(E&x)/若队列不空，则函数返回队头元素的值 if(IsEmpty()=true)return false;x=front-data;return true;79分析第分析第 i i 行元素与第行元素与第 i+1i+1行元素的关系行元素的关系从前一行的数据可以计算下一行的数据从前一行的数据可以计算下一行的数据i=2i=3i=40 1 3 3 1 01 4 6 4 10 1 2 1 00 1 1 0sts+t80从第从第 i i 行数据计算并存放第行数据计算并存放第 i+1 i

41、+1 行数据行数据1 2 1 0 1 3 3 1 0 1 4 6s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1s+t s=t s=t s=t s=t s=t s=t s=t s=ts+t s+t s+t s+t s+t s+t s+t s+t8182利用队列打印二项展开式系数的算法#include#include#include queue.hvoid YANGHVI(int n)Queue q(n+3);/队列初始化 q.makeEmpty();q.EnQueue(1);q.EnQueue(1);int s=0,t;for(int i=1;i=n;i+

42、)/逐行计算 cout endl;q.EnQueue(0);for(int j=1;j=i+2;j+)/下一行 q.DeQueue(t);q.EnQueue(s+t);s=t;if(j!=i+2)cout s ;83 任任务务编编号号 1 2 3 4 5 优优先先权权 20 0 40 30 10 执执行行顺顺序序 3 1 5 4 2848510 20 40 50 70 90插入插入6010 20 40 50 70 90 606010 20 40 50 70 90 6060909070706010 20 40 50 60 70 9086#include#include#include templ

43、ate class PQueue private:E*pqelements;/存放数组 int count;/队列元素计数 int maxPQSize;/最大元素个数 void adjust();/调整87优先级队列的类定义public:PQueue(int sz=50);PQueue()delete pqelements;bool Insert(E x);bool removeMin(E&x);bool getFront(E&x);void makeEmpty()count=0;bool IsEmpty()const return count=0;bool IsFull()const ret

44、urn count=maxPQSize;int Length()const return count;88template PQueue:PQueue(int sz)maxPQSize=sz;count=0;pqelements=new EmaxPQSize;assert(pqelements!=NULL);template bool PQueue:Insert(E x)if(IsFull()=true)return false;/判队满断言 pqelementscount+=x;/插入 adjust();return true;89优先级队列部分成员函数的实现template void PQ

45、ueue:adjust()E temp=pqelementscount-1;/将最后元素暂存再从后向前找插入位置 for(int j=count-2;j=0;j-)if(pqelementsj=temp)break;else pqelementsj+1=pqelementsj;pqelementsj+1=temp;90template bool PQueue:removeMin(E&x)if(IsEmpty()return false;x=pqelements0;/取出0号元素 for(int i=1;i count;i+)pqelementsi-1=pqelementsi;/从后向前逐个移动元素填补空位 count-;return true;91template bool PQueue:getFront(E&x)if(IsEmpty()=true)return false;x=pqelements0;return true;92