出栈序列(stack.cpp)
【题目描述】
给定一个空栈S，以及N个数字，它们的入栈顺序永远是1、2、3...N
再给定一个长度为2*N的指令序列，只含有push和pop两种字符串；
其中push表示压栈，pop表示弹栈，保证序列合法。
请根据push、pop指令序列推算出数字的出栈顺序.
【输入格式】
第一行有一个正整数N，表示有[1,N]这N个数字，其入栈顺序永远是1、2、3...N
接下来有2*N行，每行一个字符串，为push或者pop两种指令
【输出格式】
一行，N个用空格隔开的数字，表示数字的出栈顺序
【样例输入】
4
push
push
pop
push
pop
push
pop
pop
【样例输出】
2 3 4 1
【样例解释】
未执行指令之前，栈为空:{}
执行第一条指令push后，栈的状态为:{1}
执行第二条指令push后，栈的状态为:{1,2}
执行第三条指令pop后，栈顶元素2被弹出，栈的状态为:{1}
执行第四条指令push后，栈的状态为:{1,3}
执行第五条指令pop后，栈顶元素3被弹出，栈的状态为:{1}
执行第六条指令push后，栈的状态为:{1,4}
执行第七条指令pop后，栈顶元素4被弹出，栈的状态为:{1}
执行第八条指令pop后，栈顶元素1被弹出，栈被清空:{}
可以看到，入栈顺序是1 2 3 4，弹栈顺序是:2 3 4 1
【数据范围】
对于100%的数据:2<=n<=10000
输入：
第一行有一个正整数N，表示有[1,N]这N个数字，其入栈顺序永远是1、2、3...N
接下来有2*N行，每行一个字符串，为push或者pop两种指令
输出：
一行，N个用空格隔开的数字，表示数字的出栈顺序
难度：
中等
输入示例：
4
push
push
pop
push
pop
push
pop
pop
输出示例：
2 3 4 1
代码类型：
C/C++
大概就是这样，没找到题，所以没有测试成功，但是按理来说2<=n<=10000应该问题不大
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int point = 1;
int main(){
stack<int> stack;
int n;
cin >> n;
string oper;
for(int i=0;i<2*n;i++){
cin >> oper;
if(oper=="push"){
stack.push(point);
point++;
}else if(oper=="pop"){
cout << stack.top() <<" ";
stack.pop();
}
}
system("pause");
return 0;
}
参考下面代码
// 合法的出栈序列.cpp
#include <iostream>
#include<stack>
#include<queue>
using namespace std;
//声明函数
bool check_stack(queue<int> &q) {
//声明一个栈s
stack<int> s;
int n = q.size();
for (int i = 1; i <= n; i++)
{
//按顺序入栈
s.push(i);
while (!s.empty()&&q.front()==s.top())
{
s.pop();
q.pop();
}
}
//如果s不为空就是不合法的
if (!s.empty())
{
return false;
}
return true;
}
int main()
{
//模拟数据 例:3 5 4 2 1
queue<int> q;
q.push(3);
q.push(5);
q.push(4);
q.push(2);
q.push(1);
if (check_stack(q)) {
cout << "合法的" << endl;
}
else {
cout << "不合法" << endl;
}
}