template <class Type> class Queue ∥链式队列类定义 Queue(: p(NULL)0 ∥构造函数 Type item ) 将item加入到队列中 Type DeQueue ( 删除并返回队头元素 ∥查看队头元素的值 int IsEmpty const i return p= NULL; ∥判队列空否 QueueNode<Type>*p; 队尾指针(在循环链表中) }; 队列的析构函数 template <class Type> Queue<Type>: Queue (i 队列的析构函数 while(pl=NULL){s=p;p=p->link; delete s;}∥逐个删除队列中的结点 队列的插入函数 template <class Type> void Queue<Type>: En Queue( const Type item )i if( p== NULL) /队列空,新结点成为第一个结点 p= new QueueNode<Type>( item, NULL ) p->link=p; 队列不空,新结点链入p之后 QueueNode<Type> *s=new QueueNode<Type( iten m, NULL s->link=p->link;p=p->link=s;W结点p指向新的队尾 队列的删除函数 template <class Type> Type Queue<Type>: DeQueue (i i(p=NULL){cout<"队列空,不能删除!"<<endl; return0;} QueueNode<Type> *s=p: 队头结点为p后一个结点 p->link ∥重新链接,将结点s从链中摘下 Type revalue =s->data; delete s; 保存原队头结点中的值,释放原队头结点 return revalue 返回数据存放地址 队空条件p=NULL 3-11若将一个双端队列顺序表示在一维数组Ⅴ[m中,两个端点设为end和end2,并组织成一个循环队列。 试写出双端队列所用指针endl和end2的初始化条件及队空与队满条件,并编写基于此结构的相应的插入 ( enqueue)新元素和删除( dEqueue)算法 【解答】 end2 初始化条件endl=end2=0; 队空条件endl=end225 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; //队尾指针（在循环链表中） }; 队列的析构函数 template <class Type> Queue<Type>::~Queue ( ) { //队列的析构函数 QueueNode<Type> *s; while ( p != NULL ) { s = p; p = p->link; delete s; } //逐个删除队列中的结点 } 队列的插入函数 template <class Type> void Queue<Type>::EnQueue ( const Type & item ) { if ( p == NULL ) { //队列空, 新结点成为第一个结点 p = new QueueNode<Type> ( item, NULL ); p->link = p; } else { //队列不空, 新结点链入 p 之后 QueueNode<Type> *s = new QueueNode<Type> ( item, NULL ); s->link = p->link; p = p->link = s; //结点 p 指向新的队尾 } } 队列的删除函数 template <class Type> Type Queue<Type>::DeQueue ( ) { if ( p == NULL ) { cout << "队列空, 不能删除！" << endl; return 0; } QueueNode<Type> *s = p; //队头结点为 p 后一个结点 p->link = s->link; //重新链接, 将结点 s 从链中摘下 Type retvalue = s->data; delete s; //保存原队头结点中的值, 释放原队头结点 return retvalue; //返回数据存放地址 } 队空条件 p == NULL。 3-11 若将一个双端队列顺序表示在一维数组 V[m]中，两个端点设为 end1 和 end2，并组织成一个循环队列。 试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入 (enqueue)新元素和删除(dlqueue)算法。 【解答】 初始化条件 end1 = end2 = 0; 队空条件 end1 = end2; end1 end2