問題：元素出棧，入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,1,2）

公司主營業(yè)務(wù)：成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)公司推出張家川回族自治免費做網(wǎng)站回饋大家。

  定義一個棧sp，入棧序列為str1，出棧序列為str2，長度分別為size1和size2。如果兩個序列為空或長度不等，則不合法，針對長度相等且不為空的兩個序列進(jìn)行判斷。

先將str1中第一個元素入棧，然后通過循環(huán)使str1后移。

1、如果當(dāng)前棧為空且入棧序列不為空，則入棧序列str1后移，sp入棧。

2、如果棧頂元素不等于出棧序列且入棧序列不為空，則入棧序列str1后移，sp入棧。

3、如果棧頂元素等于出棧序列，sp出棧，出棧序列str2后移。

循環(huán)比較后，如果棧為空，則出棧序列是合法的。

下面以入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,1,2）為例進(jìn)行說明。

利用模板實現(xiàn)對象OutStack，可以判斷不同類型元素出棧，入棧順序的合法性，具體實現(xiàn)如下：

#include
using namespace std;
#include
#include
template
class OutStack
{
public:
	OutStack();
	OutStack(const T* str1, const T* str2, size_t size1, size_t size2);
	~OutStack();
	bool OutStack::Legality();
private:
	T* _str1;
	T* _str2;
	size_t _size1;
	size_t _size2;
};
template
OutStack::OutStack()
:_str1[NULL]
, _str2[NULL]
, sp(NULL)
{}
template
OutStack::OutStack(const T* str1, const T* str2, size_t size1, size_t size2)
: _str1(new T[size1])
, _str2(new T[size2])
, _size1(size1)
, _size2(size2)
{
	memcpy(_str1, str1,(sizeof(T)*_size1));//memcpy按照字節(jié)數(shù)進(jìn)行復(fù)制的
	memcpy(_str2 ,str2,(sizeof(T)*_size2));
}
template
OutStack::~OutStack()
{
	if (_str1 || _str2)
	{
		delete[] _str1;
		delete[] _str2;
	}
}
template
bool OutStack::Legality()
{
	T* str1 = _str1;//入棧序列
	T* str2 = _str2;//出棧序列
	stack sp;
	if (str1 && str2 && _size1 != _size2)
		return 0;
	sp.push(*str1);//先將str1中第一個元素入棧
	for (size_t i = 0; i < _size1;)//將出棧序列比較完
	{
		if (*str1 != NULL && sp.empty())
		{
			str1++;
			sp.push(*str1);
			i++;//i和str1同步進(jìn)行,直到str1進(jìn)行完
		}
		if (*str1 != NULL && sp.top() != *str2)//棧頂元素與出棧元素比較
		{
			str1++;
			sp.push(*str1);
			i++;//i和str1同步進(jìn)行，直到str1進(jìn)行完
		}
		if (sp.top() == *str2)
		{
			sp.pop();
			str2++;
		}
	}
	if (sp.empty())//如果棧為空，則出棧序列是合法的
	{
		return 1;
	}
	return 0;
}

測試用例如下：

void Test1()
{
	int arr1[] = { 1, 2, 3, 4, 5 };//入棧序列
	int str1[] = { 4, 5, 3, 1, 2 };//出棧序列
	//int str1[] = { 3, 2, 1, 5, 4 };//出棧序列
	OutStack s1(arr1, str1, 5, 5);
	cout << s1.Legality() << endl;

	char* arr2 = "abcdef";//入棧序列
	//char* str2 = "bafdce";//出棧序列
	char* str2 = "baefdc";//出棧序列
	OutStack s2(arr2, str2, 6, 6);
	cout << s2.Legality() << endl;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

分享名稱：判斷元素出棧，入棧順序的合法性-創(chuàng)新互聯(lián)
瀏覽地址：http://weahome.cn/article/diegho.html