第一篇：實(shí)驗(yàn)報(bào)告——棧和隊(duì)列的應(yīng)用

實(shí)驗(yàn)5 棧和隊(duì)列的應(yīng)用

目的和要求：

（1）熟練棧和隊(duì)列的基本操作；（2）能夠利用棧與隊(duì)列進(jìn)行簡(jiǎn)單的應(yīng)用。

一、題目

題目1.利用順序棧和隊(duì)列，實(shí)現(xiàn)一個(gè)棧和一個(gè)隊(duì)列，并利用其判斷一個(gè)字符串是否是回文。所謂回文，是指從前向后順讀和從后向前倒讀都一樣的字符串。例如，a+b&b+a等等。

題目2.假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲?，F(xiàn)要求寫(xiě)一算法模擬上述舞伴配對(duì)問(wèn)題，并實(shí)現(xiàn)。

題目3.打印機(jī)提供的網(wǎng)絡(luò)共享打印功能采用了緩沖池技術(shù)，隊(duì)列就是實(shí)現(xiàn)這個(gè)緩沖技術(shù)的數(shù)據(jù)結(jié)構(gòu)支持。每臺(tái)打印機(jī)具有一個(gè)隊(duì)列（緩沖池），用戶(hù)提交打印請(qǐng)求被寫(xiě)入到隊(duì)列尾，當(dāng)打印機(jī)空閑時(shí)，系統(tǒng)讀取隊(duì)列中第一個(gè)請(qǐng)求，打印并刪除之。請(qǐng)利用隊(duì)列的先進(jìn)先出特性，完成打印機(jī)網(wǎng)絡(luò)共享的先來(lái)先服務(wù)功能。

題目4.假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素, 同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag == 0和tag == 1來(lái)區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿(mǎn)”。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。

題目5.利用循環(huán)鏈隊(duì)列求解約瑟夫環(huán)問(wèn)題。

請(qǐng)大家從本組未討論過(guò)的五道題中選擇一道，參照清華鄧俊輝老師MOOC視頻及課本相關(guān)知識(shí)，編寫(xiě)相應(yīng)程序。

選擇題目3：

打印機(jī)提供的網(wǎng)絡(luò)共享打印功能采用了緩沖池技術(shù)，隊(duì)列就是實(shí)現(xiàn)這個(gè)緩沖技術(shù)的數(shù)據(jù)結(jié)構(gòu)支持。

二、程序清單

//Ch3.cpp #include #include #include“ch3.h” template void LinkedQueue::makeEmpty()//makeEmpty//函數(shù)的實(shí)現(xiàn) { LinkNode*p;while(front!=NULL)//逐個(gè)刪除隊(duì)列中的結(jié)點(diǎn)

{

p=front;

front=front->link;

delete p;} };template bool LinkedQueue::put_in(T&x）{//提交命令函數(shù)

if(front==NULL){//判斷是否為空

front=rear=new LinkNode;//如果為空，新結(jié)點(diǎn)為對(duì)頭也為對(duì)尾

front->data=rear->data=x;

if(front==NULL)//分配結(jié)點(diǎn)失敗

return false;} else{

rear->link=new LinkNode;//如不為空，在鏈尾加新的結(jié)點(diǎn)

rear->link->data=x;

if(rear->link==NULL)

return false;

rear=rear->link;} return true;};template bool LinkedQueue::carry_out()//執(zhí)行命令函數(shù) { if(IsEmpty()==true)//判斷是否為空

{

return false;} cout<data<<“ ”;//輸出鏈尾的數(shù)據(jù)，代表執(zhí)行打印命令

LinkNode*p=front;front=front->link;//刪除以執(zhí)行的命令，即對(duì)頭修改

delete p;//釋放原結(jié)點(diǎn)

return true;};void main()

//主函數(shù) { LinkedQueue q;//定義類(lèi)對(duì)象

char flag='Y';

//標(biāo)志是否輸入了命令

const int max=30;//一次獲取輸入命令的最大個(gè)數(shù) while(flag=='Y')//循環(huán) { int i=0;char str[max];//定義存儲(chǔ)屏幕輸入的命令的數(shù)組

gets(str);//獲取屏幕輸入的命令

while(str[i]!='