【正文】 )。 end2在鏈尾, 可插不可刪 }。 }隊(duì)列的析構(gòu)函數(shù) template class Type QueueType :: ~Queue ( ) { //隊(duì)列的析構(gòu)函數(shù) QueueNodeType *p。 } } 隊(duì)列的插入函數(shù) templateclass Type //從隊(duì)列end1端插入void DoubleQueueType :: EnDoubleQueue1 ( const Typeamp。 item ) { end2 = end2link = new DoubleQueueNodeType ( item, end1 )。 //被刪除結(jié)點(diǎn) end1link = plink。 return retvalue。 //逐個(gè)刪除隊(duì)列中的結(jié)點(diǎn), 包括表頭結(jié)點(diǎn) while ( end1 != end1link ) { p = end1。寫(xiě)出各個(gè)類的聲明。 //析構(gòu)函數(shù) virtual void Add ( const Typeamp。 } //判空函數(shù) virtual int IsFull ( ) { return top == maxSize 1。 //存儲(chǔ)數(shù)組 int maxSize。 top = 1。 else elements [ ++top ] = item。 x = elements [0]。 top。 //構(gòu)造函數(shù) ~Stack ( )。 return NULL。x。 隊(duì)列的構(gòu)造函數(shù)templateclass Type QueueType :: Queue ( int sz ) : Bag ( sz ) { }//隊(duì)列的構(gòu)造函數(shù)Queue將調(diào)用Bag的構(gòu)造函數(shù) 優(yōu)先級(jí)隊(duì)列的類定義（繼承Bag類） template class Type class PQueue : public Bag { public: PQueue ( int sz = DefaultSize )。 優(yōu)先級(jí)隊(duì)列的刪除函數(shù) template class Type Type *PQueueType :: Remove ( ) { //若優(yōu)先級(jí)隊(duì)列不空則函數(shù)返回該隊(duì)列具最大優(yōu)先權(quán)(值最小)元素的值, 同時(shí)將該元素刪除。 min = elements[0]。 i++ ) if ( elements[i] min ) { min = elements[i]。 returnamp。 //前視的類定義 template class Type class PQueueNode { //優(yōu)先級(jí)隊(duì)列結(jié)點(diǎn)類的定義 friend class PQueueType。 } //取得結(jié)點(diǎn)優(yōu)先級(jí) virtual PQueueNodeType * GetLink ( ) { return link。 } //修改結(jié)點(diǎn)優(yōu)先級(jí) virtual void SetLink ( PQueueNodeType * next ) { link = next。 //鏈指針 }。 //插入新元素value到隊(duì)尾 virtual Type Remove ( )。 } //判隊(duì)列空否 private: PQueueNodeType *front, *rear。 front = frontlink。 value, int newpriority ) { //插入函數(shù) PQueueNodeType *q = new PQueueNode ( value, newpriority, NULL )。amp。 front = q。 } } templateclass Type Type PQueueType :: Remove ( ) { //刪除隊(duì)頭元素并返回 if ( IsEmpty ( ) ) return NULL。retvalue = qdata。 retvalue。 value )。 //?？諘r(shí)新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn) else { qlink = front。 //插入新元素value到隊(duì)尾 }templateclass Type void QueueType :: Insert ( Type amp。 //插入在隊(duì)尾位置 } 。 if ( IsEmpty ( ) ) front = rear = q。 } //插入在前端 } (2) 隊(duì)列的定義與實(shí)現(xiàn) template class Type class Queue : public PQueue { //隊(duì)列類定義 public: Queue ( ) : front ( NULL ), rear ( NULL ) { } //構(gòu)造函數(shù) void Insert ( Typeamp。 value ) { //插入函數(shù) PQueueNodeType * q = new PQueueNode ( value, 0, NULL )。 else return frontdata。 if ( front == NULL ) rear = NULL。 front = frontlink。 prlink = q。 p = plink。 //隊(duì)列空時(shí)新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn) else { PQueueNodeType *p = front, *pr = NULL。 } //循鏈逐個(gè)刪除 rear = NULL。templateclass Type void PQueueType :: MakeEmpty ( ) { //將優(yōu)先級(jí)隊(duì)列置空 PQueueNodeType *q。 //讀取隊(duì)頭元素的值 virtual void MakeEmpty ( )。 } //析構(gòu)函數(shù) virtual void Insert ( Typeamp。 //數(shù)據(jù) int priority。 value ) { data = value。 value, int newpriority, PQueueType * next ) : data ( value ), priority ( newpriority ), link ( next ) { } //構(gòu)造函數(shù) virtual Type GetData ( ) { return data。 //返回最小元素的值 }415 試?yán)脙?yōu)先級(jí)隊(duì)列實(shí)現(xiàn)棧和隊(duì)列。 } elements[minindex] = elements[top]。 for ( int i = 1。 return NULL。 //刪除函數(shù) } 優(yōu)先級(jí)隊(duì)列的構(gòu)造函數(shù) template class Type PQueueType :: PQueue ( int sz ) : Bag ( sz ) { } //建立一個(gè)最大具有sz個(gè)元素的空優(yōu)先級(jí)隊(duì)列。 //構(gòu)造函數(shù) ~Queue ( )。 x = elements [ top ]。 //刪除函數(shù)}。x。 i top。 return NULL。} Bag類的插入函數(shù)templateclass Type void BagType :: Add ( const Type amp。 //數(shù)組當(dāng)前元素個(gè)數(shù)}。 } virtual void Full ( ) { cerr “DataStructure is full.” endl。 //插入函數(shù) virtual Type *Remove ( )?！窘獯稹?Bag類的定義templateclass Type class Bag {public: Bag ( int sz = DefaultSize )。 delete p。 return end1linkdata。 delete p。 return 0。 else //隊(duì)列不空, 新結(jié)點(diǎn)鏈入end1之后 end1link = new DoubleQueueNodeType ( item, end1link )。 end1 = end1link。 //創(chuàng)建循環(huán)鏈表的表頭結(jié)點(diǎn) assert ( !end1 || !end2 )。 } //判隊(duì)列空否 private: QueueNodeType *end1, *end2。 //從隊(duì)列end2端插入 Type DeDoubleQueue