栈和队列的运用.doc

《栈和队列的运用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、链栈的5种运算来实现。 4.13停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按达到停车场时间的先后依次从停车场最里面向大门口停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车

3、场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不受停车费，并且仍然保持在便道上的车辆次序。是编程模拟停车场管理。三、算法描述1.第1题的算法实现#include#defineelemtypecharconstmaxsize=1000;classseqstack{public:elemtypestack[maxsize];inttop;voidinistack(){top=0;}voidpush(elemtypex){if(top==maxsize-1)cout

4、<<"overflow";else{top++;stack[top]=x;}}voidpop(){if(top==0)cout<<"underflow";elsetop--;}elemtypegettop(){if(top==0){cout<<"underflow";return0;}elsereturnstack[top];}boolempty(){if(top==0)returntrue;elsereturnfalse;}};voidmain()13{intn,i;elemtypex;seqstackS;S.

5、inistack();cout<<"请输入车厢数";cin>>n;cout<<"请输入"<>x;if(x=='H')cout<#define elemtype charconst ma

6、xsize=1000;elemtype s1[maxsize],s2[maxsize];class seqstack{    public:elemtype stack[maxsize];int top;void inistack(){top=0;}void push(elemtype x){top++;stack[top]=x;}void pop(){top--;}elemtype gettop(){return stack[top];}bool empty(){if(top==0) return true;e

7、lse  return false;}int oper(elemtype op){switch(op){case'+':case'-':return 1;case'*':case'/':return 2;case'(':return 0;default:return 0;}}void change(){elemtype y,ch;top=0;inistack();push('@');int i=0,j=0;ch=s1[i];while(ch!='@'){if(ch==' ') ch=s1[++i];else if

8、(ch=='('){push(ch);ch=s1[++i];}else if(ch==')'){y=gettop();                 while(y!='(') {s2[j++]=y;s2[j++]=' ';pop();y=gettop();} pop();ch=s1[++i];}else if((ch=='+')

9、

10、(ch=='-')

11、

12、(ch=='*