第4章栈与队列 ∥进队列 ∥标志改1,表示队列不空 删除函数 assert(! IsEmpty (); ∥判断队列是否不空,空则出错处理 front =( front+1)%m /队头位置进1,队头指针指示实际队头的前一位置 ∥标志改0,表示栈不满 ∥返回原队头元素的值 读取队头元素函数 Type Queue<Type>: GetFront (i assert(! IsEmpty () ∥判断队列是否不空,空则出错处理 return Q(front 1)%m]; 返回队头元素的值 4-11若使用循环链表来表示队列,p是链表中的一个指针。试基于此结构给出队列的插入( enq ueue)和删除 ( dequeue)算法,并给出p为何值时队列空 【解答】 链式队列的类定义 template <class Type> class Queue ∥链式队列类的前视定义 template <class Type> class QueueNode i ∥链式队列结点类定义 friend class Queue<Type> ∥数据域 QueueNode<Type> *link /链域 QueueNode( Type d=0, QueueNode *=NULL):data(d,ink①{}∥构造函数 template <class Type> class Queue i ∥链式队列类定义 publie Queue ( p(NULL) ∥构造函数 Queue ( ∥析构函数 void En Queue( const Type item ) ∥将iem加入到队列中 Type DeQueue (; ∥删除并返回队头元素 Type GetFront ( 查看队头元素的值 void Make Empty ( ∥置空队列,实现与~ Queue()相同 int Is Empty () const i return p= NULL; ∥判队列空否 QueueNode<Type>*p; /队尾指针(在循环链表中)第 4 章 栈与队列 43 Q[rear] = item; //进队列 tag = 1; //标志改 1，表示队列不空 } 删除函数 template<class Type> Type Queue<Type> :: DeQueue ( ) { assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 front = ( front + 1 ) % m; //队头位置进 1, 队头指针指示实际队头的前一位置 tag = 0; //标志改 0, 表示栈不满 return Q[front]; //返回原队头元素的值 } 读取队头元素函数 template<class Type> Type Queue<Type> :: GetFront ( ) { assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 return Q[(front + 1) % m]; //返回队头元素的值 } 4-11 若使用循环链表来表示队列，p 是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除 (dequeue)算法，并给出 p 为何值时队列空。 【解答】 链式队列的类定义 template <class Type> class Queue; //链式队列类的前视定义 template <class Type> class QueueNode { //链式队列结点类定义 friend class Queue<Type>; private: Type data; //数据域 QueueNode<Type> *link; //链域 public: QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } //构造函数 }; template <class Type> class Queue { //链式队列类定义 public: Queue ( ) : p ( NULL ) { } //构造函数 ~Queue ( ); //析构函数 void EnQueue ( const Type & item ); //将 item 加入到队列中 Type DeQueue ( ); //删除并返回队头元素 Type GetFront ( ); //查看队头元素的值 void MakeEmpty ( ); //置空队列，实现与~Queue ( ) 相同 int IsEmpty ( ) const { return p == NULL; } //判队列空否 private: QueueNode<Type> *p; //队尾指针（在循环链表中）