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