if( pr== NULL)(q->ink =front front =4:3 插入在队头位置 se i 插入在队列中部或尾部 if(pr== rear )rear=q template< class Type> Type PQueue<Iype>:; Remove(){删除队头元素并返回 if Is Empry ()return NULL; PQueueNode<Type> *g=front: front= front->ink; ∥将队头结点从链中摘下 Type &revalue =q->data; delete q; if (front = NULL)rear NULL return& revalues template<class Type> Type PQueue<Type> : Get(t ∥读取队头元素的值 if( lsEmpry())return NULL (1)栈的定义与实现 template <class Type> class Stack publie PQueue i 栈类定义 Stack ( front( NULL ), rear NULL)1 造函数 void Insert ( Type value ) 插入新元素wae到队尾 oid Stack<Type>: Insert( Type& value )i 插入函数 PQueueNode<type> *q= new PQueueNode value, 0, NULL ) if( lsEmpry ()front =rear=q; ∥栈空时新结点为第一个结点 else( g->ink =front; front=g; 3 插入在前端 (2)队列的定义与实现 template <class Type> class Queue: public PQueue i /队列类定义 Queue () front( NULL), rear(NULL) ∥构造函数 template<class Type> 插入函数 PQueueNode<Type>* 9= new PQueueNode value, 0, NULL ) 队列空时新结点为第一个结点 else rear=rear->ink =9: 插入在队尾位置if ( pr == NULL ) { q->link = front; front = q; } //插入在队头位置 else { q->link = p; pr->link = q; //插入在队列中部或尾部 if ( pr == rear ) rear = q; } } template<class Type> Type PQueue<Type> :: Remove ( ) { //删除队头元素并返回 if ( IsEmpty ( ) ) return NULL; PQueueNode<Type> *q = front; front = front->link; //将队头结点从链中摘下 Type &retvalue = q->data; delete q; if ( front == NULL ) rear = NULL; return& retvalue; } template<class Type> Type PQueue<Type> :: Get ( ) { //读取队头元素的值 if ( IsEmpty ( ) ) return NULL; else return front->data; } (1) 栈的定义与实现 template <class Type> class Stack : public PQueue { //栈类定义 public: Stack ( ) : front ( NULL ), rear ( NULL ) { } //构造函数 void Insert ( Type & value ); //插入新元素 value 到队尾 } template<class Type> void Stack<Type> :: Insert ( Type& value ) { //插入函数 PQueueNode<Type> * q = new PQueueNode ( value, 0, NULL ); if ( IsEmpty ( ) ) front = rear = q; //栈空时新结点为第一个结点 else { q->link = front; front = q; } //插入在前端 } (2) 队列的定义与实现 template <class Type> class Queue : public PQueue { //队列类定义 public: Queue ( ) : front ( NULL ), rear ( NULL ) { } //构造函数 void Insert ( Type& value ); //插入新元素 value 到队尾 } template<class Type> void Queue<Type> :: Insert ( Type & value ) { //插入函数 PQueueNode<Type>* q = new PQueueNode ( value, 0, NULL ); if ( IsEmpty ( ) ) front = rear = q; //队列空时新结点为第一个结点 else rear = rear->link = q; //插入在队尾位置 }