while(pl=NULL){s=p;p=p->lmk; delete s;}m逐个删除队列中的结点 队列的插入函数 template <class Type> void Queue<Type>: EnQueue const Type item)i if(P== NULL)( 队列空,新结点成为第一个结点 p= new QueueNode<type>( item, NULL); P->link =p; QueueNode<type> *s=new QueueNode<Type>( item, NULL); s->lnk=p->lnk;p=p->lnk=s;w结点p指向新的队尾 队列的删除函数 emplate <class Type> Type queue<Type>: DeQueue (i if(p==NULL){cout<<"队列空,不能删除!"<<end; return0;} s= 队头结点为 ∥重新链接,将结点s从链中摘下 Type revalue = s->data: delete s; ∥保存原队头结点中的值,释放原队头结点 return revalue ∥返回数据存放地址 队空条件p==NUL。 4-12若将一个双端队列顺序表示在一维数组Ⅵm中,两个端点设为endl和end2,并组织成一个循环队列 试写出双端队列所用指针endl和end2的初始化条件及队空与队满条件,并编写基于此结构的相应的插入 ( enqueue)新元素和删除( dEqueue)算法。 【解答】 初始化条件endl=end2=0; 队空条件endl=end2 队满条件(endl+1)%m=enn2;∥设endl端顺时针进栈,end端逆时针进栈 循环队列类定义 #include <assert h> template <class Type> class Doublequeue i ∥循环队列的类定义 Doublequeue ( delete [V; void EnQueue( Type& item, const int end ); Type DeQueue(const int end); Type GetFront (const int end ) void Make Empty (endl end =0; 置空队列 ∥判两队列空否 int IsFull(() const{ return(endl1+1)%m==endn2;}∥判两队列满否 int endl. end2 /队列两端的指针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。 4-12 若将一个双端队列顺序表示在一维数组 V[m]中，两个端点设为 end1 和 end2，并组织成一个循环队列。 试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入 (enqueue)新元素和删除(dlqueue)算法。 【解答】 初始化条件 end1 = end2 = 0; 队空条件 end1 = end2; 队满条件 ( end1 + 1 ) % m = end2; //设 end1 端顺时针进栈，end2 端逆时针进栈 循环队列类定义 #include <assert.h> template <class Type> class DoubleQueue { //循环队列的类定义 public: DoubleQueue ( int=10 ); ~DoubleQueue ( ) { delete [ ] V; } void EnQueue ( Type & item, const int end ); Type DeQueue (const int end ); Type GetFront (const int end ); void MakeEmpty ( ) { end1 = end2 = 0; } //置空队列 int IsEmpty ( ) const { return end1 == end2; } //判两队列空否 int IsFull ( ) const { return (end1+1) % m == end2; } //判两队列满否 private: int end1, end2; //队列两端的指针 end1 end2