题目之火车站点

图灵题目

题目

从A地来编号为：1～n的火车，他们按顺序进入站点C(若留在站点，则他们的排列顺序类似于栈），输入一定的出站顺序，设计程序判断能否实现。

样例：

判断思路(正序尚未想到，此处无用）：

1. 对于第一个，可以进去以后立刻出来
2. 对于第二个，由于要 5 先出来，则全部都要进去，由于 1在最里面，所以1不可以先于2``3出来
3. 对于第三个，全部进去，以后按照顺序出来就好

实现工具：

• （我感觉是）队列
• (下面都是完成后的判断）使用两个栈，一个队列。
  
  • O代表出站，使用队列，因为我是从最后一位读起的，先进先出
  • E代表进站，我使用的是栈，从最小开始进栈
  • S代表车站，我使用的是栈，先进后出

设计思路：//事实证明，实现的手段并不重要，最重要还是思路，所以说队列并不是重点。

全部进队列
(由于后面已经有了，这里全部删除了）

还是金胜比较厉害啊，一句就把这个问题的解决要点想出来了。
还是有点bug的。
（这段基本没用）

#include <iostream>
using namespace std;
int main() {
  int num;
  cin>>num;
  int array[num];
  bool flag = true;
  for (int i = 0; i < num; i++) {
    cin>>array[i];
  }
  for (int j = 1; j < num-1; j++) {
    if (array[j+1] > array[j] && array[j-1] > array[j]) {
      flag = false;
    }
  }
  if (flag) cout<<"success."<<endl;
  else cout<<"failed."<<endl;
  return 0;
}

重新再构造模型：

获得出站的顺序，或者说直接就把它入栈O里面
获得O栈顶的数据，与入站E的第一个元素比较
    若是相等，则出O和E
    若是不等，则将O的元素入站S

伪代码：

get the sequence of the train
while O is not empty
    if S.front == E.front && S.front
        S.pop
        E.pop
    else if O.front == E.front
        O.pop
        E.pop
    else
        x = O.front
        S.push(x)
while S.front == E.front
    S.pop
    E.pop
if S.isEmpty
    cout<<"success."
else 
    cout<<"failed."

代码：

#include "stackClass_v2"
#include "queueClass"
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  queue<int> O;
  Stack<int> E;
  Stack<int> S;
  int count = 0;
  int seq = 0;
  cin>>seq;
  while (seq) {
    int n = (seq - seq/10*10);
    O.push(n);
    seq /= 10;
    count++;
  }
  for (int i = 0; i < count; i++) {
    E.push(i+1);
  }
  while (!O.isEmpty()) {
    if (!S.isEmpty() && S.front() == E.front()) {
      S.pop();
      E.pop();
    }
    else if (!O.isEmpty() && O.front() == E.front()) {
      O.pop();
      E.pop();
    }
    else {
      int x = O.front();
      S.push(x);
      O.pop();
    }
  }
  while (!S.isEmpty() && S.front() == E.front()) {
    S.pop();
    E.pop();
  }
  if (S.isEmpty()) {
    cout<<"success.";
  }
  else cout<<"failed.";
  return 0;
}

按照这个伪代码，终于写好啦！！！
以后写程序前先写伪代码吧233333333333

总结

1. 写程序前先写伪代码有助于成功
2. 对于stack以及queue等类，好像还有内在的bug，慢慢de
3. 提高效率，学gdb！！！啊啊啊！！！