第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, 队尾指针指示实际队尾位置