C++ train entry algorithm implementation code

[problem description]

There is a railway station in a city. There are n cars coming into the station from direction A, numbered 1~n in order of arrival. Your task is to get them in a certain order into the track in direction B and out of the station. To reorganize the car, you can use transfer station C. This is a station where you can park as many cars as you like, but because of the terminal cap, cars entering C have to exit in the opposite order. For each car, once you move from A to C, you can't go back to A; Once you move from C to B, you can't go back to C. In other words, at any given moment, there are only two choices: A - C and C - B.

The problem is similar to that of previous experiments with data structures, but simpler. Try to write their own next, and the book reference answer code still has a large gap. The code is as follows:

#include<iostream>
using namespace std;
const int MAXSIZE=100;
void main()
{
    int n;
    cin>>n;
    int a[MAXSIZE],b[MAXSIZE];
    int stack[MAXSIZE];
    for(int i=0;i<n;i++)
    {
        a[i]=i+1;
        cin>>b[i];                   　　 //The stack order
    }
    int top=-1;
    int count=0;
    int i=0;
    for(;;)
    {
        if(i<n)
        {
            ++top;
            stack[top]=a[i++];            //Into the stack
            cout<<"PUSH"<<endl;
        }

        if(stack[top]==b[count])
        {
            top--;count++;
            cout<<"POP"<<endl;
        }
        else if(i==n)
        {
            cout<<"NO"<<endl;
            break;
        }
        if(count==n)
        {
            cout<<"YES"<<endl;
            break;
        }
        if(top<-1)
        {    
            cout<<"NO"<<endl;
            break;
        }
    }
}

  The reference code in the book is as follows:

 #include<iostream>
using namespace std;
const int MAXN=1000+10;
int n,target[MAXN];
void main()
{
    while(cin>>n)
    {
        int stack[MAXN],top=0;
        int A=1,B=1;                                          　　  //A is used to record the number of pushes, and B is used to record the train number that derailed
        for(int i=1;i<=n;i++)
            cin>>target[i];                                        //Record order of derailment
        int ok=1;
        while(B<=n)
        {
            if(A==target[B]){A++;B++;}
            else if(top && stack[top]==target[B]){top--;B++;}    　　//Out of the stack
            else if((A<=n)) stack[++top]=A++;                   　　 //Into the stack
            else {ok=0;break;}
        }
        if(ok)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
 

  Again, it can be implemented using STL, with only minor changes to the reference answers in the book. The code is as follows:

 
#include<iostream>
#include<stack>
using namespace std;
const int MAXN=1000+10;
int n,target[MAXN];
int main()
{
    while(cin>>n)
    {
        stack<int> s;
        int A=1,B=1;
        for(int i=1;i<=n;i++)
            cin>>target[i];
        int ok=1;
        while(B<=n)
        {
            if(A==target[B]){A++;B++;}
            else if(!s.empty() && s.top()==target[B]){s.pop();B++;}
            else if(A<=n) s.push(A++);
            else {ok=0;break;}
        }
        if(ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}
 

【 summary 】

There is still room for optimization of your own code. Learn the clear logical expression of the reference answer. Learn how to use the STL stack.

In connection with the data structure experiment about the elevation of the train into the rail, the limitation of the buffer rail should be increased by a judgment.

I do not know how deep the pit is C++ beginners currently stay in the "water problem" stage step by step, feel the stones across the river to Daniel