LintCode 3210: Train access (栈好题)

3210 · Train access
C++
Medium

Description
Now there is a station with only one entrance, and trains can only exit or enter from the only one.
Now you are given an incoming train order in_order, and an outgoing stack order leave_order.

Please design a program to determine whether a train can enter the station in the incoming order and whether it can exit the station in the outgoing order.

Note:

If in_order = [1,2,3] train 1 cannot enter the station until train 2 and train 3 enter the station.
If leave_order = [1,2,3] train 1 cannot leave the station before train 2 and train 3 can leave the station.
And if there are trains in front of train 1 in the station, train 1 cannot leave the station either, because there is only one entrance/exit in the station.
This question requires you to complete the code in the function train in the file Solution.cpp.

This function.

Receives two vector containers in_order and leave_order that store shaped data indicating the incoming and outgoing order of trains. The data in them represents the train number.
Returns a bool data true or false, which means the train can leave the station in the order of leave_order or not in the order of leave_order.
The evaluator will run main.cpp to call the train function in Soluction.cpp by importing a custom function library, and get your return value to determine the correctness of the result.

The number of elements in in_order and leave_order are the same.
There are no duplicate elements.

Use the stack container in the library to solve the problem.
Example
Input Sample 1:

[1,2,3]
[1,3,2]
Output sample 1:

true
The flow of the train is as follows.
1 Inbound
1 Outbound
2 Inbound
3 Inbound
3 Outbound
2 exit
You can see that 1 can exit immediately after entering the station, 2 can wait after entering the station, and 3 can exit after entering the station.
If the inbound order is 1,2,3, the outbound order 1,3,2 can be realized.

Input sample 2:

[1,2,3]
[3,1,2]
Output sample 2:

false
If you want 3 to leave the station first, then you need to enter both trains 1,2 first, in the order of entry.
After that, 3 can leave the station.
But then 1 wants to exit, but 1 is blocked by 2 in front of it, so this exit order cannot be achieved.

这题跟lintcode 377和lintcode 1678差不多，都是火车进站类的栈问题。
解法1：

/**
 * @param in_order: An arryy
 * @param leave_order: An arryy
 * @return: A boolean
 */
bool train(vector<int> &in_order, vector<int> &leave_order) {
    if (in_order.size() != leave_order.size()) return false;
    stack<int> stk;
    int in_pos = 0, out_pos = 0;
    while (in_pos < in_order.size()) {
        //if (in_order[in_pos] != leave_order[out_pos]) {
        stk.push(in_order[in_pos]); //注意这里push是没有if条件的。
        in_pos++;
        while (!stk.empty() && stk.top() == leave_order[out_pos]) {
            stk.pop();
            out_pos++;
        }
    }
    return stk.empty();
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21