栈和队列及其应用7

《栈和队列及其应用7》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、栈和队列及其应用栈和队列通常用来存储程序执行期间产牛的一些临时信息。这两种特殊表结构的共同特点是，只做插入和删除，不做查找，而且所有的插入和删除只在端点进行。栈是一种特殊的表结构，满足先进后出策略(LIFO:lastinfirstout),栈的插入和删除操作只在同一端点进行。可以进行插入的端点叫栈顶(top),另一个端点叫栈底(bottom)。栈的插入操作又叫进栈(push)或压栈，栈删除操作又叫退栈(pop)或岀栈。逬栈栈的结构示意图注意：进栈和退栈可以不定期地、反复交替进行。牛活中类似栈的应用的例子：装药片的小圆桶，军用子弹卡等。思考：假

2、设有编号为1,2,3的3辆车，如果按照编号为1,2,3的顺序入栈，那么可能的出栈顺序有几种情况？？？栈的存储方式：1•顺序存储2.链式存储栈的常见操作(顺序存储方式实现)数组s[M]存储一个栈(M代表栈的容量)，top变量指示栈顶指针(下标)。M二6时:进栈算法：//宏定义#defineM6^defineEMPTY-1voidpushs(ints[],int&top){intx,k;cout«，z请输入要进栈的元素值x「；cin>>x;辻(top二二MT){cout<<栈已经满，进栈失败!z，<

3、;top++;s[top]=x;cout<

4、的插入和删除只在两个端点进行。允许插入的一端交队尾（last），允许删除的一端叫队头（first）o队的插入和删除操作分别称为进队和出队。队结构示意图生活屮队的例子很多：排队上车或购物等。同栈的结构一样，进队和入队操作是不定期地、反复地进行的。队的存储方式：1•顺序存储2.链式存储队的常见操作（顺序存储方式实现）（详见板书）循环队列（详见板书）数据结构---栈和队列栈和队列的基础知识栈：栈是一种特殊的表结构，满足先进后出策略（LIFO:lastinfirstout）,栈的插入和删除操作只在同一端点进行。栈的常见操作：入栈、岀栈（栈空和栈满的判

5、断）队：队又称为队列，是一种特殊的表结构，满足先来先服务策略（FIFO:firstinfirstout），队的插入和删除只在两个端点进行。队的常见操作：入队、出队（队空、队满的判断）数据结构---栈和队列简单应用文字输入(enter.cpp)K问题描述H在文字输入的过程中，出现输入错误是不可避免的，所以需要给用户提供一个改正的方法。我们的方法是这样的：用符号表示前一个字符无效，用符号表示本行之前输入的所有内容无效。比如一个字符串“abcd$bcd”，它的实际内容是“abcbcd”，字符串uabc#abc$$dn的实际内容是“ad”。K输入文件

6、U输入文件名：enter,in文件第一行是一个整数N(1<7V<1OO),表示这个文本文件的行数。Z后N行，每行一个长长的字符串(长度不会超过10000),其中就包括'$'和这样的字符和一些英文字母，没有其它的字符。K输出文件U输岀文件名：enter,out文件屮有个字符串，每个字符串一行，是输入文件的最终结果。K样例输入D2abcd$bcdabc#abc$$dK样例输出Uabcbcdad天使之城(ange1・cpp)K问题描述U天使城有一个火车站，每辆火车都从A方向驶入车站，口再从B方向驶出车站。为了调度火车，火车站设有停放轨一一道，可存放

7、5辆火车。已知从A进入车站顺序为1、2、3……o•x喝©h期纠1现在给你一个调度方案，判断是否可行，如果可行，输出鲨今〃出站顺序。H有以下几种调度方法：日A.将A上的头一辆车驶出B方向B.将A上的头一辆车停入暂停轨道C.将暂停轨道上最外面的车驶岀B方向K输入文件』输入文件：angel,in第一行一个整数N(n<30)表示调度方案步骤数目。下一行一个字符串，有N个大写字母，表示调度方法。K输岀文件》输出文件：angel,out若不可行(暂停站满了还停车、暂停站空了还出车)，则输出一行“No”。若可行，输出一行“Yes”，再输出若干行，每行一个整

8、数，表示车出站序列。K样例输入》6ABBCCAK样例输出UYes1324K样例输入》5BACACK样例输出HNo银行取款（bank・cpp）K问题描述U在现代文明社