2022年栈和队列的基本操作实现及其应资料 .pdf

《2022年栈和队列的基本操作实现及其应资料 .pdf》由会员分享，可在线阅读，更多相关《2022年栈和队列的基本操作实现及其应资料 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、题目三、Rails Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could

2、be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N = 1

3、000 coaches numbered in increasing order 1, 2, ., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ., aN. Help him and write a program that decides whether it is possible to get the required o

4、rder of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the statio

5、n. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. Input The input consists of blocks of lines. Each block except the last describes one train and possibly more re

6、quirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output The output

7、contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corres

8、ponding to one block of the input. There is no line in the output corresponding to the last null block of the input. Sample Input 5 1 2 3 4 5 5 4 1 2 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 0 6 6 5 4 3 2 1 0 0 Sample Output Yes No

9、 Yes 程序清单：（STL标准模板库）一、#include #include #include using namespace std; int a1001,n,i,j; int fan() stacks; / 火车是按（ 1-n）的顺序进栈inti,j; for(i=0,j=1;in&j=n+1;) if(s.empty()|s.top()!=ai)/ 栈空或栈顶元素不与ai相同时进站 if(j=(n+1) / 不能正常出站条件return 0; / 不能正常出站返回0 s.push(j+); / 将 j 压入栈中 else / 栈顶元素与 ai相同时进站 s.pop(); / 弹出栈顶元

10、素i+; /i+ ，a 的下个元素继续进行 return 1; /* fan()解释：1-n 和 an的每个元素进行比较。用 j=1，j+表示 1n 的每个元素用 ai（0=in）表示 ai的每个元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 如果栈为空时让j 进栈，然后 j+。如果栈顶元素与ai不相同，让 j 进栈，然后 j+。如果栈顶元素与ai相同，弹出栈顶元素，然后i+。结束条件： 1、j=(n+1)时表示不能按给出

11、的顺序出站，则返回0 2、循环结束返回1 */ int main() while(scanf(%d,&n),n)/ 有多少辆火车，以0 结束。 while(scanf(%d,&a0),a0) / 输入出站次序，以0 结束 for(i=1;in;i+) scanf(%d,&ai); / 把出站次序放在数组a 中。if(fan() printf(Yesn); / 可以出站输出 Yes else printf(Non); / 不可以正常出站输出No return 0; 运行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心

12、整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 二、#include #include #include using namespace std; int a1001,n,i,j,k; int fan() stacks; inti,j=0,k; for(i=1;i=n;i+) if(aj=i) / 当 aj与 i 相同时 j+; / 进行下一个 a 中的元素while(!s.empty()/栈不空时 k=s.top(); / 得到栈顶元素s.pop(); / 弹出栈顶元素if(k=aj) / 栈顶元素与 aj相同，继续进行下一个j+; else /

13、 栈顶元素与 aj不同时 s.push(k); / 把 k 再压入栈中break; /if 语句结束。 else / 当 aj与 i 不相同时把 i 压入栈中s.push(i); if(s.empty() / 栈空返回 1 return 1; else / 栈不空返回 0 return 0; int main() while(scanf(%d,&n),n) while(scanf(%d,&a0),a0) for(i=1;in;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4

14、 页，共 5 页 - - - - - - - - - scanf(%d,&ai); if(fan() printf(Yesn); else printf(Non); return 0; /* 主要解释一下 fan() 1-n 和 an的每个元素进行比较。用 i=1，i+表示 1n 的每个元素用 aj（0=jn）表示 aj的每个元素。当 aj与 i 相同时， j+，让栈顶元素继续与aj比较，直到 aj与栈顶元素不同当 aj与 i 相同时将 i 压入栈中。结束条件： 1、最后栈空，返回1（可以按所给的顺序出站）2、栈不空，返回0（不可以按所给的顺序出站）*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -