314-判断出栈序列是否可行

青旅半醒 2023-01-22 11:54 24阅读 0赞

# 判断出栈序列是否可行 #

## 题目如下 ##

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

**示例 1：**  
输入：pushed = \[1,2,3,4,5\], popped = \[4,5,3,2,1\]  
输出：true  
解释：我们可以按以下顺序执行：  
push(1), push(2), push(3), push(4), pop() -> 4,  
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

## 解题代码及注释 ##

#include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    
    bool IsPopOrder(vector<int> pushV, vector<int> popV)
    {
        
    	//第一步: 判断边界
    	if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
    		return false;
    
    	int len = pushV.size();//获取入栈序列的数组长度
    	stack<int> s;//定义一个栈
    	for (int i = 0, j = 0; i < len; ++i)//遍历入栈序列数组
    	{
        
    		s.push(pushV[i]);//入栈
    		while (!s.empty() && s.top() == popV[j])
    		//判断此时的栈顶元素是否和对应下标的出栈序列数组元素相等
    		{
        
    			s.pop();//出栈
    			++j;//j往后走
    		}
    	}
    	return s.empty();
    }
    
    int main()
    {
        
    	vector<int> a = {
         1,2,3,4,5 };
    	vector<int> b = {
         4,5,3,2,1 };
    	cout << IsPopOrder(a, b) << endl;
    
    	return 0;
    }

## 运行截图如下 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/888c312d6d2349428b1e27c21d97a7cb.png