Uva 514 过来学学栈

一、题意

一列火车车厢号从1...n，问能否依靠一个中转站将车厢顺便变为指定的排序。
有若干组数据，每组数据第一行一个n,之后若干行每行为一询问。

二、解析

显然用栈模拟中转站。
车厢从1...n首先必然进栈，然后根据执行排序来判断是否需要出栈。

三、代码

#include <iostream>
#include <stack>
using namespace std;
const int maxn = 1000 + 5;
int n, a[maxn];

int main() {
    while(cin >> n && n) {
        while(cin >> a[0] && a[0]) {
            for(int j = 1; j < n; j ++) cin >> a[j];
            stack<int> stk;
            int j = 0;
            for(int i = 1; i <= n; i ++) {
                stk.push(i);
                while(!stk.empty() && stk.top() == a[j]) stk.pop(), j ++;
            }
            cout << (stk.empty() ? "Yes\n" : "No\n");
        }
        cout << endl;
    }
}

四、归纳

• 注意栈的题目执行stk.top()前一定要判定!stk.empty()
• 注意栈的题经常性是将出栈操作放在while循环中，思考时要特别注意不要遗漏这一细节。