# 14151: 【原4151】出栈序列

### 题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4151

## Sample Input

``````2
3 1 3 2
3 3 1 2
``````

## Sample Output

``````Yes
No
``````

T<=10, n<=10^6

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

int main() {
int T;
ios::sync_with_stdio(false);
cin >> T;

for (; T > 0; T--) {
int num;
bool flag = true;
cin >> num;
int stackTop = 0;
//不断遍历模拟
for (int i = 0, n = 1; i < num; i++) {
int currentNum;
cin >> currentNum;
if (!flag) continue;
if (n <= currentNum) {
stackTop = currentNum;
n = currentNum + 1;
}
if (currentNum <= stackTop)
stackTop=currentNum;
else {
flag = false;
}
}

if (flag)
printf("Yes\n");
else
printf("No\n");

}

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

template <class T>
class seqStack {
private:
T *data;
int nowSize;
int maxSize;
void doublespace();

public:
seqStack(int initSize = 10);
seqStack(const seqStack<T> &);
~seqStack();
int size() const;
void push(T);
T top();
T pop();
bool isEmpty();
T find(T) const;
seqStack<T> &operator=(const seqStack<T> &);
T &operator[](int);
};

template <class T>
seqStack<T>::seqStack(int initSize) {
data = new T[initSize];
nowSize = 0;
maxSize = initSize;
}

template <class T>
seqStack<T>::seqStack(const seqStack<T> &right) {
nowSize = right.nowSize;
maxSize = right.maxSize;
data = new T[maxSize];
for (int i = 0; i < nowSize; i++) {
data[i] = right.data[i];
}
}

template <class T>
seqStack<T>::~seqStack() {
delete[] data;
data = NULL;
}

template <class T>
void seqStack<T>::doublespace() {
maxSize *= 2;
T *tmp;
tmp = new T[maxSize];

for (int i = 0; i < nowSize; i++) {
tmp[i] = data[i];
}

delete[] data;
data = tmp;

tmp = NULL;
}

template <class T>
int seqStack<T>::size() const {
return nowSize;
}

template <class T>
void seqStack<T>::push(T x) {
if (nowSize == maxSize) {
doublespace();
}
data[nowSize++] = x;
}

template <class T>
T seqStack<T>::top() {
if (nowSize > 0) {
return data[nowSize - 1];
}
}

template <class T>
T seqStack<T>::pop() {
if (nowSize > 0) {
return data[--nowSize];
}
}

template <class T>
bool seqStack<T>::isEmpty() {
return (nowSize == 0);
}

template <class T>
T seqStack<T>::find(T x) const {
for (int i = 0; i < nowSize; i++) {
if (data[i] == x) {
return x;
}
}
return -1;
}

template <class T>
seqStack<T> &seqStack<T>::operator=(const seqStack<T> &right) {
if (this != &right) {
delete[] data;

nowSize = right.nowSize;
maxSize = right.maxSize;
data = new T[maxSize];
for (int i = 0; i < nowSize; i++) {
data[i] = right.data[i];
}
}

return *this;
}

template <class T>
T &seqStack<T>::operator[](int x) {
return data[nowSize - x - 1];
}

bool checkOrder(int *a, int n) {
int save = 0;
seqStack<int> sta;
for (int i = 0; i < n; i++) {
if (a[i] > save + 1) {
for (int j = save + 1; j < a[i]; j++) {
sta.push(j);
}
save = a[i];
} else if (a[i] == save + 1) {
save = a[i];
} else if (a[i] < save) {
if (a[i] == sta.top()) {
sta.pop();
} else {
return 0;
}
}
}
return 1;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int nums[1000100], T, n;

cin >> T;
for (int i = 0; i < T; i++) {
cin >> n;
for (int j = 0; j < n; j++) {
cin >> nums[j];
}
if (checkOrder(nums, n)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}

return 0;
}
``````

## q4x3's solution

``````/**
* 栈模拟
* 为什么每道题都要快读TATTTTT
**/
#include <iostream>
#include <stdio.h>

using namespace std;
int tmp, nex, flag = 1;

struct sstack
{
int a[1000233];
int top;
};

x = 0;
char ch;
while (ch = getchar(), (ch < '0' || ch > '9'));
x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
}

int main() {
int T;
cin >> T;
for(int i = 0;i < T;++ i) {
int N;
nex = 0; flag = 1;
sstack s;
s.top = 0; s.a[0] = nex;
for(int i = 0;i < N;++ i) {
while(flag) {
if(s.a[s.top] == tmp - 1) {
-- s.top;
break;
}
++ s.top;
++ nex;
if(nex + 1 > N) flag = 0;
s.a[s.top] = nex;
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
}
``````

## victrid's solution

``````#include <cstdio>
#include <iostream>
using namespace std;
//Changed logic to avoid duplicats.
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x  = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
int proc[1000000];
int stk[1000000];
int* stkptr = stk;
int T, N, now;
int main() {
while (T--) {
stkptr = stk;
now    = 0;
for (int j = 0; j < N; j++)
for (int nums = 1; nums <= N; ++nums) {
*stkptr++ = nums;
while (stkptr != stk && now < N && proc[now] == stkptr[-1]) {
stkptr--;
now++;
}
}
printf(stkptr == stk ? "Yes\n" : "No\n");
}
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
int t,st[1100000],top,n,now,a[1100000];
int main() {
ios::sync_with_stdio(false);
cin>>t;
for (int i=0;i<t;++i)
{
cin>>n;
now=0;
top=0;
for (int j=0;j<n;++j)
cin>>a[j];
for (int j=1;j<=n;++j) {
st[top++] = j;
while (a[now]==st[top-1]&&now<n&&top>=0) {
top--;
now++;
}
}
if (top!=0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
``````