输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId

解题思路：

首先遍历要被压入栈的vector，在遍历的同时对比给出的假设出栈顺序的vector第一个元素，如果相等，那么删除入栈的那个元素，同时将假设出栈的vector将要对比的位置后移。

如果不相等那么就继续入下一个元素，假设出栈顺序的vector指针位置不变。遍历完成后判断栈是否为空，如果为空那么证明是它的胡出栈顺序，反之则不是。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
	bool IsPopOrder(vector<int> pushV, vector<int> popV)
	{
		stack<int> stmp;
		int i=0;
		/* 遍历要压栈的vector */
		for (auto &vi:pushV)
		{
			stmp.push(vi);
			for (;!stmp.empty()&&stmp.top()==popV[i];++i)
			{
				stmp.pop();
			}
		}
		return stmp.empty();
	}
};
int main()
{
	vector<int> puv{ 1,2,3,4,5 };
	vector<int> pov{ 4,5,3,2,1 };
	Solution test;
	cout << test.IsPopOrder(puv, pov);
	/*stack<int> s;
	s.push(1);
	s.push(2);
	cout << s.empty();*///不为空的时候返回0
	system("pause"); 
	return 0;
}

最后

以上就是清秀面包为你收集整理的输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。的全部内容，希望文章能够帮你解决输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。