2022.10.30每日一题

Daimayuan Online Judge-出栈序列判断

题目描述

现在有一个栈，有 \(n\) 个元素，分别为 \(1,2,…,n\)。我们可以通过 push 和 pop 操作，将这 \(n\) 个元素依次放入栈中，然后从栈中弹出，依次把出栈的元素写下来得到的序列就是出栈序列。
比如 \(n=3\)，如果执行 push 1，push 2，pop，push 3，pop，pop，那么我们 pop 操作得到的元素依次是 \(2,3,1\)。也就是说出栈序列就是 \(2,3,1\)。
现在给定一个合法的出栈序列，请输出一个合法的由 push 和 pop 操作构成的操作序列。这里要求 push 操作一定是按 \(1,2,…,n\) 的顺序。

输入格式

第一行一个整数 \(n\)。接下来一行 \(n\) 个整数，表示出栈序列。

输出格式

输出 \(2n\) 行，每行一个 push 或 pop 操作，可以证明一个出栈序列对应的操作序列是唯一的。

样例输入1

3
2 3 1

样例输出1

push 1
push 2
pop
push 3
pop
pop

样例输入2

5
1 3 5 4 2

样例输出2

push 1
pop
push 2
push 3
pop
push 4
push 5
pop
pop
pop

数据范围

对于 \(100\%\) 的数据，保证 \(1≤n≤100000\)，输入一定是个合法的出栈序列。

解题思路

比较基础的模拟题。因为保证是以 \(1,2,3,...,n\) 的顺序进栈，那么我们只需要出栈情况，也就是栈顶元素为当前 \(a[i]\) 对应的元素，那么我们就可以出栈，\(i\) 后移一位。而进栈操作，只要不满足出栈规则，就一直进栈即可。本题记得特判一下栈为空的情况

C++代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int tt = 0;
int stk[N], a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    int num = 1;
    for(int i = 1; i <= n; i ++)
    {
        while(!tt || stk[tt] != a[i])
        {
            printf("push %d\n", num);
            stk[++ tt] = num;
            num ++;
        }
        if(stk[tt] == a[i])
        {
            printf("pop\n");
            tt --;
        }
    }
    return 0;
}