UVa -514（栈的运用)

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station
was built in last century. Unfortunately, funds were extremely limited that time. It was possible to
establish only a surface track. Moreover, it turned out that the station could be only a dead-end one
(see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A A Acontinues in the direction
B B B with coaches reorganized in some way. Assume that the train arriving from the direction A has
N ≤ 1000 N ≤ 1000 N≤1000 coaches numbered in increasing order 1 , 2 , . . . , N 1, 2, . . . , N 1,2,...,N. The chief for train reorganizations must
know whether it is possible to marshal coaches continuing in the direction B so that their order will
be a 1 . a 2 , . . . , a N a_1.a_2, . . . , a_N a1​.a2​,...,aN​ . Help him and write a program that decides whether it is possible to get the required
order of coaches. You can assume that single coaches can be disconnected from the train before they
enter the station and that they can move themselves until they are on the track in the direction B B B. You
can also suppose that at any time there can be located as many coaches as necessary in the station.
But once a coach has entered the station it cannot return to the track in the direction A A A and also once
it has left the station in the direction B B B it cannot return back to the station.

Input

The input file consists of blocks of lines. Each block except the last describes one train and possibly
more requirements for its reorganization. In the first line of the block there is the integer N described
above. In each of the next lines of the block there is a permutation of 1, 2, . . . , N. The last line of the
block contains just ‘0’.
The last block consists of just one line containing ‘0’.

Output

The output file contains the lines corresponding to the lines with permutations in the input file. A line
of the output file contains ‘Yes’ if it is possible to marshal the coaches in the order required on the
corresponding line of the input file. Otherwise it contains ‘No’. In addition, there is one empty line after
the lines corresponding to one block of the input file. There is no line in the output file corresponding
to the last “null” block of the input file.

Sample Input

5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

Sample Output

Yes
No

Yes
题意：
有n节按顺序标号的列车要从 A A A移动到 B B B，中间有一个可以进入的只有一个口的站，当列车进入这个站之后就不能回到 A A A，同样，从站里进入 B B B也不能回到站内。进入站之后，必须等里站口近的列车出去之后，里面的列车才能出来。例如， 1 1 1， 2 2 2进入了站， 1 1 1想要出站，必须等 2 2 2先出去。每次有多组询问，以一个 0 0 0结束询问，每次回答这种顺序是否能实现。

题解：
这个中间站的性质与栈一致，所以就想到用栈来解决问题。如果按照原本的顺序，则直接顺利通过，即 1 1 1在第 1 1 1位出现， n n n在第 n n n位出现。如果不是按照这个顺序，那么我们就将当前位置应该出现的值 p u s h push push到栈里。在接下来的遍历中，如果栈头元素与询问中的元素相等，即可 p o p pop pop栈头元素。如果已经遍历完了 n n n位元素，但这时通过的列车不足 n n n个，就说明无法满足询问顺序。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 10;

int que[maxn];
int n, now, finish;

void solve() {
	while (~scanf("%d", &que[1]), que[1]) {
		stack<int> st;
		for (int i = 2; i <= n ; ++i) scanf("%d", &que[i]);
		que[n + 1] = 0;
		now = finish = 1;//now为当前应该出现的列车，即按顺序的1-n
						//finish为已经通过的列车数量
		while (finish <= n) {
			if (que[finish] == now) {//当前位置对应，即a在a位上，列车可以直接通过
				now++;
				finish++;
			}
			else if (!st.empty() && st.top() == que[finish]) {
			//这一步判断要在push之前，如果栈头元素与当前询问位置一致，即可出栈
				st.pop();
				finish++;
			}
			else if (now <= n) st.push(now++);//应该出现的列车与询问的列车不一样，入栈
			else break;//遍历完了n节列车，不能在入栈了，无法满足
		}
		if (finish > n) puts("Yes");
		else puts("No");
	}
	puts("");
}

int main() {
	while (~scanf("%d", &n), n) solve();
	return 0;
}