else return M(end2+1)%m]: 4-13设用链表表示一个双端队列,要求可在表的两端插入,但限制只能在表的一端删除。试编写基于此结 构的队列的插入( enqueue)和删除( dequeue)算法,并给出队列空和队列满的条件 解答】 链式双端队列的类定义 template <class Type 链式双端队列类的前视定义 template <class Type> class Doublequeuenode ∥链式双端队列结点类定义 friend class Double queue<Typ Type data; ∥数据域 Double QueueNode<Type> link ∥链域 Doublequeuenode( Type d=0, DoubleQueueNode=NULL):da(d,lmk(D{}∥构造函数 }; template <class Type> class Doublequeue 式双端队列类定义 ∥构造函数 ∥析构函数 void EnDoubleQueuel const Type& item ) ∥从队列end1端插入 con ; ∥从队列end2端插入 Type DeDouble queue ( 删除并返回队头end1元素 Type GetFront ( 查看队头endl元素的值 void Make Empty(; ∥置空队列 int Is Emp() const( return endl==endl->lmnk;}/判队列空否 private: Oueuenode<Iype>*endl,·end2; MendI在链头,可插可删;en在链尾,可插不可删 }; 队列的构造函数 template<class Type> doublequeue<Type> doubleQueue (i ∥构造函数 ∥创建循环链表的表头结点 assert(lendl lend ) end1->link 队列的析构函数 template <class Type> Queue<Type> : :-Queue (i /队列的析构函数 QueueNode<Type> *p /逐个删除队列中的结点,包括表头结点 while( endl I=NULL )P= endl; endl endl->ink; delete P;1 队列的插入函数 template<class Type> ∥从队列endl端插入else return V[(end2+1) % m]; } 4-13 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结 构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。 【解答】 链式双端队列的类定义 template <class Type> class DoubleQueue; //链式双端队列类的前视定义 template <class Type> class DoubleQueueNode { //链式双端队列结点类定义 friend class DoubleQueue<Type>; private: Type data; //数据域 DoubleQueueNode<Type> *link; //链域 public: DoubleQueueNode (Type d = 0, DoubleQueueNode *l = NULL) : data (d), link (l) { } //构造函数 }; template <class Type> class DoubleQueue { //链式双端队列类定义 public: DoubleQueue ( ); //构造函数 ~DoubleQueue ( ); //析构函数 void EnDoubleQueue1 ( const Type& item ); //从队列 end1 端插入 void EnDoubleQueue2 ( const Type& item ); //从队列 end2 端插入 Type DeDoubleQueue ( ); //删除并返回队头 end1 元素 Type GetFront ( ); //查看队头 end1 元素的值 void MakeEmpty ( ); //置空队列 int IsEmpty ( ) const { return end1 == end1->link; } //判队列空否 private: QueueNode<Type> *end1, *end2; //end1 在链头, 可插可删; end2 在链尾, 可插不可删 }; 队列的构造函数 template<class Type> doubleQueue<Type> :: doubleQueue ( ) { //构造函数 end1 = end2 = new DoubleQueueNode<Type>( ); //创建循环链表的表头结点 assert ( !end1 || !end2 ); end1->link = end1; } 队列的析构函数 template <class Type> Queue<Type> :: ~Queue ( ) { //队列的析构函数 QueueNode<Type> *p; //逐个删除队列中的结点, 包括表头结点 while ( end1 != NULL ) { p = end1; end1 = end1->link; delete p; } } 队列的插入函数 template<class Type> //从队列 end1 端插入