栈和队列的运用

1、实训题三 栈和队列的运用一、实训目的1.掌握栈的数据类型描述及栈的特点。2.掌握栈的顺序和链式两种存储结构的特点及算法描述。3.掌握栈的5种基本运算及算法在不同存储结构上的实现。4.掌握队列的数据类型描述及链式存储结构的特点和算法描述。5.掌握队列的5种基本运算及在链式存储结构上的实现。二、实训内容1. 设车辆厂生产了硬座车厢和软座车厢共n节（混合在一起），要求用顺序栈的5种运算使所有的硬座车厢排列到所有软座车厢的前面。2. 利用栈将中缀表达式转换成等价的后缀表达式。3. 将一个正整数n转换成十六进制，要求用链栈的5种运算来实现。4. 停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出

2、），它只有一个大门可以供车辆进出。车辆按达到停车场时间的先后依次从停车场最里面向大门口停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不受停车费，并且仍然保持在便道上的车辆次序。是编程模拟停车场管理。三、算法描述1.第1题的算法实

3、现#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节车厢代号（H代表硬座车厢，S代表软座车厢）;for(i=1;ix;if(x=H)coutx;else S.push(x);while(!S.empty()x=S.gettop();coutx;S.pop();coutendl;程序的结果：2第2题的算法实现#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;程序的结果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十进制数n的十六进制为;s.decTOhex(n);程序的结果：4第4题的算法实现#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该车将离开，应收停车费:(x.arrtime-y.arrtime)*M元data.num!=x.num)r=p;p=p-next;if(p!=NULL)cout便道上有编号为x.num的车辆endl;cout该车将离开，应收停车费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请输