关于给定栈求出所有合法栈的思考
关于给定栈求出所有合法栈的思考
创新互联建站服务项目包括同心网站建设、同心网站制作、同心网页制作以及同心网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，同心网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到同心省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
前几天看到一篇关于给定几个元素，给一个出栈的顺序，判断出栈的顺序是否合法，我们也可以通过给定的元素顺序求出所有的合法的出栈顺序，困扰我的问题是如何求出给定元素的所有的排列问题，之前有篇博文也有求三个数的全序列的，但采用的是三个for循环，实在是too young too simple，效率低不说，而且没有一点实用性，总不能几个数几个for循环，这也太傻了（
）。
对于判断出栈的合法性问题，我先把思想写出来，至于代码实现需要过两天，求所有的合法出栈顺序有两种思路。
方案1：一种是将所有元素的排列求出来，然后将每种都带入到判断栈的合法性的函数中，从而将合法的选出来。
方案2：第二种思路是利用之前括号匹配的思想，压栈为0，出栈为1，出栈的前提是0的个数大于1的个数，然后将所有的可能保存下来，就是所有的合法出栈顺序。
很明显方案2效率高，但博主对于第二中方案的实现实在有压力，先把第一种简单实现下，第二中方案的实现尽快补上（
）
方案一代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
#pragma once
#include
#include
using namespace std;
bool Check_Push_Pop(int* pPush, int* pPop, int length)
{
if (length <= 0 || pPush == NULL || pPop == NULL)
{
return false;
}
int in = 0;
int out = 0;
stack
//s.push(pPush[0]);
int index = 0; //压入元素的个数
for (out = 0; out < length; out++)
//(1)for循环控制什么,记录弹出了几个元素
{
for (in = index; in <= length; in++)
//pPush[1,2,3,4,5] pPop[4,5,3,2,1] 控制压入了几个元素
{
if ((s.empty()) || s.top() != pPop[out])
//(2)为什么要进行判空 当栈中为空时必须进行压栈操作
{
if (in == length)
//(3)此时所有元素已经压栈但并没找到出栈的元素，证明出栈的元素不合法
{
return false;
}
s.push(pPush[in]);
++index;
}
else //栈顶的元素和弹出的元素相等，直接弹出
{
s.pop();
break; //跳出这层for循环，使它遍历下一个出栈元素
}
}
}
return true;
}
void SWAP(int *a, int *b) //交换数组中的两个元素
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void perm(int *list, int i, int n,int& count,int* push)
{
int j = 0;
if (i == n)
{
if (Check_Push_Pop(push, list, n))
{
for (j = 0; j < n; j++)
{
cout << list[j];
cout << " ";
}
count++;
cout << endl; //加
}
}
else
{
for (j = i; j < n; j++)
{
SWAP(list + i, list + j);
perm(list, i + 1, n,count,push);
SWAP(list + i, list + j);
}
}
}
int main()
{
int list[4] = { 1, 2, 3, 4}; //入栈的元素
int push[4] = { 1, 2, 3, 4};
cout << "Please input a number!" << endl;
int n = 0;
int count = 0;
cin >> n;
perm(list, 0, n,count,push);
cout << count << endl;
system("pause");
return 0;
}
方案1的实现的难点主要在于递归的使用，实现的思想是将数组中的每一元素放在第一位，然后递归将第二位当做第一位继续递归，直至i等于n，打印出来随后的过程是从后向前逐个交换，从而实现全排列。全排列的数组传到断 Check_Push_Pop（）函数中判断，若合法则打印，否则不打印。
方案2随后奉上
博主学识尚欠，若有理解错误的地方，请大神指出错误，
，博主一定认真分析，尽快修改。
分享名称：关于给定栈求出所有合法栈的思考
文章出自：http://mswzjz.cn/article/jhggjs.html