題目描述：給定一個(gè)入棧序列，給定一個(gè)出棧序列，判斷該出棧序列是否合法。

10年積累的成都網(wǎng)站建設(shè)、網(wǎng)站制作經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有常寧免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

分析：假如入棧序列為1 2 3 4 5，判斷4 5 3 2 1 是否是合法的出棧順序。

兩個(gè)序列均以數(shù)組的形式給出

從兩個(gè)數(shù)組的第一個(gè)元素開始，如果棧為空，或者，棧頂元素不等于當(dāng)前出棧數(shù)組當(dāng)前下標(biāo)對(duì)應(yīng)的元素時(shí)，將當(dāng)前入棧數(shù)組中下標(biāo)所指向的元素進(jìn)行壓棧

初始狀態(tài)如下：

步驟1：把 1 進(jìn)行壓棧，并將下標(biāo)后移，如下圖所示，

步驟2：依次進(jìn)行判斷并壓棧，當(dāng)4進(jìn)棧后，此時(shí)棧頂元素等于出棧數(shù)組下標(biāo)所指向的元素，將4出棧，如下圖所示

步驟3：將 4 出棧，并將出棧數(shù)組的下標(biāo)后移，繼續(xù)判斷棧頂元素是否為當(dāng)前出棧數(shù)組下標(biāo)對(duì)應(yīng)的元素，是，則出棧，否則繼續(xù)往后執(zhí)行

步驟4：重復(fù)上述步驟，直到入棧數(shù)組中的下標(biāo)走到盡頭

當(dāng)最后一個(gè)元素入棧后，此時(shí)只需循環(huán)判斷棧頂元素是否與出棧數(shù)組當(dāng)前下標(biāo)對(duì)應(yīng)的元素相等，如果該序列合法，則棧中的元素最終都會(huì)出棧，不合法則棧永遠(yuǎn)不為空

此時(shí)，棧為空，則該序列合法。

代碼如下：

#include<iostream>
#include<stack>
#include<cassert>
using namespace std;


template<class T>
bool IsSequenceVaild(const T* inSequence, const T* outSequence, size_t n)
{
	assert(inSequence && outSequence);

	stack<T> sc;
	int j = 0;  //用來記錄出棧數(shù)組當(dāng)前元素的下標(biāo)
	for (int i = 0; i < n; ++i)
	{
		sc.push(inSequence[i]);

		while (!sc.empty() && sc.top() == outSequence[j])
		{
			sc.pop();
			++j;
		}
	}

	return (sc.size() == 0) ? true : false;
}


void Test1()
{
	int in[5] = { 1, 2, 3, 4, 5 };
	int out1[5] = { 1, 2, 3, 4, 5 };
	int out2[5] = { 4, 5, 3, 2, 1 };
	int out3[5] = { 3, 5, 4, 2, 1 };
	int out4[5] = { 3, 5, 4, 2, 1 };

	int out[5] = { 4, 5, 3, 1, 2 };

	cout << IsSequenceVaild<int>(in, out1, 5) << endl;
	cout << IsSequenceVaild<int>(in, out2, 5) << endl;
	cout << IsSequenceVaild<int>(in, out3, 5) << endl;
}

void main()
{
	Test1();

	system("pause");
}

網(wǎng)站標(biāo)題：給定入棧順序，判斷出棧順序是否合法
文章轉(zhuǎn)載：http://www.chinadenli.net/article0/jdhiio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、品牌網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站收錄、網(wǎng)站制作、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)