關于給定棧求出所有合法棧的思考

關于給定棧求出所有合法棧的思考

    前幾天看到一篇關于給定幾個元素，給一個出棧的順序，判斷出棧的順序是否合法，我們也可以通過給定的元素順序求出所有的合法的出棧順序，困擾我的問題是如何求出給定元素的所有的排列問題，之前有篇博文也有求三個數的全序列的，但采用的是三個for循環，實在是too young too simple，效率低不說，而且沒有一點實用性，總不能幾個數幾個for循環，這也太傻了（）。

對于判斷出棧的合法性問題，我先把思想寫出來，至于代碼實現需要過兩天，求所有的合法出棧順序有兩種思路。

方案1：一種是將所有元素的排列求出來，然后將每種都帶入到判斷棧的合法性的函數中，從而將合法的選出來。

方案2：第二種思路是利用之前括號匹配的思想，壓棧為0，出棧為1，出棧的前提是0的個數大于1的個數，然后將所有的可能保存下來，就是所有的合法出棧順序。

    很明顯方案2效率高，但博主對于第二中方案的實現實在有壓力，先把第一種簡單實現下，第二中方案的實現盡快補上（）

方案一代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>

using namespace std;

#pragma once

#include<iostream>

#include<stack>

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<int> 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隨后奉上

博主學識尚欠，若有理解錯誤的地方，請大神指出錯誤，，博主一定認真分析，盡快修改。