紫书 第六章 例题 6-2 算法： 设栈 s，用于模拟停在站内的火车车厢。 输入出站顺序 {c[n]}，对每一节车厢 c[i]，分三种情况： ①如果栈 s 为空（车站没有车厢），或 c[i] > s.top()（即最后进站的车厢编号小于出站次序中该节车厢的编号），新车厢入栈（需要用一个变量 p 记录上次最后入栈的车厢编号，p 的初始值为 1）直到 c[i] = s.top()（最后进站的车厢编号等于出站次序中该节车厢的编号），然后执行②。 ② c[i] = s.top()，最后进站的车厢出站，读取期望的出站顺序中的下一个车厢编号 c[i+1]。 ③ c[i] < s.top()，因为准备进站的车厢是根据入站次序编号 1、2、3、……、n 的，当 c[i] < s.top() 时，为了将 c[i] 车厢出站，必须将站内的跟在 c[i] 车厢之后入站的车厢先出站，这样出站的顺序就不符合列车长要求的次序，输出 No。 当全部次序读取完毕，输出 Yes。 每个测试情况输出完毕以后要额外输出一个空行，而且 Yes、No 不要分别写成 YES、NO 或 yes、no。当输出 No 以后，站内一般还有未出站的车厢，因为已经放弃处理，所以在处理下一个序列之前，栈内剩余的数据需要清空。 AC 代码（30 ms）：
#include<cstdio> #include<cstdlib> #include<stack> #pragma warning(disable:4996) using namespace std; stack<unsigned short> s; unsigned short c[1000], n, p = 1; bool result; int main() { for (;;) { scanf("%hu", &n); if (n == 0)break; for (;;) { scanf("%hu", &c[0]); if (c[0] == 0) { putchar('\n'); break; } for (unsigned short i = 1; i < n; ++i) { scanf("%hu", &c[i]); } result = true; p = 1; while (s.empty() == false)s.pop(); for (unsigned short i = 0; i < n; ++i) { if (s.empty() == true || c[i] > s.top()) { for (unsigned short j = p; j <= c[i]; ++j, ++p) s.emplace(j); s.pop(); continue; } else if (c[i] == s.top()) { s.pop(); continue; } else { result = false; break; } } switch (result) { case true:puts("Yes"); break; case false:puts("No"); } } } return 0; }