欢迎关注Hadoop、Spark、Flink、Hive、Hbase、Flume等大数据资料分享微信公共账号:iteblog_hadoop
  1. 文章总数:978
  2. 浏览总数:11,981,182
  3. 评论:3939
  4. 分类目录:106 个
  5. 注册用户数:6130
  6. 最后更新:2018年12月15日
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
iteblog_hadoop
大数据技术博客公众号bigdata_ai
大数据猿:
bigdata_ai

判断一个序列是不是栈的输出序列

题目描述:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5、6、7,那么2、1、4、3、7、6、5就有可能是一个pop系列。但序列4、3、5、1、2、7、6就不可能是push序列1、2、3、4、5的pop序列。

问题分析:解决这个问题我们可以申请一个栈,然后从输入序列开头一个一个判断是否等于输出序列的头。举个简单的例子。比如输入序列为1、2、3、4输出序列为3、4、2、1,这是输出序列第一个数字为3,我们就从输入序列开始寻找3,直到找到3,而假如3之前有数据我们就把它们存入栈中,在输入序列中,开始碰到的是1元素,和输出序列的第一个元素不相等,我们就把1放入栈中,然后就是2元素,也不想等,也放入栈中,然后就是3,这时候和输出序列的第一个元素相等,我们就把输出序列的下标移到2,而输入序列的下标移到3,这时候输出序列的元素为4,先个栈顶元素比较,发现不相等,这时候元素要么在输入序列的后面,要么就没有,我们在输入序列里面寻找,此时的出入序列指到元素4正好和输出序列的元素相等,于是我们把输出序列和输入序列的下标都加上1,此时输入序列已经弄完了,而输出序列指着2,我们也先和栈顶元素比较,发现它们相等,于是我们把栈顶元素删除,同时输出序列的下标加1,这时候输出序列直到元素1,我们再和栈顶元素比较,发现它们相等,于是我们把栈顶元素删除,同时输出序列的下标加1。这时候我们发现栈为空,而且输入序列的下标已经直到输入序列的末尾,这说明输出序列是栈的输出序列,我们返回true,否则我们返回false;代码实现如下所示:


#include <iostream>
/*
* author: w397090770
* Email:wyphao.2007@163.com
* 仅用于学习交流之用
**/
#include <vector>
#include <stack>

using namespace std;

bool IsPopOrder(const vector<int> & Push, const vector<int> & Pop){
 if(Push.size() != Pop.size()){
 return false;
 }

 stack<int>temp;
 int tempIndex = 0;
 int tempIndex2 = 0;
 int Size = Pop.size();

 while(tempIndex2 < Size){
 for(; tempIndex < Size; tempIndex++){
 if(Push[tempIndex] == Pop[tempIndex2]){
 tempIndex2++;
 tempIndex++;
 break;
 }
 temp.push(Push[tempIndex]);
 }

 if(!temp.empty() && temp.top() != Pop[tempIndex2]){

 for(; tempIndex < Size; tempIndex++){
 if(Push[tempIndex] == Pop[tempIndex2]){
 tempIndex2++;
 tempIndex++;
 break;
 }
 temp.push(Push[tempIndex]);
 }
 }else if(!temp.empty()){
 temp.pop();
 tempIndex2++;
 }
 if(!temp.empty() && tempIndex >= Size && temp.top() != Pop[tempIndex2]){
 return false;
 }else{
 while(!temp.empty() && temp.top() == Pop[tempIndex2]){
 temp.pop();
 tempIndex2++;
 }
 }

 }

 if(temp.empty() && tempIndex >= Size){
 return true;
 }

 return false;
}
int main(){
 vector<int> Push, Pop;
 //1 1
 //1 2
 //1, 2, 3, 4, 5 3, 5, 4, 1, 2
 //1, 2, 3, 4, 5 4, 3, 5, 1, 2
 //1, 2, 3, 4, 5 3, 5, 4, 2, 1
 //1, 2, 3, 4, 5 4, 5, 3, 2, 1
 //1, 2, 3, 4, 5 3, 5, 4, 2, 1
 Push.push_back(1);
 Push.push_back(2);
 Push.push_back(3);
 Push.push_back(4);
 Push.push_back(5);
 Push.push_back(6);
 Push.push_back(7);

 Pop.push_back(2);
 Pop.push_back(1);
 Pop.push_back(4);
 Pop.push_back(3);
 Pop.push_back(7);
 Pop.push_back(5);
 Pop.push_back(6);

cout << IsPopOrder(Push, Pop) << endl;
 return 0;
}

(转载请注明:https://www.iteblog.com/archives/14,请不要用于商业目的。)

本博客文章除特别声明,全部都是原创!
转载本文请加上:转载自过往记忆(https://www.iteblog.com/)
本文链接: 【判断一个序列是不是栈的输出序列】(https://www.iteblog.com/archives/14.html)
喜欢 (3)
分享 (0)
发表我的评论
取消评论

表情
本博客评论系统带有自动识别垃圾评论功能,请写一些有意义的评论,谢谢!