【正文】 2端逆時針進棧循環(huán)隊列類定義 include template class Type class DoubleQueue { //循環(huán)隊列的類定義 public: DoubleQueue ( int=10 )。 Type DeQueue (const int end )。 } //判兩隊列空否 int IsFull ( ) const { return (end1+1) % m == end2。 //隊列最大可容納元素個數(shù) } 構(gòu)造函數(shù) template class TypeDoubleQueueType:: DoubleQueue ( int sz ) : end1 (0), end2 (0), m (sz) { //建立一個最大具有m個元素的空隊列。item, const int end ) { assert ( !IsFull ( ) )。 //end2端先進隊列, 指針再進1 end2 = ( end2 1 + m ) % m。if ( end == 1 ) { temp = V[end1]。 //end2端指針先退1。 temp。試編寫基于此結(jié)構(gòu)的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿的條件。 //數(shù)據(jù)域 DoubleQueueNodeType *link。 //析構(gòu)函數(shù) void EnDoubleQueue1 ( const Typeamp。 //從隊列end2端插入 Type DeDoubleQueue ( )。 } //判隊列空否 private: QueueNodeType *end1, *end2。 //創(chuàng)建循環(huán)鏈表的表頭結(jié)點 assert ( !end1 || !end2 )。 end1 = end1link。 else //隊列不空, 新結(jié)點鏈入end1之后 end1link = new DoubleQueueNodeType ( item, end1link )。 return 0。 delete p。 return end1linkdata。 delete p?！窘獯稹?Bag類的定義templateclass Type class Bag {public: Bag ( int sz = DefaultSize )。 //插入函數(shù) virtual Type *Remove ( )。 } virtual void Full ( ) { cerr “DataStructure is full.” endl。 //數(shù)組當前元素個數(shù)}。} Bag類的插入函數(shù)templateclass Type void BagType :: Add ( const Type amp。 return NULL。 i top。x。 //刪除函數(shù)}。 x = elements [ top ]。 //構(gòu)造函數(shù) ~Queue ( )。 //刪除函數(shù) } 優(yōu)先級隊列的構(gòu)造函數(shù) template class Type PQueueType :: PQueue ( int sz ) : Bag ( sz ) { } //建立一個最大具有sz個元素的空優(yōu)先級隊列。 return NULL。 for ( int i = 1。 } elements[minindex] = elements[top]。 //返回最小元素的值 }415 試利用優(yōu)先級隊列實現(xiàn)棧和隊列。 value, int newpriority, PQueueType * next ) : data ( value ), priority ( newpriority ), link ( next ) { } //構(gòu)造函數(shù) virtual Type GetData ( ) { return data。 value ) { data = value。 //數(shù)據(jù) int priority。 } //析構(gòu)函數(shù) virtual void Insert ( Typeamp。 //讀取隊頭元素的值 virtual void MakeEmpty ( )。templateclass Type void PQueueType :: MakeEmpty ( ) { //將優(yōu)先級隊列置空 PQueueNodeType *q。 } //循鏈逐個刪除 rear = NULL。 //隊列空時新結(jié)點為第一個結(jié)點 else { PQueueNodeType *p = front, *pr = NULL。 p = plink。 prlink = q。 front = frontlink。 if ( front == NULL ) rear = NULL。 else return frontdata。 value ) { //插入函數(shù) PQueueNodeType * q = new PQueueNode ( value, 0, NULL )。 } //插入在前端 } (2) 隊列的定義與實現(xiàn) template class Type class Queue : public PQueue { //隊列類定義 public: Queue ( ) : front ( NULL ), rear ( NULL ) { } //構(gòu)造函數(shù) void Insert ( Typeamp。 if ( IsEmpty ( ) ) front = rear = q。試編寫一個算法，以判斷一個串是否是回文。 while ( A[i] != “\0” ) { ( A[i] )。 i++。}【解答2】 采用遞歸算法，判斷從s到e中的字符串是否回文，通過函數(shù)返回是或不是。}416 設(shè)有一個雙端隊列，元素進入該隊列的順序是1, 2, 3, 4。 end1 end2輸出受限的雙端隊列 end1 end2輸入受限的雙端隊列 輸出受限雙端隊列不能得到的輸出序列有： 4 1 3 2 4 2 3 1 輸人受限雙端隊列不能得到的輸出序列有： 4 2 1 3 4 2 3 1 所以有：(1) 4 1 3 2(2) 4 2 1 3(3) 4 2 3 1 34。 (1) 能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列； (2) 能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列； (3) 既不能由輸入受限的雙端隊列得到，又不能由輸出受限的雙端隊列得到的輸出序列。 else if ( s e ) return 1。 break。 } //掃描字符串，所有字符進棧 i = 0。算法如下：int palindrome ( char A[ ], int n ) { stackchar st (n+1)。 //插入在隊尾位置 }415 所謂回文，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。 //插入新元素value到隊尾 }templateclass Type void QueueType :: Insert ( Type amp。 //?？諘r新結(jié)點為第一個結(jié)點 else { qlink = front。 value )。 retvalue。retvalue = qdata。 } } templateclass Type Type PQueueType :: Remove ( ) { //刪除隊頭元素并返回 if ( IsEmpty ( ) ) return NULL。 front = q。amp。 value, int newpriority ) { //插入函數(shù) PQueueNodeType *q = new PQueueNode ( value, newpriority, NULL )。 front = frontlink。 } //判隊列空否 private: PQueueNodeType *front, *rear。 //插入新元素value到隊尾 virtual Type Remove ( )。 //鏈指針 }。 } //修改結(jié)點優(yōu)先級 virtual void SetLink ( PQueueNodeType * next ) { link = next。 } //取得結(jié)點優(yōu)先級 virtual PQueueNodeType * GetLink ( ) { return link。 //前視的類定義 template class Type class PQueueNode { //優(yōu)先級隊列結(jié)點類的定義 friend class PQueueType。 returnamp。 i++ ) if ( elements[i] min ) { min = elements[i]。 min = elements[0]。 優(yōu)先級隊列的刪除函數(shù) template class Type Type *PQueueType :: Remove ( ) { //若優(yōu)先級隊列不空則函數(shù)返回該隊列具最大優(yōu)先權(quán)(值最小)元素的值, 同時將該元素刪除。 隊列的構(gòu)造函數(shù)templateclass Type QueueType :: Queue ( int sz ) : Bag ( sz ) { }//隊列的構(gòu)造函數(shù)Queue將調(diào)用Bag的構(gòu)造函數(shù) 優(yōu)先級隊列的類定義（繼承Bag類） template class Type class PQueue : public Bag { public: PQueue ( int sz = DefaultSize )。x。 return NULL。 //構(gòu)造函數(shù) ~Stack ( )。 top。 x = elements [0]。 else elements [ ++top ] = item。 top = 1。 //存儲數(shù)組 int maxSize。 } //判空函數(shù) virtual int IsFull ( ) { return top == maxSize 1。 //析構(gòu)函數(shù) virtual void Add ( const Typeamp。寫出各個類的聲明。 //逐個刪除隊列中的結(jié)點, 包括表頭結(jié)點 while ( end1 != end1link ) { p = end1。 return retvalue。 //被刪除結(jié)點 end1link = plink。 item ) { end2 = end2link = new DoubleQueueNodeType ( item, end1 )。 } } 隊列的插入函數(shù) templateclass Type //從隊列end1端插入void DoubleQueueType :: EnDoubleQueue1 ( const Typeamp。 }隊列的析構(gòu)函數(shù) template class Type QueueT