作者:戊辰冬月半 | 来源:互联网 | 2023-05-19 06:26
【问题描述】某城市有一个火车站,铁轨铺设如图所示。有n节车厢从A方向驶入车站,按进站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,你可以借助中转
【问题描述】
某城市有一个火车站,铁轨铺设如图所示。有n节车厢从A方向驶入车站,按进站顺序编号为1~n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出。对于每个车厢,一旦从A移入C,就不能再回到A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择:A→C和C→B。
这个问题和之前数据结构实验的火车入轨类似,而且较之简化。自己尝试写了下,和书上参考答案的代码量仍有较大差距。代码如下:
1 #include
2 using namespace std;
3 const int MAXSIZE=100;
4 void main()
5 {
6 int n;
7 cin>>n;
8 int a[MAXSIZE],b[MAXSIZE];
9 int stack[MAXSIZE];
10 for(int i=0;i)
11 {
12 a[i]=i+1;
13 cin>>b[i]; //出栈顺序
14 }
15 int top=-1;
16 int count=0;
17 int i=0;
18 for(;;)
19 {
20 if(i<n)
21 {
22 ++top;
23 stack[top]=a[i++]; //入栈
24 cout<<"PUSH"<<endl;
25 }
26
27 if(stack[top]==b[count])
28 {
29 top--;count++;
30 cout<<"POP"<<endl;
31 }
32 else if(i==n)
33 {
34 cout<<"NO"<<endl;
35 break;
36 }
37 if(count==n)
38 {
39 cout<<"YES"<<endl;
40 break;
41 }
42 if(top<-1)
43 {
44 cout<<"NO"<<endl;
45 break;
46 }
47 }
48
49 }
书中参考代码如下:
1 #include
2 using namespace std;
3 const int MAXN=1000+10;
4 int n,target[MAXN];
5 void main()
6 {
7 while(cin>>n)
8 {
9 int stack[MAXN],top=0;
10 int A=1,B=1; //A用来记录入栈次数,B用来记录出轨的火车序号
11 for(int i=1;i<=n;i++)
12 cin>>target[i]; //记录出轨顺序
13 int ok=1;
14 while(B<=n)
15 {
16 if(A==target[B]){A++;B++;}
17 else if(top && stack[top]==target[B]){top--;B++;} //出栈
18 else if((A<=n)) stack[++top]=A++; //入栈
19 else {ok=0;break;}
20 }
21 if(ok)
22 cout<<"Yes"<<endl;
23 else
24 cout<<"No"<<endl;
25 }
同样,可以用STL来实现,只需对书中参考答案作微小改动,代码如下:
1 /*STL栈来实现*/
2 #include
3 #include
4 using namespace std;
5 const int MAXN=1000+10;
6 int n,target[MAXN];
7 int main()
8 {
9 while(cin>>n)
10 {
11 stack<int> s;
12 int A=1,B=1;
13 for(int i=1;i<=n;i++)
14 cin>>target[i];
15 int ok=1;
16 while(B<=n)
17 {
18 if(A==target[B]){A++;B++;}
19 else if(!s.empty() && s.top()==target[B]){s.pop();B++;}
20 else if(A<=n) s.push(A++);
21 else {ok=0;break;}
22 }
23 if(ok)
24 cout<<"YES"<<endl;
25 else
26 cout<<"NO"<<endl;
27 }
28 }
【总结】
自己写的代码仍有优化的空间。学习参考答案的清晰逻辑的表达。学习STL栈的使用。
联系数据结构实验中关于火车入轨的提升,对缓冲轨的限制,应该增加一个判断即可。