首页 > 试题广场 > 栈的压入、弹出序列
[编程题]栈的压入、弹出序列
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
推荐
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 回复(144)

【思路】借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是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 回复(121)

python 解法,模拟这个过程就可以了。


# -*- coding:utf-8 -*-
class Solution:

    def IsPopOrder(self, pushV, popV):
        # stack中存入pushV中取出的数据
        stack=[]
        while popV:
            # 如果第一个元素相等,直接都弹出,根本不用压入stack
            if pushV and popV[0]==pushV[0]:
                popV.pop(0)
                pushV.pop(0)
            #如果stack的最后一个元素与popV中第一个元素相等,将两个元素都弹出
            elif stack and stack[-1]==popV[0]:
                stack.pop()
                popV.pop(0)
            # 如果pushV中有数据,压入stack
            elif pushV:
                stack.append(pushV.pop(0))
            # 上面情况都不满足,直接返回false。
            else:
                return False
        return True
发表于 2017-10-13 18:33:14 回复(20)
 public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA.length == 0 || popA.length == 0) {
			return false;
		}
      Stack<Integer> stack = new Stack<Integer>();
		int j = 0;
		for (int i = 0; i < popA.length; i++) {
			stack.push(pushA[i]);
			while (j < popA.length && stack.peek() == popA[j]) {
				stack.pop();
				j++;
			}

		}
		return stack.empty() ? true : false;
    }
发表于 2015-10-05 14:21:25 回复(18)
/*C++
模拟堆栈操作:将原数列依次压栈,栈顶元素与所给出栈队列相比,如果相同则出栈,
如果不同则继续压栈,直到原数列中所有数字压栈完毕。
检测栈中是否为空,若空,说明出栈队列可由原数列进行栈操作得到。否则,说明出栈队列不能由原数列进行栈操作得到。
*/
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> s;
        int j=0;
        for(int i=0;i<pushV.size();++i){
            s.push(pushV[i]);
            while(!s.empty()&&s.top()==popV[j]){
                s.pop();
                ++j;
            }
        }
        if(s.empty())
            return true;
        return false;
    }
};

