關(guān)于給定棧求出所有合法棧的思考

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括同心網(wǎng)站建設(shè)、同心網(wǎng)站制作、同心網(wǎng)頁制作以及同心網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，同心網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到同心省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

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

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

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

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

方案一代碼如下：

#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;  //壓入元素的個數(shù)

for (out = 0; out < length; out++)              

                               //(1)for循環(huán)控制什么,記錄彈出了幾個元素

{

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)為什么要進(jìn)行判空  當(dāng)棧中為空時必須進(jìn)行壓棧操作

{

if (in == length)          

                                    //(3)此時所有元素已經(jīng)壓棧但并沒找到出棧的元素，證明出棧的元素不合法

{

return false;

}

s.push(pPush[in]);

++index;

}

else                        //棧頂?shù)脑睾蛷棾龅脑叵嗟?，直接彈?/p>

{

s.pop();

break;            //跳出這層for循環(huán)，使它遍歷下一個出棧元素

}

}

}

return true;

}

void SWAP(int *a, int *b) //交換數(shù)組中的兩個元素

{

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的實(shí)現(xiàn)的難點(diǎn)主要在于遞歸的使用，實(shí)現(xiàn)的思想是將數(shù)組中的每一元素放在第一位，然后遞歸將第二位當(dāng)做第一位繼續(xù)遞歸，直至i等于n，打印出來隨后的過程是從后向前逐個交換，從而實(shí)現(xiàn)全排列。全排列的數(shù)組傳到斷 Check_Push_Pop（）函數(shù)中判斷，若合法則打印，否則不打印。

方案2隨后奉上

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