本文主要是介绍判断是否是合法的出栈序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在技术笔试面试上，我们常常会遇到这样一类题型，如给你一个入栈序列，然后再让你判断几个序列是否有可能为它的出栈序列，如：
入栈序列为 1 2 3 4 5，则 1 2 3 4 5可能为它的出栈序列，而 5 4 1 2 3不可能为它的出栈序列。
对于n比较小的情况，我们往往可以通过手动模拟的方式来判断，对于n比较大的时候，这种方法就显得效率不佳了。
下面介绍一种通用的方法判定合法出栈序列，时间复杂度为O(n)。为了叙述方便，我们不妨设入栈序列为 1 2 3.......n，并且每个元素各不相等。
事实上，一个出栈序列固定的话，那么没个数的出栈顺序和时间都是固定的，则我们可以模拟栈的入栈出栈过程，来判断是否一个合法的出栈序列。
我们首先设po为目前为止入栈的元素中最大的数，初始化为0，若下一个出栈元素要大于po的话（设为x），说明我必须将[po+1,x]中的所有书都入栈，再将x弹出即可（这时还应把po赋值为x）。否则说明下一个出栈的元素已经在栈中，并且肯定是栈顶元素，若栈顶元素与下一个出栈元素不相等的话，我们可以判断这不是一个合法出栈序列，否则，若所有的出栈元素都不引起冲突，则说明这是一个合法序列。这里再说一下时间复杂度，因为我们只有在下一个出栈元素大于po时，才将元素压入栈中，并且我们每一次判断一个出栈元素是否发生冲突时，都会将栈顶元素弹出，所以每一个元素都入栈一次，出栈一次，所以时间复杂度为O(n)。
算法的具体实现请看代码。
#include <stdio.h>
#define maxn 1005
int stack[maxn],top;
int out[maxn];
int check(int n)
{ int po=0; for(int i=1;i<=n;i++) { for(int j=po+1;j<=out[i];j++) { po=j; stack[top++]=j; } if(stack[--top]!=out[i]) return 0; } return 1;
}
int main()
{ int n; scanf("%d",&n);//假设入栈序列为1 2。。。。n for(int i=1;i<=n;i++) { scanf("%d",&out[i]); } if(check(n)) printf("Yes\n"); else printf("No\n"); return 0;
}
判断是否是合法的出栈序列
栈，这个“后进先出(Last In First Out)” 数据结构应该都不陌生。如果 a、b、c 依次入栈，然后出栈，那么出栈顺序是 c、b、a；如果 a 入栈然后出栈、b 入栈出栈、c 入栈出栈，那么出栈顺序是 a、b、c。如果只是强调 a、b、c 的入栈顺序，而不强调具体的出栈顺序，那么 cba 和 abc 都可以是出栈顺序，acb、bac 和 bca 也都可以，而 cab 是不可以的：因为 c 首先出栈说明 a b 在栈中，c 出栈后其他出栈顺序只能是 ba 而不可能是 ab。
现在给 n 个数或是字母，假定就是 1、2、3、...、n ，已知它们是按照顺序入栈的，有几个问题：
- 给定一个序列，判断是否可能是一个出栈序列？比如 1 2 3 ... n 肯定可以，n (n-1) ... 3 2 1 也可以，但是 1 4 2 ... 就不可以；
- 合法的出栈序列有多少种 ?
模拟入栈出栈
me 们可以模拟一下入栈出栈操作，如果可以就是 yes，如果不可以就是 no ! 但如何模拟呢 ? 举个 1 2 3 4 5 的出栈例子 4 5 3 2 1 。me 们建一个辅助栈(最初是空的)再加一个带入栈元素 in (最初是 1 )，然后看判断序列 4 5 3 2 1。
- 待入栈元素 in = 1，当前判断序列元素是 4，1 ≠ 4 那么， 1 入栈，然后 in = 2；2 ≠ 4 然后 2 入栈，然后 3 入栈；然后 in = 4；
- in = 4，那么应该是 4 入栈然后出栈，这里直接可以将当前判断元素换成下一个也就是 5 ；
- 4 出栈以后， me 们发现栈顶 top 是 3，不匹配 5，这个时候没法继续出栈；那么执行和第一步类似的操作，使用 in 去判断；
- in = 5 匹配第二个判断元素，那么 5 入栈出栈(直接看下一个判断元素)，这个时候栈顶 top = 3，3 可以出栈，然后栈顶是 2 可以出栈，然后是 1 可以出栈；最后判断序列元素全部判断完了，那么说明序列 4 5 3 2 1 是一个合法的出栈序列；
模拟过程基本如上：最初栈为空，in = 1；然后依次扫描判断序列元素 e，如果和 in 不同则需要不断将 in 入栈(因为当前栈中元素并不匹配 e)；如果 in 和 e 相同则直接判断下一个元素(可以认为是 e 先入栈然后出栈)，这个时候考虑待判定元素 e 是否可以通过出栈匹配，如果可以则出栈，而且是尽可能多的出栈，如果不可以则有通过继续将 in 元素压入栈中寻求匹配。如果判定序列的元素都判定过了，那就是 yes；如果么法出栈，而 in 又么法继续入栈(比如 in 已经超过 n 了)，那就是 no !
#include <iostream>
#include <vector>
using namespace std;bool test_ok(int n, vector<int>& olist);int main(int argc, char *argv[])
{vector<int> olist;int n, x, count=0;bool ok;while(1){olist.clear();cin >> n;if(!cin)break;for(int i=0; i<n; ++i){cin >> x;olist.push_back(x);}ok = test_ok(n, olist);if(ok)++count;cout << ok << '\n';}cout << "count : " << count << endl;return 0;
}bool test_ok(int n, vector<int>& olist)
{vector<int> istack;int in = 1, top, oindex = 0;while(1){if(oindex >= n) // ok, olist has no element left !return true;if(in > n)return false;if(in != olist[oindex]){ // push into stackistack.push_back(in);++in;continue;}++in;++oindex;while(!istack.empty() && istack.back() == olist[oindex]){ // pop from stackistack.pop_back();++oindex;}}
}全排列
上面提的第二个问题还没有回答，不过如果 me 们已经可以判断序列了，那么将所有的序列都判断一遍然后数数有多少个合法的，不就可以了 ? 那么 1、2、3、...、n 的所有序列有多少种呢 ? 好吧，这就是一个全排列丫，有木有 !
1、2、3、...、n 的全排列有 n! 种，这个大家都知道的结论就不多说了。问题是，如何生成 n 个数的全排列，这是这里关系的重点。其实 me 这里并不关心如何实现，只是想写个程序生成 n 个数的全排列而已，不错的是，c++ 标准库已经提供了类似的函数，very good !
生成 1-n 的全排列
程序扫描一个数字 n，然后生成其所有的全排列，实际就是 n! 个序列，而每个序列以 n 打头，这样的好处就是，程序的结果可以直接传递给上面的程序使用 !
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main(int argc, char *argv[])
{vector<int> vints;int n;cin >> n;for(int i=0; i<n; ++i)vints.push_back(i+1);do {cout << n;for(int i=0; i<n; ++i)cout << ' ' << vints[i];cout << '\n';} while(next_permutation(vints.begin(), vints.end()));cout << endl;return 0;
}
这篇关于判断是否是合法的出栈序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
