第4章栈与队列 上 ip(;")<ip(-”),退OPND栈‘s,退OPND|s6 栈‘s3,退OPIR栈‘-,计算s3-ss→s6,结 22[同上同上 退OPND栈‘s6,结束 4-9假设以数组Q[m]存放循环队列中的元素,同时以rear和 length分别指示环形队列中的队尾位置和队列 中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入( enq ueue和删除 dequeue) 元素的操作 【解答】 循环队列类定义 #include <assert h> template <class Type> class Queue ∥循环队列的类定义 Queue( int10 ) Queue()i delete [elements; 3 Type DeQueue (: void Makeempty ((length =0;1 ∥置空队列 int IsEmpty (const i return length =0; ∥判队列空否 int IsFull const i return length = maxSize; 1 ∥判队列满 private int rear, length; /队尾指针和队列长度 ∥放队列元素的数组 nt max size /队列最大可容纳元素个数 构造函数 Queue<Type>: Queue( int sz ) rear(maxSize-1), length(O), max Size( z)i ∥建立一个最大具有 maxSize个元素的空队列 elements = new Type]: ∥创建队列空间 assert( elements [=0 断言:动态存储分配成功与否 插入函数 template<class Type> yoid Queue<Type> : EnQueue(Type &item )i assert(! IsFull (); ∥判队列是否不满,满则出错处理 度加1 rear=( rear +1)% masi /队尾位置进 ∥进队列 删除函数 template<class Type> (){第 4 章 栈与队列 41 21 同上 同上  icp (‘ ; ’ ) < isp (‘ - ’ ), 退 OPND 栈 ‘s5’, 退 OPND 栈 ‘s3’, 退 OPTR 栈 ‘ - ’, 计算 s3 – s5 → s6, 结 果进 OPND 栈 s6 ; 22 同上 同上  icp (‘ ; ’ ) == isp (‘ ; ’ ), 退 OPND 栈 ‘s6’, 结束 ; 4-9 假设以数组 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 ); //断言: 动态存储分配成功与否 } 插入函数 template<class Type> void Queue<Type> :: EnQueue ( Type &item ) { assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理 length++; //长度加 1 rear = ( rear +1) % maxSize; //队尾位置进 1 elements[rear] = item; //进队列 } 删除函数 template<class Type> Type Queue<Type> :: DeQueue ( ) {