栈和队列及其应用7

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

2、按照编号为1, 2, 3的顺序入 栈，那么可能的出栈顺序有几种情况？ ？ ？栈的存储方式：1 顺序存储2.链式存储栈的常见操作(顺序存储方式实现)数组sm存储一个栈(m代表栈的容量)，top变量指示栈顶指针(下标)。 m二 6 时:进栈算法：/宏定义#define m 6define empty -1void pushs (int s, int &top)int x, k;cout«，z请输入要进栈的元素值x；cin>>x;辻(top 二二mt)cout<<栈已经满，进栈失败!z，<<endl; return;/s+top;top+;sto

3、p=x;cout<<x<<"已成功进栈! /z<<endl;出栈算法：void pops(int s, int &top)int x, k;if (top二二empty)cout«/z栈已经空，退栈失败!，z«endl;return ;/x=stop-;x=stop;top;cout<<，z 已退栈顶元素，z<<x<<endl;课堂实践：结合入栈和出栈算法完成入栈、出栈、显示栈的当前元素程序（stack, cpp） o队又称为队列，是一种特殊的表结构，满足先来先服务策略（fif0:fi

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

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

6、数n (1<7v<1oo),表示这个文本文件的行数。z后n 行，每行一个长长的字符串(长度不会超过10000),其中就包括'$'和 这样的字符和一些英文字母，没有其它的字符。k输出文件u输岀文件名：enter, out文件屮有个字符串，每个字符串一行，是输入文件的最终结果。k样例输入d2abcd$bcdabc#abc$dk样例输出uabcbcd ad天使之城(ange1 cpp)k问题描述u天使城有一个火车站，每辆火车都从a方向驶入车站，口再从b方向驶出车站。为了调度火车，火车站设有停放轨一一 道，可存放5辆火车。已知从a进入车站顺序为1、2、3o x 喝©

7、;h期纠1 现在给你一个调度方案，判断是否可行，如果可行，输出鲨今出站顺序。h有以下几种调度方法：日a. 将a上的头一辆车驶出b方向b. 将a上的头一辆车停入暂停轨道c. 将暂停轨道上最外面的车驶岀b方向k输入文件输入文件：angel, in第一行一个整数n (n<30)表示调度方案步骤数目。下一行一个字符串，有n个大写字母，表示调度方法。k输岀文件输出文件：angel, out若不可行(暂停站满了还停车、暂停站空了还出车)，则输出一行“no”。若可行，输出一行“yes”，再输出若干行，每行一个整数，表示车出站序列。 k样例输入6abbccak样例输出uyes1324k样例输入5baca

8、ck样例输出hno银行取款（bank cpp）k问题描述u在现代文明社会中，大家在诸如银行办理业务、车站买票等活动时都很文明 没有插队的现象，本着“先来先服务”的规矩。五一马上到了，凡凡的爸爸打算上银行去取点钱，带着一向表现很好的凡凡 同学到海南旅游，凡凡的爸爸到银行时发现很多人在办理业务，凡凡的爸爸就自 觉地在排队机上去了一个业务号码，并焦急的等待着银行柜台叫自己的号 码k输入文件为输入文件名：bank, in输入中包含i （表示等待办理业务）和顾客的序号；或者0 （表示办理完业务的人离开）；输入数据不超过100行。k输出文件输出文件名:bank, out输岀银行排队中岀队顾客序列，若队列为空（没人等待），则输岀“none” k样例输入0i 1i 201 300