首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列
  • 热度指数:753569 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
示例1

输入

[1,2,3,4,5],[4,5,3,2,1]

输出

true

说明

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列,返回true      
示例2

输入

[1,2,3,4,5],[4,3,5,1,2]

输出

false

说明

由于是[1,2,3,4,5]的压入顺序,[4,3,5,1,2]的弹出顺序,要求4,3,5必须在1,2前压入,且1,2不能弹出,但是这样压入的顺序,1又不能在2之前弹出,所以无法形成的,返回false      
推荐
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0) return false;
        vector<int> stack;
        for(int i = 0,j = 0 ;i < pushV.size();){
            stack.push_back(pushV[i++]);
            while(j < popV.size() && stack.back() == popV[j]){
                stack.pop_back();
                j++;
            }       
        }
        return stack.empty();
    }
};

编辑于 2015-08-12 17:04:16 回复(173)

【思路】借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,直到相等以后开始出栈,出栈一个元素,则将出栈顺序向后移动一位,直到不相等,这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。

举例:

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈,此时栈顶1≠4,继续入栈2

此时栈顶2≠4,继续入栈3

此时栈顶3≠4,继续入栈4

此时栈顶4=4,出栈4,弹出序列向后一位,此时为5,,辅助栈里面是1,2,3

此时栈顶3≠5,继续入栈5

此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3

….

依次执行,最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
 import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack<Integer> s = new Stack<Integer>();
        //用于标识弹出序列的位置
        int popIndex = 0;
        for(int i = 0; i< pushA.length;i++){
            s.push(pushA[i]);
            //如果栈不为空,且栈顶元素等于弹出序列
            while(!s.empty() &&s.peek() == popA[popIndex]){
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}
发表于 2016-05-04 19:26:17 回复(147)
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0||popA.length==0)
            return false;
		ArrayList<Integer> list  = new ArrayList<Integer>();
        int j = 0;
        for(int i = 0;i<pushA.length;i++){
            if(pushA[i]!=popA[j])
            	list.add(pushA[i]);
            else
                j++;
        }
        for(int i = list.size()-1;i>=0;i--){
            if(list.get(i)!=popA[j])
                return false;
            j++;
        }
        return true;
    }
}
编辑于 2016-04-15 19:48:13 回复(8)
   JavaScript版本:           
                 function IsPopOrder(arr1,arr2){
                        if(arr1.length==0 || arr2.length==0){
                            return;
                        }
                        var stack = [];
                        var index = 0;
                        for(var i=0;i<arr1.length;i++){
                            if(arr1[i]==arr2[index]){
                                index++;
                                while(stack.length>0 && stack[stack.length-1]==arr2[index]){
                                    stack.pop();
                                    index++;
                                }
                            }else{
                                stack.push(arr1[i]);
                            }
                        }
                        if(stack.length==0){
                            return true;
                        }else{
                            return false;
                        }                       
                    }
发表于 2018-12-06 23:09:12 回复(1)
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        unordered_map<int,int> p;
        for(int i = 0; i<pushV.size(); i++)
            p[pushV[i]] = i;
        int m = 0;    
        for(int i = 0; i<popV.size(); i++){
            if(p.find(popV[i]) == p.end()) return false;
            if(p[popV[i]] > m) m = p[popV[i]];
            else if(p[popV[i]] > p[popV[i-1]]) return false;
        }
        return true;    
    }
};

不用栈的解决方案,一个hash数组搞定。原理就是,如果第n个元素已经出栈,前面n-1个元素如果在n之后出栈的话一定是逆序出栈的。
编辑于 2017-09-18 23:16:26 回复(1)
参考 @lizo 同学的答案

class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        if (pushV.empty() || popV.empty()) return false;
        stack<int> s;
        int i = 0, j = 0;
        while (i < pushV.size()) {
            s.push(pushV[i++]);
            while (j < popV.size() && s.top() == popV[j]) {
                s.pop();
                ++j;
            }
        }
        
        return s.empty();
    }
};

