实验二 栈和队列.docx
《实验二 栈和队列.docx》由会员分享，可在线阅读，更多相关《实验二 栈和队列.docx（12页珍藏版）》请在冰点文库上搜索。
实验二栈和队列
实验二栈和队列
一、实验目的
1.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
2.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
二、栈和队列的顺序存储结构
在教材中,我们给出了栈的链表存储结构和队列的链表存储结构及实现,下面给出的是栈的顺序存储结构及实现和队列的顺序存储结构及实现。
1．栈的顺序存储结构及实现C++语言源程序。
//---------------------------------------------------------------------------//栈的顺序存储结构，顺序表类
#include
//------------------------栈的顺序存储结构--------------------------------typedefintElemType;//数据元素的类型为int
constintMAXSIZE=100;//数组的容量
classSqStack
{private:
ElemTypeelem[MAXSIZE];
inttop;
public:
SqStack（void）;
~SqStack（）{};
intSqStack:
:
SetEmpty（）;
voidSqStack:
:
push（ElemTypee）;
ElemTypeSqStack:
:
pop（）;
voidSqStack:
:
PrintOut（）;
intSqStack:
:
IsEmpty（void）const;
};
//-------------------------------------------------------------SqStack:
:
SqStack（void）:
top（0）{}
intSqStack:
:
SetEmpty（）
{returntop==0;
}
voidSqStack:
:
push（ElemTypee）
{if（top==MAXSIZE-1）cout<<"\n栈满溢出"<}
ElemTypeSqStack:
:
pop（）
{{ElemTypex;
if（top==0）{
cout<<"\n栈为空，不能进行出栈操作"<x=0;//表示未曾出栈
}
else{x=elem[top];
top--;
}
returnx;
}//出栈
voidSqStack:
:
PrintOut（）
{intk;
cout<<"\nPrintOutData:
\n";
for（k=top;k>=1;k--）cout<cout<}
intSqStack:
:
IsEmpty（void）const
{if（top==0）return1;
elsereturn0;
}
//---------------------------------------------------------------------------intmain（intargc,char*argv[]）
{inti,k;
ElemTypee,x;
SqStackas;
cout<<"\n顺序表存储结构演示";
do{
cout<<"\n\n";
cout<<"\n\n1.插入一个数据元素e（入栈）";
cout<<"\n\n2.删除一个元素，返回其值（出栈）";cout<<"\n\n3..结束程序";
cout<<"\n********************************";
cout<<"\n请输入你的选择（1,2,3,4,5,6）";cin>>k;switch（k）{
case1:
{cout<<"\n入栈，数据e=?
";
cin>>e;
as.push（e）;
as.PrintOut（）;
}break;
case2:
{cout<<"\n出栈";
x=as.pop（）;
cout<<"\n出栈元素数值="<}break;
default:
break;
}//switch
cout<<"\n---------------------------------";
}while（k>=1&&k<3）;
cout<<"\n再见!
";
cout<<"\n按任意键，返回。
";
_getch（）;return0;
}
//-----------------------------------------------
2．队列的顺序存储结构及实现C++语言源程序。
//---------------------------------------------------------------------------#include
#defineMAXSIZE20
typedefintElemType;
classSeQueue
{private:
ElemTypeelem[MAXSIZE];
intfront,rear;
public:
SeQueue（）;
~SeQueue（）;
voidDisplay（）;
voidAddQ（ElemTypex）;
ElemTypeDelQ（）;
};
SeQueue:
:
SeQueue（）
{front=0;
rear=0;
cout<<"init!
"<}
SeQueue:
:
~SeQueue（）
{};//{delete[MAXSIZE]Q.elem;}
voidSeQueue:
:
Display（）
{ElemTypex;intj=0;
if（rear==front）
{cout<<"QUEUEISFULL!
";}
else{j=front+1;while（j!
=rear+1）
{x=elem[j];cout<}
voidSeQueue:
:
AddQ（ElemTypex）
{if（（rear+1）%MAXSIZE==front）//判断是否满队cout<<"\nQueuisFull!
"<}
ElemTypeSeQueue:
:
DelQ（）
{if（front==rear）//判断队列是否为空{cout<<"\nQueueisEmpty!
"<else{front=（front+1）%MAXSIZE;//出队操作returnelem[front];
}
}
intmain（）
{ElemTypee;intj;
SeQueueh;
intk;
cout<<"\n队列存储结构演示";do{
cout<<"\n\n";
cout<<"\n\n1.初步建立一个队列";
cout<<"\n\n2.输出整个队列";
cout<<"\n\n3.入队";
cout<<"\n\n4.出队";
cout<<"\n\n5.结束程序";
cout<<"\n********************************";
cout<<"\n请输入你的选择（1,2,3,4,5）";
cin>>k;
switch（k）{
case1:
{SeQueue:
:
SeQueue（）;
}break;
case2:
{h.Display（）;
}break;
case3:
{
cout<<"进队data=?
";cin>>e;h.AddQ（e）;
h.Display（）;
}break;
case4:
{e=h.DelQ（）;
if（e!
=-1）
cout<<"出队的结点值是：
"<}break;
default:
break;
}
cout<<"\n---------------------------------";}while（k>=1&&k<5）;
cout<<"\n再见!
";
cout<<"\n按任意键，返回。
";return0;
}
三、实验结果
1.栈的顺序存储结构实验结果图片
<1>初始化前
<2>入栈“365”
<3>出栈“5”———（注意：
是后进先出！
）
<4>结束程序
2.队列的的顺序存储结构实验结果图片
<1>初始化前
<2>入队“520”
<3>出队“5”———（注意：
先进先出！
！
）
<4>输出整个队列
<5>结束程序
四、总结软件设计与实现过程种的经验与体会，进一步的改进设想，可再加入哪些部分？
哪些部分可删除？
哪些部分可合并？
哪些可降低复杂度？
怎样设计能提高其可复用性？
多思考，多总结，才能不断提高程序设计能力。
答：
队列和栈可能是使用频率最高的数据结构。
栈和队列是看成是两种
特殊的线性表。
在铁路调度中用到栈，在民航机票订购系统中用到队列。
它们还广泛应用于各种软件系统。
栈是一种“先进后出”的数据结构。
像是叠盘子，叠在最上面的盘子最先
拿来使用。
在匹配表达式应用中，栈发挥了巨大的作用。
还有经典的汉诺塔问题，如果没有堆栈的帮助，你可不知道要搬碟子搬到什么时候了。
在比如Word里，发生了误操作一点也不需要惊慌，因为Word有“撤消”的功能，可以撤消你之前的操作。
把用户的操作压入栈里，要撤消操作时就从栈弹出最近发生的操作。
这样可以很方便地实现这个功能。
队列是一种“先进先出”的数据结构。
就好像在游戏里，每次接到任务就
把该任务压进任务队列里，要做任务时就从任务队列里取出一个任务，这样哪个任务先接到就先做哪个任务。
何天从
2012年11月21日星期三
升级会员 