棧和隊列的運用

1、實訓(xùn)題三 棧和隊列的運用一、實訓(xùn)目的1.掌握棧的數(shù)據(jù)類型描述及棧的特點。2.掌握棧的順序和鏈式兩種存儲結(jié)構(gòu)的特點及算法描述。3.掌握棧的5種基本運算及算法在不同存儲結(jié)構(gòu)上的實現(xiàn)。4.掌握隊列的數(shù)據(jù)類型描述及鏈式存儲結(jié)構(gòu)的特點和算法描述。5.掌握隊列的5種基本運算及在鏈式存儲結(jié)構(gòu)上的實現(xiàn)。二、實訓(xùn)內(nèi)容1. 設(shè)車輛廠生產(chǎn)了硬座車廂和軟座車廂共n節(jié)（混合在一起），要求用順序棧的5種運算使所有的硬座車廂排列到所有軟座車廂的前面。2. 利用棧將中綴表達式轉(zhuǎn)換成等價的后綴表達式。3. 將一個正整數(shù)n轉(zhuǎn)換成十六進制，要求用鏈棧的5種運算來實現(xiàn)。4. 停車場管理。設(shè)有一個可以停放n輛汽車的狹長停車場（先進后出

2、），它只有一個大門可以供車輛進出。車輛按達到停車場時間的先后依次從停車場最里面向大門口停放（最先到達的第一輛車停放在停車場的最里面）。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車離開，則排在便道上的第一輛車就可以進入停車場。停車場內(nèi)如有有某輛車要離開，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車再按原來的次序進停車場。每輛車在離開停車場時，都應(yīng)根據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車沒進停車場就要離開，允許其離開，不受停車費，并且仍然保持在便道上的車輛次序。是編程模擬停車場管理。三、算法描述1.第1題的算法實

3、現(xiàn)#include#define elemtype charconst maxsize=1000;class seqstackpublic:elemtype stackmaxsize;int top;void inistack()top=0;void push(elemtype x)if(top=maxsize-1)coutoverflow;elsetop+;stacktop=x;void pop()if(top=0)coutunderflow;else top-;elemtype gettop()if(top=0)coutunderflow;return 0;else return stac

4、ktop;bool empty()if(top=0)return true;else return false;void main()int n,i;elemtype x;seqstack S;S.inistack();coutn;cout請輸入n節(jié)車廂代號（H代表硬座車廂，S代表軟座車廂）;for(i=1;ix;if(x=H)coutx;else S.push(x);while(!S.empty()x=S.gettop();coutx;S.pop();coutendl;程序的結(jié)果：2第2題的算法實現(xiàn)#include#defineelemtypecharconstmaxsize=1000;el

5、emtypes1maxsize,s2maxsize;classseqstackpublic:elemtypestackmaxsize;inttop;voidinistack()top=0;voidpush(elemtypex)top+;stacktop=x;voidpop()top-;elemtypegettop()returnstacktop;boolempty()if(top=0)returntrue;elsereturnfalse;intoper(elemtypeop)switch(op)case+:case-:return1;case*:case/:return2;case(:retu

6、rn0;default:return0;voidchange()elemtypey,ch;top=0;inistack();push();inti=0,j=0;ch=s1i;while(ch!=)if(ch=)ch=s1+i;elseif(ch=()push(ch);ch=s1+i;elseif(ch=)y=gettop();while(y!=()s2j+=y;s2j+=;pop();y=gettop();pop();ch=s1+i;elseif(ch=+)|(ch=-)|(ch=*)|(ch=/)y=gettop();if(oper(ch)oper(y)push(ch);ch=s1+i;el

7、sey=gettop();s2j+=y;s2j+=;pop();elsewhile(ch=0)&(ch=9)|(ch=.)s2j+=ch;ch=s1+i;s2j+=;y=gettop();while(y!=)s2j+=y;s2j+=;pop();y=gettop();s2j=;voidmain()seqstacks;elemtypech;inti=0;coutch;while(ch!=)s1i+=ch;cinch;s1i=;cout中綴表達式為:endl;for(intj=0;ji;j+)couts1j;coutendl;s.change();cout后綴表達式為:endl;j=0;while

8、(s2j!=)couts2j;j+;coutendl;程序的結(jié)果3第3題的算法運算#include#define elemtype charclass linkpublic:elemtype data;link *next;class linkstackpublic:link *top;void inistack()top=new link;top-next=NULL;void push(elemtype x)link *s=new link;s-data=x;s-next=top-next;top-next=s;void pop()link *s=top-next;if(s!=NULL)to

9、p-next=s-next;delete s;elemtype gettop()if(top-next!=NULL)return(top-next-data);else return NULL;bool empty ()if(top-next=NULL) return true;else return false;void decTOhex(int n)elemtype x;inistack();while(n);int j=n%16;if(j10) x=j+48;else x=j+55;push(x);n=n/16;while(!empty()x=gettop();coutx;pop();c

10、outendl;void main()int n;linkstack s;coutn;cout十進制數(shù)n的十六進制為;s.decTOhex(n);程序的結(jié)果：4第4題的算法實現(xiàn)#includeconst int N=5;const int M=6;typedef structint num;int arrtime; elemtype;struct seqstackelemtype stackN+1;int top;s1,s2;struct linkelemtype data;link *next;struct linkqueuelink *front,*rear;q;seqstack inis

11、tack(seqstack S)S.top=0;return S;seqstack push(seqstack S,elemtype x)S.top+;S.stackS.top=x;return S;seqstack pop(seqstack S)S.top-;return S;elemtype gettop(seqstack S)return S.stackS.top;int empty(seqstack S)if(S.top=0)return 1;else return 0;linkqueue iniqueue(linkqueue s)link *p;p=new link;p-next=N

12、ULL;s.front=s.rear=p;return s;linkqueue enqueue(linkqueue s,elemtype x)link *p;p=new link;p-data=x;p-next=s.rear-next;s.rear-next=p;s.rear=p;return s;linkqueue dlqueue(linkqueue s)link *p=s.front;s.front=p-next;delete p;return s;elemtype gethead(linkqueue s)return s.front-next-data;int emptyqueue(li

13、nkqueue s)if(s.front=s.rear)return 1;else return 0;void arrive(elemtype x)if(s1.top=N)q=enqueue(q,x);else s1=push(s1,x);void delive(elemtype x)int f=1;elemtype y;link *r;while(!empty(s1)&(f=1)if(s1.stacks1.top.num!=x.num)y=gettop(s1);s1=pop(s1);s2=push(s2,y);elsef=0;y=gettop(s1);s1=pop(s1);cout停車場中有

14、編號為x.num的車endl;cout該車將離開，應(yīng)收停車費:(x.arrtime-y.arrtime)*M元data.num!=x.num)r=p;p=p-next;if(p!=NULL)cout便道上有編號為x.num的車輛endl;cout該車將離開，應(yīng)收停車費0.00元:next=p-next;delete p;elsecout便道上沒有編號為x.num的車輛，輸入的車輛不存在!endl;void pr1()int t=s1.top;cout停車場中的車輛編號和到達時間endl;while(t!=0)couts1.stackt.num s1.stackt.arrtimeendl;t-;coutnext;cout便道中的車輛編號和到達時間endl;while(p!=NULL)coutdata.num data.arrtimenext;coutendl;void main()int n;elemtype x;s1=inistack(s1);s2=inistack(s2);q=iniqueue(q);while(1)coutendl;cout請輸