13同上 进OPIR栈,取下一符号 e进OPND栈,取下一符号 进OPTR栈,取下一符号se 操作数一f进OPND栈,取下一符号 操作符|ip(/)<isp(↑”),退OPND栈‘f,退 OPNDs3s 栈‘e,退OPTR栈‘↑’,计算e↑f→s4,结果 进OPND栈 18同上同上一 进OPTR栈,取下一符号 桑作数 进OPND栈,取下一符号 操作符-p(;”)<p(/"),退OND栈'g,退OPND|ss 栈‘s4,退OPIR栈‘/,计算s4/g→s,结果 进OPND柱 同上同上 ip(;")<ip(-”),退OPND栈‘s,退OPND|s6 栈‘s3,退OPIR栈‘-’,计算s3 结 果进OPND栈 同上 退OPND栈‘s6,结束 3-8假设以数组Qm]存放循环队列中的元素,同时以rear和 length分别指示环形队列中的队尾位置和队列 中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入( enq ueue)和删除( dequeue) 元素的操作 【解答】 循环队列类定义 #include <assert h> template <class Type> class Queue ∥循环队列的类定义 Queue( int10 ) Queue(i delete [elements; 3 Type DeQueue ( Type GetFront ( void Make Empty (i length =0; 3 ∥置空队列 int Is Empty (const i return length ==0; 3 ∥判队列空否 int IsFull const i return length 判队列满否 prvate /队尾指针和队列长度 Type’ elements; 存放队列元素的数组 int max Size: /队列最大可容纳元素个数 构造函数 Queue<Type>: Queue( int sz ) rear(maxSize-1), length(0), maxSize(sz)t ∥建立一个最大具有 maxSize个元素的空队列。 ∥创建队列空间 assert( elements [=0 断言:动态存储分配成功与否22 进 OPND 栈 13 同上 同上  icp (‘ - ’ ) > isp (‘ ; ’ ), 进 OPTR 栈, 取下一符号 s3 ; - 14 e 操作数  e 进 OPND 栈, 取下一符号 s3 e ; - 15 ↑ 操作符  icp (‘↑’ ) > isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 e ; -↑ 16 f 操作数  f 进 OPND 栈, 取下一符号 s3 e f ; -↑ 17 / 操作符  icp (‘ / ’ ) < isp (‘↑’ ), 退 OPND 栈 ‘f’, 退 OPND 栈 ‘e’, 退 OPTR 栈 ‘↑’, 计算 e↑f → s4, 结果 进 OPND 栈 s3 s4 ; - 18 同上 同上  icp (‘ / ’ ) > isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 s4 ; - / 19 g 操作数  g 进 OPND 栈, 取下一符号 s3 s4 g ; - / 20 ; 操作符  icp (‘ ; ’ ) < isp (‘ / ’ ), 退 OPND 栈 ‘g’, 退 OPND 栈 ‘s4’, 退 OPTR 栈 ‘/’, 计算 s4 / g → s5, 结果 进 OPND 栈 s3 s5 ; - 21 同上 同上  icp (‘ ; ’ ) < isp (‘ - ’ ), 退 OPND 栈 ‘s5’, 退 OPND 栈 ‘s3’, 退 OPTR 栈 ‘ - ’, 计算 s3 – s5 → s6, 结 果进 OPND 栈 s6 ; 22 同上 同上  icp (‘ ; ’ ) == isp (‘ ; ’ ), 退 OPND 栈 ‘s6’, 结束 ; 3-8 假设以数组 Q[m]存放循环队列中的元素, 同时以 rear 和 length 分别指示环形队列中的队尾位置和队列 中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue) 元素的操作。 【解答】 循环队列类定义 #include <assert.h> template <class Type> class Queue { //循环队列的类定义 public: Queue ( int=10 ); ~Queue ( ) { delete [ ] elements; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { length = 0; } //置空队列 int IsEmpty ( ) const { return length == 0; } //判队列空否 int IsFull ( ) const { return length == maxSize; } //判队列满否 private: int rear, length; //队尾指针和队列长度 Type *elements; //存放队列元素的数组 int maxSize; //队列最大可容纳元素个数 } 构造函数 template <class Type> Queue<Type>:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) { //建立一个最大具有 maxSize 个元素的空队列。 elements = new Type[maxSize]; //创建队列空间 assert ( elements != 0 ); //断言: 动态存储分配成功与否