【正文】 ( ) )。 //end2端指針先退1。 } else { end2 = ( end2 + 1 ) % m。if ( end == 1 ) { temp = V[end1]。 Typeamp。 //end2端先進(jìn)隊(duì)列, 指針再進(jìn)1 end2 = ( end2 1 + m ) % m。 //end1端指針先進(jìn)1, 再按指針進(jìn)棧 V[end1] = item。item, const int end ) { assert ( !IsFull ( ) )。 //創(chuàng)建隊(duì)列空間 assert ( V != 0 )。 //隊(duì)列最大可容納元素個(gè)數(shù) } 構(gòu)造函數(shù) template class TypeDoubleQueueType:: DoubleQueue ( int sz ) : end1 (0), end2 (0), m (sz) { //建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。 //隊(duì)列兩端的指針 Type *V。 } //判兩隊(duì)列空否 int IsFull ( ) const { return (end1+1) % m == end2。 void MakeEmpty ( ) { end1 = end2 = 0。 Type DeQueue (const int end )。 } void EnQueue ( Type amp。 //設(shè)end1端順時(shí)針進(jìn)棧，end2端逆時(shí)針進(jìn)棧循環(huán)隊(duì)列類(lèi)定義 include template class Type class DoubleQueue { //循環(huán)隊(duì)列的類(lèi)定義 public: DoubleQueue ( int=10 )。end1 隊(duì)空條件 end1 = end2。試寫(xiě)出雙端隊(duì)列所用指針end1和end2的初始化條件及隊(duì)空與隊(duì)滿(mǎn)條件，并編寫(xiě)基于此結(jié)構(gòu)的相應(yīng)的插入(enqueue)新元素和刪除(dlqueue)算法。 //返回?cái)?shù)據(jù)存放地址 } 隊(duì)空條件 p == NULL。 delete s。 //隊(duì)頭結(jié)點(diǎn)為p后一個(gè)結(jié)點(diǎn) plink = slink。 return 0。 p = plink = s。 } else { //隊(duì)列不空, 新結(jié)點(diǎn)鏈入p之后QueueNodeType *s = new QueueNodeType ( item, NULL )。 item ) { if ( p == NULL ) { //隊(duì)列空, 新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)p = new QueueNodeType ( item, NULL )。 delete s。 while ( p != NULL ) { s = p。 //隊(duì)尾指針（在循環(huán)鏈表中） }。 //置空隊(duì)列，實(shí)現(xiàn)與~Queue ( ) 相同 int IsEmpty ( ) const { return p == NULL。 //刪除并返回隊(duì)頭元素 Type GetFront ( )。 item )。 template class Type class Queue { //鏈?zhǔn)疥?duì)列類(lèi)定義 public: Queue ( ) : p ( NULL ) { } //構(gòu)造函數(shù) ~Queue ( )。 //數(shù)據(jù)域 QueueNodeType *link。 //鏈?zhǔn)疥?duì)列類(lèi)的前視定義 template class Type class QueueNode { //鏈?zhǔn)疥?duì)列結(jié)點(diǎn)類(lèi)定義 friend class QueueType。試基于此結(jié)構(gòu)給出隊(duì)列的插入(enqueue)和刪除(dequeue)算法，并給出p為何值時(shí)隊(duì)列空。 //判斷隊(duì)列是否不空，空則出錯(cuò)處理return Q[(front + 1) % m]。 //標(biāo)志改0, 表示棧不滿(mǎn)return Q[front]。 //判斷隊(duì)列是否不空，空則出錯(cuò)處理 front = ( front + 1 ) % m。 //進(jìn)隊(duì)列 tag = 1。 //判隊(duì)列是否不滿(mǎn)，滿(mǎn)則出錯(cuò)處理 rear = ( rear + 1 ) % m。 //斷言: 動(dòng)態(tài)存儲(chǔ)分配成功與否 } 插入函數(shù) templateclass Type void QueueType :: EnQueue ( Type amp。 Q = new Type[m]。 //存放隊(duì)列元素的數(shù)組 int m。 } //判隊(duì)列滿(mǎn)否 private: int rear, front, tag。amp。 tag == 0。 } //置空隊(duì)列 int IsEmpty ( ) const { return front == rear amp。 Type GetFront ( )。 item )。 ~Queue ( ) { delete [ ] Q。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。return elements[(rearlength+1+maxSize) % maxSize]。 //隊(duì)列長(zhǎng)度減1return elements[(rearlength+maxSize) % maxSize]。 //進(jìn)隊(duì)列 } 刪除函數(shù) templateclass Type Type QueueType :: DeQueue ( ) { assert ( ! IsEmpty ( ) )。 //長(zhǎng)度加1rear = ( rear +1) % maxSize。item ) { assert ( ! IsFull ( ) )。 //創(chuàng)建隊(duì)列空間 assert ( elements != 0 )。 //隊(duì)列最大可容納元素個(gè)數(shù) } 構(gòu)造函數(shù) template class TypeQueueType:: Queue ( int sz ) : rear (maxSize1), length (0), maxSize (sz) { //建立一個(gè)最大具有maxSize個(gè)元素的空隊(duì)列。 //隊(duì)尾指針和隊(duì)列長(zhǎng)度 Type *elements。 } //判隊(duì)列空否 int IsFull ( ) const { return length == maxSize。 void MakeEmpty ( ) { length = 0。 Type DeQueue ( )。 } void EnQueue ( Type amp。【解答】循環(huán)隊(duì)列類(lèi)定義 include template class Type class Queue { //循環(huán)隊(duì)列的類(lèi)定義 public: Queue ( int=10 )。49 假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素, 同時(shí)以rear和length分別指示環(huán)形隊(duì)列中的隊(duì)尾位置和隊(duì)列中所含元素的個(gè)數(shù)。 ’ ) == isp (‘ 。 ’ ) isp (‘ ’ ), 退OPND棧 ‘s5’, 退OPND 棧 ‘s3’, 退OPTR棧 ‘ ’, 計(jì)算 s3 – s5 → s6, 結(jié) 果進(jìn)OPND棧s6。 ’ ) isp (‘ / ’ ), 退OPND棧 ‘g’, 退OPND 棧 ‘s4’, 退OPTR棧 ‘/’, 計(jì)算 s4 / g → s5, 結(jié)果 進(jìn)OPND棧s3 s5。 /20。 18同上同上F icp (‘ / ’ ) isp (‘ ’ ), 進(jìn)OPTR棧, 取下一符號(hào)s3 s4。 ↑16f操作數(shù)F f 進(jìn)OPND棧, 取下一符號(hào)s3 e f。 14e操作數(shù)F e 進(jìn)OPND棧, 取下一符號(hào)s3 e。 13同上同上F icp (‘ ’ ) isp (‘ 。 + * 11操作符F icp (‘ ’ ) isp (‘ * ’ ), 退OPND棧 ‘s1’, 退OPND 棧 ‘b’, 退OPTR棧 ‘*’, 計(jì)算 b * s1 → s2, 結(jié)果進(jìn) OPND棧a s2。 + * ( 9)操作符F icp (‘ ) ’ ) isp (‘ ’ ), 退OPND棧 ‘d’, 退OPND 棧 ‘c’, 退OPTR棧 ‘’, 計(jì)算 c – d → s1, 結(jié)果進(jìn) OPND棧a b s1。 + * (7操作符F icp (‘ ’ ) isp (‘ ( ’ ), 進(jìn)OPTR棧, 取下一符號(hào)a b。 + *5(操作符F icp (‘ ( ’ ) isp (‘ * ’ ), 進(jìn)OPTR棧, 取下一符號(hào)a b。 +3b操作數(shù)F b 進(jìn)OPND棧, 取下一符號(hào)a b。2+操作符F icp (‘ + ’ ) isp (‘ ?！?進(jìn)OPTR棧, 取第一個(gè)符號(hào)。 ① 如果ch是運(yùn)算對(duì)象，進(jìn)OPND棧，從中綴表達(dá)式取下一字符送入ch； ② 如果ch是運(yùn)算符，比較ch的優(yōu)先級(jí)icp(ch)和OPTR棧頂運(yùn)算符isp(OPTR)的優(yōu)先級(jí)： F 若icp(ch) isp(OPTR)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一字符送入ch； F 若icp(ch) isp(OPTR)，則從OPND棧退出一個(gè)運(yùn)算符作為第2操作數(shù)a2，再退出一個(gè)運(yùn)算符作為第1操作數(shù)a1，從OPTR棧退出一個(gè)運(yùn)算符θ形成運(yùn)算指令 (a1)θ(a2)，執(zhí)行結(jié)果進(jìn)OPND棧； F 若icp(ch) == isp(OPTR) 且ch == “)”，則從OPTR棧退出棧頂?shù)摹?”，對(duì)消括號(hào)，然后從中綴表達(dá)式取下一字符送入ch；根據(jù)以上規(guī)則，給出計(jì)算a + b * (c d) e↑f / g時(shí)兩個(gè)棧的變化?！睍r(shí)，執(zhí)行以下工作，否則結(jié)束算法?！?2) 從頭掃描中綴表達(dá)式，取一字符送入ch。 a + b * (c d) e↑f / g 【解答】 設(shè)在表達(dá)式計(jì)算時(shí)各運(yùn)算符的優(yōu)先規(guī)則如上一題所示。 ), 退棧輸出。 。 39。 ), 退棧輸出。 。 / 39。 ), 退棧輸出。 ?！?9。 /↑a x * b x 2 10 。 ), 進(jìn)棧, 讀下一符號(hào)。 ) icp ( 39。 /a x * b x 8 ↑操作符F isp ( 39。 ), 進(jìn)棧, 讀下一符號(hào) 。 ) icp ( 39。 a x * b 6 /操作符F isp ( 39。 ), 進(jìn)棧, 讀下一符號(hào)。 ) icp ( 39。 。 ), 退棧輸出。 ) icp ( 39。 *a x 4 操作符F isp ( 39。 ), 進(jìn)棧, 讀下一符號(hào)。 ) icp ( 39。 。 1 a操作數(shù)F 直接輸出, 讀下一符號(hào)。39。然后將“(”退棧以對(duì)消括號(hào)，后者將結(jié)束算法。”號(hào)配對(duì)時(shí)。運(yùn)算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)“)”或棧底的“。從表中可知，icp(“(”)最高，但當(dāng)“(”進(jìn)棧后，isp(“(”)變得極低。 ( ^ *,/, % +, ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1 isp也叫做棧內(nèi)(in stack priority)優(yōu)先數(shù)，icp也叫做棧外(