边第3讲 栈和队列

《边第3讲 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、约瑟夫问题这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。第3章栈和队列迷宫问题迷宫问题取自于心理学古典实验。心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻

2、找通路以到达出口老鼠能够记住已经走过的路，不会反复走重复的路径.栈和队列是限定插入和删除只能在表的“端点”进行的线性表。栈和队列是两种常用的数据类型栈只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)栈(Stack)退栈进栈a1anan-1topbottom1．intLength()const初始条件：栈已存在。操作结果：返回栈元素个数。2．boolEmpty()const初始条件：栈已存在。操作结果：如栈为空，则返回true，否则返回false3．voi

3、dClear()初始条件：栈已存在。操作结果：清空栈。4．voidPrt()const初始条件：栈已存在。操作结果：从栈底到栈顶依次输出栈的每个元素5．voidPush(constElemTypex)初始条件：栈已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……6．ElemTypeTop()初始条件：栈已存在且非空。操作结果：返回栈顶元素。a1a2an……7．voidPop()初始条件：栈已存在且非空。操作结果：删除栈顶元素。a1a2anan-1……栈的应用函数调用表达式计算栈的数组表示—顺序栈top空栈topt

4、optoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptop//文件名SqStack.h#includeusingnamespacestd;template//模板声明，数据元素虚拟类型为TclassSqStack//顺序栈类{private://数据成员intmaxSize;//存储空间容量inttop;//栈顶指针T*s;//顺序栈存储空间首地址public://成员函数SqStack(

5、int);//构造函数，建立空栈,即栈初始化voidPrt();//顺序输出栈中的元素与栈顶指针intflag();//检测顺序栈的状态voidPush(T);//入栈TPop();//退栈TTop();//读栈顶元素};//建立容量为mm的空栈templateSqStack::SqStack(intm){maxSize=m;//存储空间容量s=newT[maxSize];//动态申请存储空间top=0;//栈顶指针为0，即建立空栈return;}//顺序输出栈中的元素与栈顶指针templatev

6、oidSqStack::Prt(){inti;cout<<"top="<0;i--)cout<intSqStack::flag(){if(top==maxSize)return(-1);//存储空间已满，返回-1if(top==0)return(0);//栈为空，返回0return(1);//正常返回1}//入栈templatevoidSqStack::Push

7、(Tx){if(top==maxSize)//存储空间已满，上溢错误{cout<<"Stackoverflow!"<TSqStack::Pop(){Ty;if(top==0)//栈为空，下溢错误{cout<<"Stackunderflow!"<

8、//返回退出栈的元素}//读栈顶元素templateTSqStack::Top(){if(top==0)//栈为空{cout<<"Stackempty!"<