题目:
输入两个整数序列。其中一个序列表示栈的push 顺序,判断另一个序列有没有可能是对应的pop 顺序。
为了简单起见,我们假设push 序列的任意两个整数都是不相等的。
比如输入的push 序列是1、2、3、4、5,那么4、5、3、2、1 就有可能是一个pop 系列,但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。
思路一:
对Pop系列进行遍历,借用一个Stack的变量Sim来记录入栈的变量,在遍历的过程中不断的优先去找栈顶元素进行比较,如果比较结果不相等接了去找Push系列中的元素进行比较,不相等就Push到Sim来,反复这样的操作直到遍历完Pop系列。
(如果我们希望pop 的数字正好是栈顶数字,直接pop 出栈即可;如果希望pop 的数字目前不在栈顶,我们就到push 序列中还没有被push 到栈里的数字中去搜索这个数字,并把在它之前的所有数字都push 进栈。如果所有的数字都被push 进栈仍然没有找到这个数字,表明该序列不可能是一个pop 序列。)
代码如下:
/*----------------------------- Copyright by yuucyf. 2011.08.17 ------------------------------*/ #include "stdafx.h" #include <iostream> #include <stack> using namespace std; bool IsPopSeries(const char *pszPushSeries, const char *pszPopSeries) { if (NULL == pszPushSeries || NULL == pszPopSeries) return false; int i32PushLen= strlen(pszPushSeries); int i32PopLen = strlen(pszPopSeries); stack<int> stackSim; int i32I = 0, i32J = 0; int i32TempElem = 0; bool bFind = false; for (i32I = 0; i32I < i32PopLen; i32I++) { bFind = false; for (; i32J < i32PushLen; i32J++) { if (!stackSim.empty()) { if (stackSim.top() == pszPopSeries[i32I]) { stackSim.pop(); break; } } if (pszPopSeries[i32I] != pszPushSeries[i32J]) stackSim.push(pszPushSeries[i32J]); else { bFind = true; i32J++; break; } } if (!stackSim.empty() && i32J >= i32PushLen && !bFind) { i32TempElem = stackSim.top(); stackSim.pop(); if (i32TempElem != pszPopSeries[i32I]) return false; } } return true; } int _tmain(int argc, _TCHAR* argv[]) { char aszPushSeries[] = "12345"; char aszPopSeries[] = "12345"; cout << "push系列为" << aszPushSeries << ",那么系列" << aszPopSeries << "是否是它的一个Pop系列?(1是0不是)" << endl; cout << IsPopSeries(aszPushSeries, aszPopSeries) << endl; return 0; }