在各大互联网公司的比试中，关于出栈问题基本上是必考的。问题的本质其实非常简单，稍加总结即可秒杀这类题！（这种问题秒杀一个是一个！）
老规矩，从题目入手
一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是：（） A edcbd B decba C dceab D abcde
栈之根本——后进先出（Last In First Out , LIFO）。初次接触到这个问题的人，或许会认为入栈abcde，出栈就只能是edcba。
其实是这个问题描述有歧义，应该是分段入栈的顺序，也就是说，可能先入栈a，再取出a，入栈b，再取出b……，所以D也是可能的，也就是说，并不是等所有元素都入栈了，才开始出栈。
知道这个意思了以后，就要明确这个问题的矛盾根本所在：第一次出栈d，说明什么？说明a，b，c一定早已入栈（入栈顺序决定的）。那么在出栈d以后，a，b，c的出栈顺序一定是c，b，a，而不用理会中间d后面再入栈的字符字符（因为可以再入栈，再出栈嘛）。所以立即选中C，不用犹豫，理由简单：d出栈了，abc一定已经入栈，那么abc只能以cba的顺序出栈，C不符合，OK！
总之，挨个看出栈序列的数据，根据入栈顺序，分析它出来时，栈中应该还有谁，谁还没入栈，然后分析此时可不可能是它出栈。
下面针对具体问题，编程来进行分析。
输入一个压栈序列，判断第二个序列是否为其出栈序列。
例如：入栈序列：1 2 3 4 5 6，出栈序列，4,3,5,2,6,1
算法思想，根据出栈序列，入栈，直到其当前栈顶元素等于出栈元素；如果所有元素均入栈后，都无法使得当前栈顶元素与出栈元素相同，则表明该出栈序列不否和！
根据入栈序列入栈：（左为栈顶）
栈：1 2 3 4 1 2 3 1 2 5 1 2 1 6 1 |空
出栈元素： 4 3 5 2 6 1 ， 4 3 5 2 6 1 ，4 35 2 6 1，4 3 5 2 6 1 ，4 3 5 26 1 ，4 3 5 2 61 ，完
#include <iostream>
#include <stack>
using namespace std;
bool IsStackPopOrder(int *pushorder, int *poporder, int len)
{
bool isorder = false;
if (pushorder != NULL && poporder != NULL && len > 0)
{
stack<int> s;
//入栈
int *pnextpush = pushorder;
//出栈
int *pnextpop = poporder;
//循环直到所有元素都已出栈
while ((pnextpop - poporder) < len)
{
//进栈直到当前元素与出栈元素相同
while (s.empty() || s.top() != *pnextpop)
{
if ((pnextpush - pushorder) == len)
{
break;
}
s.push(*pnextpush);
pnextpush++;
}
if (s.top() == *pnextpop)
{
s.pop();
pnextpop++;
}
else
{
break;
}
}
if ((pnextpop - poporder) == len && s.empty())
isorder = true;
}
return isorder;
}
void main()
{
int array1[7] = { 1, 2, 3, 4, 5, 6, 7 };
int array2[7] = { 4, 3, 5, 6, 7, 2, 1 };
if (IsStackPopOrder(array1, array2, 7))
cout << "是" << endl;
else
cout << "否" << endl;
system("pause");
}