加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

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

(2015-11-08 09:54:10)
标签：

判断一个序列是不是栈

教育

数据结构

it

 分类： 数据结构

题目描述：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5、6、7，那么2、1、4、3、7、5、6就有可能是一个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，这时候和输出序列的第一个元素相等，我们就把输出序列的下标加一，而输入序列删除该元素，这时候输出序列的元素为4，先跟栈顶元素2比较，发现不相等，这时候元素要么在输入序列的后面，要么就没有，我们在输入序列里面寻找，此时的输入序列指到元素4正好和输出序列的元素相等，于是我们把输出序列和输入序列的下标都加上1，此时输入序列已经弄完了，而输出序列指着2，我们也先和栈顶元素比较，发现它们相等，于是我们把栈顶元素删除，同时输出序列的下标加1，这时候输出序列指到元素1，我们再和栈顶元素比较，发现它们相等，于是我们把栈顶元素删除，同时输出序列的下标加1。这时候我们发现栈为空，而且输入序列的下标已经直到输入序列的末尾，这说明输出序列是栈的输出序列，我们返回true，否则我们返回false;代码实现如下所示：

 

       
  1. #include   
  2.   
  3. #include   
  4. #include   
  5.   
  6. using namespace std;  
  7.   
  8. bool IsPopOrder(const vector<</span>int> & Push, const vector<</span>int> & Pop){  
  9.     if(Push.size() != Pop.size()){  
  10.         return false;  
  11.     }  
  12.       
  13.     stack<<span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); font-weight: bold; background-color: inherit;">int>temp;  
  14.     int tempIndex = 0;  
  15.     int tempIndex2 = 0;  
  16.     int Size = Pop.size();  
  17.       
  18.     while(tempIndex2 < Size){  
  19.         for(; tempIndex < Size; tempIndex++){  
  20.             if(Push[tempIndex] == Pop[tempIndex2]){  
  21.                 tempIndex2++;  
  22.                 tempIndex++;  
  23.                 break;  
  24.             }  
  25.             temp.push(Push[tempIndex]);  
  26.         }  
  27.           
  28.         if(!temp.empty() && temp.top() != Pop[tempIndex2]){  
  29.               
  30.             for(; tempIndex < Size; tempIndex++){  
  31.                 if(Push[tempIndex] == Pop[tempIndex2]){  
  32.                     tempIndex2++;  
  33.                     tempIndex++;  
  34.                     break;  
  35.                 }  
  36.                 temp.push(Push[tempIndex]);  
  37.             }  
  38.         }else if(!temp.empty()){  
  39.             temp.pop();  
  40.             tempIndex2++;  
  41.         }  
  42.         if(!temp.empty() && tempIndex >= Size && temp.top() != Pop[tempIndex2]){  
  43.             return false;  
  44.         }else{  
  45.             while(!temp.empty() && temp.top() == Pop[tempIndex2]){  
  46.                 temp.pop();  
  47.                 tempIndex2++;  
  48.             }  
  49.         }  
  50.           
  51.     }  
  52.       
  53.     if(temp.empty() && tempIndex >= Size){  
  54.         return true;  
  55.     }  
  56.       
  57.     return false;  
  58. }  
  59. int main(){  
  60.     vector<<span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); font-weight: bold; background-color: inherit;">int> Push, Pop;  
  61.     //1      1  
  62.     //1      2  
  63.     //1, 2, 3, 4, 5         3, 5, 4, 1, 2  
  64.     //1, 2, 3, 4, 5         4, 3, 5, 1, 2  
  65.     //1, 2, 3, 4, 5         3, 5, 4, 2, 1  
  66.     //1, 2, 3, 4, 5         4, 5, 3, 2, 1  
  67.     //1, 2, 3, 4, 5         3, 5, 4, 2, 1  
  68.     Push.push_back(1);  
  69.     Push.push_back(2);  
  70.     Push.push_back(3);  
  71.     Push.push_back(4);  
  72.     Push.push_back(5);  
  73.     Push.push_back(6);  
  74.     Push.push_back(7);  
  75.       
  76.     Pop.push_back(2);  
  77.     Pop.push_back(1);  
  78.     Pop.push_back(4);  
  79.     Pop.push_back(3);  
  80.     Pop.push_back(7);  
  81.     Pop.push_back(5);  
  82.     Pop.push_back(6);  
  83.   
  84.     cout << IsPopOrder(Push, Pop) << endl;  
  85.     return 0;  
  86. }  

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有