关于给定栈求出所有合法栈的思考-创新互联

关于给定栈求出所有合法栈的思考

    前几天看到一篇关于给定几个元素，给一个出栈的顺序，判断出栈的顺序是否合法，我们也可以通过给定的元素顺序求出所有的合法的出栈顺序，困扰我的问题是如何求出给定元素的所有的排列问题，之前有篇博文也有求三个数的全序列的，但采用的是三个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;

//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随后奉上

博主学识尚欠，若有理解错误的地方，请大神指出错误，，博主一定认真分析，尽快修改。

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。