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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/523177.html
標籤：其他
上一篇：Codeforces Round #831 (Div. 1 + Div. 2)
下一篇：代碼隨想錄演算法訓練營第四天|24、兩兩交換鏈表中的節點|19、洗掉鏈表的倒數第N個節點|面試題02.07.鏈表相交|142、環形鏈表Ⅱ