2016.11.22

栈

铁轨问题：
a是原序列的标记指针，b是标记目标序列的指针，这点理解了就好了。
另，第一个判断当前的目标序列是否与原序列的现在相等，第二个是当中转站中不为0时，让中转站的元素与目标相比，第三个是当两个条件都不满足时，则让栈中的元素增加。
代码

#include <stdio.h>
int main(void)
{
    int target[20] = {0};
    int stack[20] = {0};
    int a = 1,b = 1;
    int i;
    int n;
    scanf("%d",&n);
    for (i = 1;i <= n;i++)
        scanf("%d",&target[i]);
    int top = 0;
    int ok = 1;
    while (b <= n)
    {
        if (target[a] == stack[b]) {a++;b++;}
        else if (top && (stack[top] == target[b])) {top--;b++;}
        else if (a <= n) stack[top] = a++;
        else ok = 0;
    }
    if (ok) printf("yes\n");
    else printf("no\n");
    return 0;
}

c++:

#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main(void)
{
    int b[20] = {0};
    int n;
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        scanf("%d",&b[i]);
    int x = 1,y = 1;
    int ok = 1;
    while (x <= n)
    {
        if (y == b[x]) {y++;x++;}
        else if (!s.empty() && s.top() == b[x]) {s.pop();x++;}
        else if (y <= n) s.push(y++);
        else {ok = 0;break;}
    }
    if (ok) printf("yes\n");
    else printf("no\n");
    return 0;
}