发表于 2017-02-23 16:31:08 回复(0)
萌头像
class Solution {
public:
 bool IsPopOrder(vector<int> pushV, vector<int> popV) { 
  auto i = pushV.begin();
  while (s.size()<pushV.size()&&popV.size()>0)
  { 
   if (i != pushV.end())
   {
    s.push(*i);
    i++;
   }
   if (s.top()==*popV.begin())
   {
    s.pop();
    popV.erase(popV.begin(), popV.begin()+1);
   }
   else
   {
    if (i==pushV.end())
    {
     return false;
    }
   }
  }
  return popV.size() > 0 ? false : true;
 }
private:
 stack<int> s;
};

发表于 2016-07-27 17:48:58 回复(0)
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0 && 0 == popV.size())
            return false;
        stack<int> pushS;
        int pushP = 0, popP = 0;
        while(pushP < pushV.size())
            {
            pushS.push(pushV[pushP++]);
            while(popP < popV.size() &&pushS.top() == popV[popP])
            {
                ++popP;
                pushS.pop();
            }
        }
        if(popP != popV.size())
            return false;
        else
            return true;
    }
};
发表于 2016-04-11 17:18:51 回复(0)
//栈的压入、弹出序列
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
	bool flag=false;
	if(pushV.size() >0)
	{
		stack<int> s;
		unsigned int i=0; //指向pushV
		unsigned int j=0; //指向popV
		while(j<popV.size())
		{
			while((i<pushV.size()) && (s.empty() || s.top()!= popV[j]))
				s.push(pushV[i++]);
			if(s.top() != popV[j])
				break;
			else
			{
				s.pop();
				++j;
			}
		}
		if(s.empty() && j==popV.size())
			flag=true;
	}
	return flag;
}

发表于 2015-08-25 19:08:34 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
    def IsPopOrder(self, pushV, popV):
        # write code here
        self.stack.append(pushV.pop(0))
        while self.stack:
            if self.stack[-1] == popV[0]:
                self.stack.pop(-1)
                popV.pop(0)
            elif pushV:
                    self.stack.append(pushV.pop(0))
            else:
                return False
        return True
a little complex but easy to understand, simulate the situation when a stack works
发表于 2018-07-04 22:09:53 回复(2)
找到第一个出栈的元素在入栈序列中的序号,接下来只要看这个序号之前的元素是否符合出栈规则:
比如 1,2,3,4,5       3 先出, 那就只要看1和2在出栈序列中的序号分布,正确的出栈顺序
应该是2先1后,如果在出栈序列中出现了1先2后,直接返回false,否则(就这个例子来说),返回
true:
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV or not popV:
            return False
        
        for x in popV:
            if x not in pushV:
                return False
        
        firstIndex = pushV.index(popV.pop(0))
        for i in range(firstIndex - 1):
            for j in range(i+1, firstIndex):
                if i < j and popV.index(pushV[i]) < popV.index(pushV[j]):
                    return False
        return True

发表于 2017-07-07 19:59:48 回复(1)
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> sk;
        int idx = 0;//用于标识弹出序列的位置
        for(int i=0;i<pushV.size();i++){
            sk.push(pushV[i]);//先入栈
            //再循环判断当前栈顶元素是否是popV的出栈元素
            while(idx<popV.size()&&!sk.empty()&&popV[idx]==sk.top()){
                sk.pop();//出栈
                idx++;//弹出序列向后一位
            }
        }
        return sk.empty();//为空则为true
    }
};

发表于 2022-08-07 00:39:23 回复(0)
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int i=0;
        for(auto e:pushV)
        {
            st.push(e);

            while((!st.empty())&&st.top()==popV[i])
            {
                 st.pop();
                 i++;
            }
        }
        
        return st.empty();
    }
};

发表于 2022-07-30 09:51:29 回复(0)
while(auxStack.top() == popV[j] && j< popV.size()){
    ...
}
如果代码如上,先判定元素是否相等,运行时会判段错误(popV[j]数组越界了)。
所以,应该把j<size的判定写在前面。根据逻辑运算的短路原则:一旦j<size为真,则结束判断直接返回真,也就避免了数组越界的发生。
发表于 2021-09-15 16:28:45 回复(0)
class Solution:
    def IsPopOrder(self, pushV, popV):
        if not pushV&nbs***bsp;not popV:
            return False
        stack = []
        index = 0
        # 模拟进出栈过程
        for i in pushV:
            stack.append(i)
            while stack and stack[-1] == popV[index]:
                stack.pop()
                index += 1
        return stack == []

