比如一個(gè)棧的壓棧順序?yàn)?绪囱，2，3莹捡，4鬼吵，5；那么3篮赢，2齿椅，1，4启泣，5就可能是棧的pop序列涣脚；
而4，2寥茫，3遣蚀，1，5就不可能，因?yàn)橐萷op 4妙同，就必須先把1射富，2，3粥帚，4壓棧進(jìn)去胰耗，那么要pop2 的話，先得pop3芒涡。
所以這個(gè)題就看你怎么去利用這個(gè)條件了柴灯。
我的思路是這樣的：有一個(gè)stack和兩個(gè)數(shù)組，push和pop费尽，兩個(gè)數(shù)組分別保存兩個(gè)序列赠群，stack是用來模擬pop和push的情況的。
首先我們要pop的數(shù)記為*popnode旱幼，然后我們?cè)跅＠锩鎸ふ疫@個(gè)值查描，如果找不到的話，我們看還有沒有剩下的未push的數(shù)字柏卤，如果有的話冬三，我們把它們都push進(jìn)去直到找到我們要pop的數(shù)字或者已經(jīng)把所有的數(shù)字都push進(jìn)去了。
舉個(gè)例子：
push[]={1,2,3,4,5},pop[]={4,3,2,1,5); popnode=4->push 1,2,3,4; pop 4; popnode=5->push 5; pop 5; pop 3,2,1
根據(jù)上面的思路寫出的代碼：
里面加入了一些輸出缘缚，debug的時(shí)候用的勾笆，也可以用來理清思路：
運(yùn)行結(jié)果
bool solution(int* push, int* pop, int len)
{
if (!pop || !push || len <= 0)
return false;
std::stack<int> s;
bool k = true;
int* popnode = pop;
int* pushnode = push;
while (popnode - pop < len)
{
while (s.empty()||(s.top() != *popnode&&(pushnode<len+push)))
{
if(!s.empty())
std::cout << "s.top=" << s.top() << " popnode=" << *popnode << "\n";
s.push(*pushnode++);
std::cout << "push:" << *(pushnode - 1)<<"\n";
}
if (s.top() == *popnode)
{
std::cout << "pop node :" << *popnode << std::endl;
s.pop();
popnode++;
}
else if ((pushnode - push >= len - 1))
{
std::cout << "to break"<<"\n";
k = false;
//popnode = pop + 5;
break;
//return false;
}
}
return k;
}
int main()
{
int push[] = { 1, 2, 3, 4, 5 };
int pop[] = {4,5,3,2,1 };//4,5,3,2,1
if (solution(push, pop, 5))
std::cout << "yes!";
else std::cout << "no!";
}
