问题
判断一数字序列是否为这些数字入栈的一种出栈方式（前提：栈中的数字不重复）
例如
假设入栈的序列为：1 2 3 4 5
那么4 5 3 2 1为一种弹出序列， 4 3 5 1 2不是
思路
开辟一个辅助栈，模拟入栈出战过程(假设pa为入栈序列，pb为出战序列)
- pa中的元素依次压入辅助栈
- 新压入的元素与弹出序列的栈底相同，辅助栈弹出，同时pb向上移动
- 不相同了pa中的元素继续入辅助栈
参考代码
#include <iostream> #include <stack> using namespace std; bool IsPopOrder(const int *a, const int *b, int lena, int lenb) { if(lena != lenb || lena == 0) return false; bool rev = false; int pa = 0; int pb = 0; int *newa = new int[lena]; int top = -1; for(pa = 0; pa < lena; ++pa) { ++top; newa[top] = a[pa]; while(newa[top] == b[pb]) { --top; ++pb; } } if(top == -1) rev = true; delete []newa; return rev; } int main() { int a[] = {1, 2, 3, 4, 5}; int b[] = {4, 5, 3, 2, 1}; int c[] = {4, 3, 5, 1, 2}; int d[] = {4, 5, 9, 2, 1}; int lena = sizeof(a) / sizeof(int); int lenb = sizeof(b) / sizeof(int); int lenc = sizeof(c) / sizeof(int); int lend = sizeof(d) / sizeof(int); cout << IsPopOrder(a, b, lena, lenb) << endl; cout << IsPopOrder(a, c, lena, lenc) << endl; cout << IsPopOrder(a, d, lena, lend) << endl; }
结果
1
0
0
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3618339.html，如需转载请自行联系原作者