发表于 2016-04-11 21:24:00 回复(10)
看了一下,大家基本都是用栈来模拟过程,其实这题有个递归思路来解,假设pushA中的元素为Xi,popA被X0分割成两个序列p1和p2,因为X0是第一个入栈的元素,所以p1中的元素必定比p2中的元素先入栈,这两个序列必然都满足弹出序列
设p1长度为m,则p1对应的入栈序列为X[1:m+1],p2对应X[m+1:n],n是原来序列的长度。
import java.util.Arrays;
 
 public class PopOrder { 
  
  public boolean IsPopOrder(int [] pushA,int [] popA) {
   int length=popA.length;
   if(length==0)
   return true;
   if(length==1)
     return popA[0]==pushA[0];
   int i;
   for (i = 0; i < popA.length; i++) {
   if(popA[i]==pushA[0])
   break;
   }
   return IsPopOrder(Arrays.copyOfRange(pushA, 1, i+1),Arrays.copyOfRange(popA, 0, i)) &&
 IsPopOrder(Arrays.copyOfRange(pushA, i+1, length),Arrays.copyOfRange(popA, i+1,length));
 }
 
 

编辑于 2018-12-03 12:14:37 回复(10)
/*思路:先循环将pushA中的元素入栈,遍历的过程中检索popA可以pop的元素
**如果循环结束后栈还不空,则说明该序列不是pop序列。
**文字有点难说明白,看代码。
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(ArrayList<Integer> pushA,ArrayList<Integer> popA) {
        Stack stack = new Stack();
        if( pushA.size() == 0 && popA.size() == 0 ) return true;
        for( int i=0,j=0; i < pushA.size(); i++ ){
            stack.push( pushA.get(i) );
            while( ( !stack.empty() )&& ( stack.peek() == popA.get(j) ) ){
                stack.pop();
                j ++;
            } 
        }
        
        return stack.empty() == true;
    }
}

编辑于 2015-05-06 16:28:49 回复(9)

题目描述

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

解题思路

一开始都看不懂题目...

后来才好像明白是什么个意思...

假设有一串数字要将他们压栈: 1 2 3 4 5

如果这个栈是很大很大,那么一次性全部压进去,再出栈:5 4 3 2 1

但是,如果这个栈高度为4,会发生什么? 1 2 3 4都顺利入栈,但是满了,那么要先出栈一个,才能入栈,那么就是先出4,然后压入5,随后再全部出栈:4 5 3 2 1

那么我总结了所有可能的出栈情况:

5 4 3 2 1//栈高度为5

4 5 3 2 1//栈高度为4

3 4 5 2 1//栈高度为3

2 3 4 5 1//栈高度为2

1 2 3 4 5//栈高度为1

借助一个辅助的栈,遍历压栈的顺序,依次放进辅助栈中。

对于每一个放进栈中的元素,栈顶元素都与出栈的popIndex对应位置的元素进行比较,是否相等,相等则popIndex++,再判断,直到为空或者不相等为止。

我的答案

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;
        }

        //弹出序列的下表索引
        int popIndex = 0;

        //辅助栈
        Stack<Integer> stack = new Stack<Integer>();

        for(int i=0;i<pushA.length;i++){
            //不停地将pushA中的元素压入栈中,一旦栈顶元素与popA相等了,则开始出栈
            //不相等则继续入栈
            stack.push(pushA[i]);
            while(!stack.isEmpty() && stack.peek()==popA[popIndex]){
                stack.pop();
                popIndex++;
            }
        }
        //栈中没有元素了说明元素全部一致,并且符合弹出顺序,那么返回true
        return stack.isEmpty();
    }
}
编辑于 2019-03-08 10:39:35 回复(10)

某算法竞赛书原题

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> s;
        int A = 0, B = 0;
        bool ans = true;
        while(B < pushV.size()){
            if(pushV[A] == popV[B]) {A++; B++; }
            else if(!s.empty() && s.top() == popV[B]) {s.pop(); B++; }
            else if(A < pushV.size()) s.push(pushV[A++]);
            else {ans = false; break;}
        }
        return ans;
    }
};
发表于 2018-12-02 16:05:34 回复(0)
# 只有我是纯分析栈的特点这么做的么?
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        min_i = 0
        popped = []
        for j in popV:
            popped.append(j)
            for i in range(len(pushV)):
                if pushV[i] == j:
                    if i < min_i:
                        return False
                    while i > 0:
                        if pushV[i - 1] not in popped:
                            min_i = i - 1
                            break
                        else:
                            i -= 1
                    break
            else:
                return False
        return True
#看了大家的思路后,果然模拟还行哈哈。
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        for psh in pushV:
            stack.append(psh)
            if stack[-1] == popV[0]:
                popV.pop(0)
                stack.pop()
        for pp in popV:
            if pp == stack[-1]:
                stack.pop()
        return stack == []


编辑于 2017-11-02 02:04:14 回复(2)
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 回复(6)
import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> s = new Stack<>();
      int i = 0;
      for(int a: pushA)
      {
    	  s.push(a);
    	  while(!s.isEmpty() && s.peek() == popA[i])
    	  {
    		  s.pop();
    		  i++;
    	  }
      }
      if(s.isEmpty()) return true;
      return false;
    }
}

发表于 2016-08-03 14:21:15 回复(3)
class Solution {
public:
	bool IsPopOrder(vector<int> pushV, vector<int> popV) {
		int i = 0, j = 0, len = pushV.size();
		stack<int> st;
		st.push(pushV[i++]);
		while (i < len || j < len)
		{
			if (st.top() == popV[j])
			{
				j++;
				st.pop();
			}
			else
			{
				if (i < len)
					st.push(pushV[i++]);
				else
					return false;
			}
		}
		return true;
	}
};

发表于 2016-07-25 00:16:36 回复(1)

好多人用辅助栈来求解,完全没有必要!我的思路:取出弹出序列的第一个元素,然后找到此元素
在入栈序列的位置n,那么入栈序列的前n个元素如果依次等于弹出序列从后往前数的n个元素,那么此 弹出序列就是正确的弹出序列!代码如下,测试已通过: class Solution { public:     bool IsPopOrder(vector<int> pushV,vector<int> popV) {         if(pushV.size()!=popV.size())             return false;         int address=-1;
for(int i=0;i<pushV.size();i++) // 找弹出序列的第一个元素在入栈序列中的位置         {             if(pushV[i]==popV[0])                 address=i;         }         if(address==-1)// 没找到,失败             return false;   // 将弹出序列逆序显示         vector<int> temp=vector<int>(popV.rbegin(),popV.rend());         for(int i=0;i<address;i++)         {             if(pushV[i]!=temp[i])// 若有一个不相等,失败                 return false;         }         return true;     } };

编辑于 2018-01-21 16:45:08 回复(10)
    # 用一个栈stack模拟
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        while(True):
            if not popV: # 如果压入、弹出序列已经顺利模拟完毕,则模拟成功
                return True
            if not stack or popV[0] != stack[-1]: # 如果栈顶元素不是该弹出的元素,则继续入栈
                if not pushV: # 如果全部元素都已入栈却不能弹出,则模拟失败
                    return False
                stack.append(pushV.pop(0))
            else: # 如果当前栈顶元素就是该弹出的元素则弹出
                stack.pop()
                popV.pop(0)

发表于 2019-06-10 00:32:10 回复(0)
   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)
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        j = 0
        for i in pushV:
            stack.append(i)
            while len(stack)>0 and popV[j] == stack[len(stack)-1]:
                stack.pop()
                j+=1
        return len(stack)==0

发表于 2018-01-19 13:50:59 回复(0)
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 回复(0)
用一个容器模仿压入栈,从左到右扫描出栈序列,每次压栈后将满足出栈条件的元素出栈,最后判断
容器是否为空,空说明所有元素都成功出栈,否则有元素未成功出栈,出栈序列错误。

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	for(int i = 0,j = 0; i < pushA.length; i++) {
    		list.add(pushA[i]);
    		while(!list.isEmpty() && list.get(list.size()-1) == popA[j] ) {
    			list.remove(list.size()-1);
    			++j;
    		}	
    	}
    	return list.isEmpty();
    }
}

发表于 2017-03-22 22:19:31 回复(3)
参考 @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)