第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 ( ) {
第4章栈与队列 assert(! IsEmpty () ∥判断队列是否不空,空则出错处理 /队列长度减1 return elements( rearden gth+ maxsize)% maxs ize];∥返回原队头元素值 读取队头元素值函数 template<class Type> Type Queue<Type>: Get Front()i assert(! IsEmpty () return elements[(rear-length+ 1+maxs ize)% maxSize; /返回队头元素值 4-10假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag,以tag=0和tag=1来区别在队 头指针( front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入( enqueue)和 删除( dequeue)算法。 【解答】 循环队列类定义 #include <assert h> template <class Type> class Queue 环队列的类定义 Queue( int=10); Queue(i delete [Q: 3 void EnQueue( Type item ) Type getFront(片 void MakeEmpty (i front =rear=tag=0; 3 ∥置空队列 int Is Empty) const{ return front=rear&&tag=0;}∥判队列空否 int IsFull( const{ return front=rear&&tag==1;}∥判队列满否 int rear, front, tag: 队尾指针、队头指针和队满标志 ∥存放队列元素的数组 int m; 队列最大可容纳元素个数 构造函数 template <class Type Queue<Type>: Queue( int Sz ) rear(), front(O), tag(O), m(sz)i ∥建立一个最大具有m个元素的空队列 ∥创建队列空间 assert(Q=0; 断言:动态存储分配成功与否 插入函数 assert(!IsFu()片; ∥判队列是否不满,满则出错处理 rear=( rear+1)% /队尾位置进1,队尾指针指示实际队尾位置
第 4 章 栈与队列 42 assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 length--; //队列长度减 1 return elements[(rear-length+maxSize) % maxSize]; //返回原队头元素值 } 读取队头元素值函数 template<class Type> Type Queue<Type> :: GetFront ( ) { assert ( ! IsEmpty ( ) ); return elements[(rear-length+1+maxSize) % maxSize]; //返回队头元素值 } 4-10 假设以数组 Q[m]存放循环队列中的元素, 同时设置一个标志 tag，以 tag == 0 和 tag == 1 来区别在队 头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和 删除(dlqueue)算法。 【解答】 循环队列类定义 #include <assert.h> template <class Type> class Queue { //循环队列的类定义 public: Queue ( int=10 ); ~Queue ( ) { delete [ ] Q; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { front = rear = tag = 0; } //置空队列 int IsEmpty ( ) const { return front == rear && tag == 0; } //判队列空否 int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否 private: int rear, front, tag; //队尾指针、队头指针和队满标志 Type *Q; //存放队列元素的数组 int m; //队列最大可容纳元素个数 } 构造函数 template <class Type> Queue<Type>:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) { //建立一个最大具有 m 个元素的空队列。 Q = new Type[m]; //创建队列空间 assert ( Q != 0 ); //断言: 动态存储分配成功与否 } 插入函数 template<class Type> void Queue<Type> :: EnQueue ( Type &item ) { assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理 rear = ( rear + 1 ) % m; //队尾位置进 1, 队尾指针指示实际队尾位置