发表于 2021-08-12 21:12:22 回复(0)
使用JavaScript来实现

思路:
  1. 创建一个辅助栈stack,设置一个变量j(初始值为0)
  2. 循环第一个序列,将元素依次压入辅助栈stack中。同时要判断当前入栈的元素和第二个序列中第j个元素是否相等,如果相等,stack弹出一个元素,j++。这里要使用while循环来判断,因为如果连续入栈的话,出栈就得连续出栈。
  3. 如果最后stack为空,返回true,表示第二个序列是该栈的弹出顺序。否则返回false
function IsPopOrder(pushV, popV)
{
    // write code here
    let stack = [];
    let j = 0;
    let length = pushV.length;
    for(let i = 0;i < length;i++) {
        stack.push(pushV[i]);
                // 如果没有j<length显示条件,stack为空时,stack[-1]是undefined
                // popV[j]也是undefined,因为此时j已经超过了数组的长度,就是死循环了
        while(j < length && popV[j] === stack[stack.length - 1]) {
            stack.pop();
            j++;
        }
    }
    return stack.length === 0;
}
module.exports = {
    IsPopOrder : IsPopOrder
};
编辑于 2021-07-25 12:29:09 回复(0)
import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
            int p2Index = 0;
            for (int i = 0; i < pushA.length; i++) {
                stack.add(pushA[i]);
                while (!stack.isEmpty() && stack.peek() == popA[p2Index]){
                    p2Index++;
                    stack.pop();
                }
            }

            return p2Index == popA.length;
    }
}

发表于 2021-07-01 14:11:39 回复(0)
Python
栈的高度不同,结果也是不同的
例如:栈的高度为1,压入【1,2,3,4,5】,最后的答案也是【1,2,3,4,5】
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        index = 0
        for inV in pushV:
            stack.append(inV)
            while stack and stack[-1] == popV[index]:
                index +=1
                stack.pop()
        return len(stack)==0


发表于 2021-06-19 16:12:51 回复(0)
# -*- coding:utf-8 -*-
# 基本思想:按入栈顺序,将pushV的元素依次入stack栈,如果栈顶元素等于popV的第一个元素,
# 此时要将stack的栈顶元素出栈,并丢掉popV的第一个元素,此时,如果栈顶元素仍然等于popV的
# 第一个元素,则继续出战,直到值不相等时,继续将pushV的元素入栈,反复操作直到pushV为空。
# 此时只需要判断stack和popV是否相反,如果是,返回true, 否则返回false。

    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV&nbs***bsp;not popV:
            return False
        stack = []             # 定义一个栈
        equal = False          # 标志位,如果为true,则继续出栈操作,不进行入栈操作
        while pushV:
            if not equal or not stack:
                stack.append(pushV.pop(0))
            if stack[-1] != popV[0]:
                equal = False
                continue
            equal = True
            stack.pop()
            popV.pop(0)
        if len(stack) != len(popV):
            return False
        while stack:
            if stack.pop() != popV.pop(0):
                return False
        return True
    

编辑于 2021-05-24 23:54:01 回复(0)
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        for num in pushV:
            stack.append(num)
            if not stack and not popV:
                   return True
            while stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
                if not stack or not popV:
                    break
        if popV:
            return False
        return True
发表于 2021-05-02 20:44:12 回复(0)
献丑,请多指教,
建立空栈result和指针index;
遍历pushV中的元素,将当前元素入栈result;
执行while循环,在result不为空的条件下,比较popV中指针所在元素和result中栈顶元素;
如果相等,result出栈一次,指针+1;
如果result为空,返回True;
否则返回False。
(注意:在while循环过程中,result不会为空,只有最后一次才会出现为空的情况。)
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        result = []
        index = 0
        for i in pushV:
            result.append(i)
            while result != [] and result[-1] == popV[index]:
                result.pop()
                index += 1
        if result == []:
            return True
        return False


编辑于 2021-04-09 12:00:39 回复(0)