首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列
  • 热度指数：788722 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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
算法知识视频讲解
添加回答
推荐
lizo头像 lizo 
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 回复(174)
Java
牛客885183922号头像 牛客885183922号 
  //1.遍历pushV数组每次入栈一个元素之后拿栈顶元素和popV的j下标比较是否一样，一样则可出栈
     //不一样i++
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushV.length;i++){
            stack.push(pushV[i]);
            while(!stack.empty() && j<popV.length && stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }

        return stack.empty();
    }

发表于 2025-07-30 18:04:48 回复(0)
Java
Slytherin_头像 Slytherin_
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
        boolean flag = false;
        int j=0;
        if(pushV.length==0)return flag;
        for(int i=0;i<pushV.length;i++){  
            stack.push(pushV[i]);    
            while(!stack.isEmpty() && j<popV.length && stack.peek()==popV[j]){
                j++;
                stack.pop();
            }          
        }
        if(stack.isEmpty())flag=true;
        return flag;
    }
}
发表于 2025-03-12 17:09:06 回复(0)
Java
17c89头像 17c89 
import java.util.*;

/**
 * NC272 栈的压入、弹出序列
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // return solution1(pushV, popV);
        // return solution11(pushV, popV);
        return solution2(pushV, popV);
        // return solution22(pushV, popV);
    }

    /**
     * 栈
     * @param pushV
     * @param popV
     * @return
     */
    private boolean solution1(int[] pushV, int[] popV){
        int n = popV.length;
        if(n == 0){
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        int target;

        // pushV index
        int j = 0;
        // popV index
        for(int i=0; i<n; i++){
            // 依次查找pop目标
            target = popV[i];
            if(stack.isEmpty()){
                // 当前栈为空 且 没有剩余待压入栈整数
                if(j == n){
                    return false;
                }
                // 当前栈为空 将下一个剩余整数压入栈
                stack.push(pushV[j++]);
            }
            // 栈顶不是目标整数
            while(stack.peek()!=target && j<n){
                // 目标整数在栈中
                if(stack.contains(target)){
                    return false;
                }
                stack.push(pushV[j++]);
            }
            if(stack.peek() == target){
                stack.pop();
            }else{
                return false;
            }
        }

        return true;
    }

    /**
     * 栈: 简化
     * @param pushV
     * @param popV
     * @return
     */
    private boolean solution11(int[] pushV, int[] popV){
        int n = popV.length;
        if(n == 0){
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        int target;

        // pushV index
        int j = 0;
        // popV index
        for(int i=0; i<n; i++){
            // 依次查找pop目标
            target = popV[i];
            // 栈为空 或 栈顶不是目标整数
            while((stack.isEmpty()||stack.peek()!=target) && j<n){
                // 目标整数在栈中
                if(stack.contains(target)){
                    return false;
                }
                stack.push(pushV[j++]);
            }
            if(stack.peek() == target){
                stack.pop();
            }else{
                return false;
            }
        }

        return true;
    }

    /**
     * 栈: 优化
     * @param pushV
     * @param popV
     * @return
     */
    private boolean solution2(int[] pushV, int[] popV){
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num: pushV){
            stack.push(num);
            while(!stack.isEmpty() && stack.peek()==popV[i]){
                stack.pop();
                i++;
            }
        }

        return stack.isEmpty();
    }

    /**
     * 模拟栈: 数组
     * @param pushV
     * @param popV
     * @return
     */
    private boolean solution22(int[] pushV, int[] popV){
        int j = 0;
        int i = 0;
        for(int num: pushV){
            pushV[j++] = num;
            while(j>0 && pushV[j-1]==popV[i]){
                j--;
                i++;
            }
        }

        return j==0;
    }
}

发表于 2025-02-05 12:28:10 回复(0)
Java
zzyccc_头像 zzyccc_
请教一下问题出在哪 
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();

        int i, j = 0;
        for (i = 0; i < pushV.length; i++) {
            if (pushV[i] == popV[j]){
                j++;
                if (!stack.isEmpty() && stack.peek() == popV[j]){
                    j++;
                    stack.pop();
                }
            } else {
                stack.push(pushV[i]);
            }
        }

        for (int k = 0; k < stack.size(); k++) {
            if (stack.pop() != popV[j]){
                return false;
            }
            j++;
        }

        return true;
    }


发表于 2024-09-15 11:22:05 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        if(pushV == null || popV == null) {
            return false;
        }

        int len1 = pushV.length;
        int len2 = popV.length;
        if(len1 != len2) {
            return false;
        }

        Stack<Integer> sta = new Stack<>();
        int j = 0;
        for(int i = 0; i < len1; i++) {
            sta.push(pushV[i]);
            while(!sta.isEmpty() && sta.peek() == popV[j]) {
                j++;
                sta.pop();
            }
        }
        return sta.isEmpty();
    }
}
发表于 2023-07-18 11:42:06 回复(0)
Java
Hadoopdoop头像 Hadoopdoop 
public class Solution {
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        List<Integer> listA = Arrays.stream(pushA).boxed().collect(Collectors.toList());
        List<Integer> listB = Arrays.stream(popA).boxed().collect(Collectors.toList());
        Stack<Integer> stack = new Stack<>();
        int first = listB.get(0);
        int index;
        for (index = 0; index < listA.size(); index++) {
            if (listA.get(index) != first) {
                stack.push(listA.get(index));
            } else {
                break;
            }
        }
        if (index >= listA.size()) return false;
        stack.push(listA.get(index));
        List<Integer> aList = listA.subList(index + 1, listA.size());
        Queue aQueue = new LinkedList();
        for (Integer it : aList) {
            aQueue.add(it);
        }
        Queue bQueue = new LinkedList();
        for (Integer it : listB) {
            bQueue.add(it);
        }
        return  judge(stack, aQueue, bQueue);
    }

    private boolean judge(Stack<Integer> stack, Queue<Integer> aQueue,
                          Queue<Integer> bQueue) {
        if (stack.isEmpty() && aQueue.isEmpty()  && bQueue.isEmpty()) {
            return true;
        }
        if (stack.isEmpty()  && !aQueue.isEmpty() && !bQueue.isEmpty()) {
            stack.push(aQueue.poll());
            return judge(stack, aQueue, bQueue);
        }
        if (!bQueue.isEmpty() && !stack.isEmpty() &&
                Objects.equals(bQueue.peek(), stack.peek())) {
            bQueue.poll();
            stack.pop();
            return judge(stack, aQueue, bQueue);
        }
        if (!bQueue.isEmpty() && !stack.isEmpty() && bQueue.peek() != stack.peek() &&
                !aQueue.isEmpty()) {
            stack.push(aQueue.poll());
            return judge(stack, aQueue, bQueue);
        }
        return false;
    }

}

发表于 2023-03-09 16:26:01 回复(0)
Java
码客明头像 码客明 
public boolean IsPopOrder(int [] pushA, int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int popAi = 0;
        int pushAi = 0;
        //先将首元素进行一个压栈的操作
        stack.push(pushA[pushAi++]);
        //下面进行循环当两个数组同时遍历完就退出
        while (pushAi < pushA.length || popAi < popA.length) {
            //因为要stack.peek()所以必须提前判断一下栈是否是空的
            //当栈顶元素与popA当前指向的元素相同时就出栈，popAi++
            if (!stack.empty() && stack.peek() == popA[popAi]) {
                popAi++;
                stack.pop();
            //当pushA数组没有遍历完的时候则进行压栈操作    
            } else if (pushAi < pushA.length) {
                stack.push(pushA[pushAi++]);
            //否则就是不正常情况直接退出循环就行了    
            } else {
                break;
            }
        }
        //判断一下栈是否为空，空的话就返回true
        if (stack.empty()) {
            return true;
        } else {
            return false;
        }
    }

发表于 2022-10-21 17:10:59 回复(0)
Java
ludvig头像 ludvig 
import java.util.Stack;

//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
//假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列
public class Solution {
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        int i = 0;
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        //模拟判断出栈序列是否合法的过程
        //如果想满足出栈序列
        //那么就挨个看出栈序列的元素，如果当前栈顶就是这个元素，那就出，否则就只能入栈 直到满足当前栈顶是我想出栈的那个元素
        //break:如果入栈序列都走完了，该入栈的元素都入了，没元素可入栈了,却还是不满足栈顶元素等于要出栈的元素 就break
        //最后判断:即出栈序列没遍历完 肯定就是false 遍历完 说明确实能这样出栈 返回true
        while (true) {
            if (!stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            } else {
                if (i < pushA.length) {
                    stack.push(pushA[i]);
                    i++;
                } else {
                    break;
                }
            }
        }
        if (j == popA.length) {
            return true;
        }
        return false;
    }
}

发表于 2022-10-20 18:26:09 回复(0)
Java
牛客949315280号头像 牛客949315280号 
import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int j = 0;//遍历popA数组
        for(int  i = 0;i < pushA.length;i++){
            stack.push(pushA[i]);
            //相同弹出去
            //j< popA.length防止j越界
            //!stack.empty()防止空栈异常
            while(j< popA.length && !stack.empty() && stack.peek(). equals(popA[j]) ){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

发表于 2022-09-24 20:51:27 回复(0)
Java
牛客39857374号头像 牛客39857374号 
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int push = 0;
        //正常情况下，当前pop的值要么在stack顶端，要么在剩下未push值里
        for (int pop = 0; pop < popA.length; pop++) {
            //在stack顶就弹出
            if (!stack.isEmpty() && stack.peek() == popA[pop]) {
                stack.pop();
                continue;
            }
            for (; push < pushA.length; push++) {
                //遍历push，如果和pop值相等，跳过，相当于已经push和pop了
                if (pushA[push] == popA[pop]) {
                    push++;
                    break;
                }
                //如果不相等，这些值还在需要pop的值前面，全部push进去
                if (pushA[push] != popA[pop]) {
                    stack.push(pushA[push]);
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 2022-09-09 02:37:52 回复(0)
Java
牛客208400313号头像 牛客208400313号 
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0, j = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
发表于 2022-08-17 10:23:59 回复(0)
Java
giasodgo头像 giasodgo 
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    	Stack stack = new Stack();
		int j=0;
		for(int i=0;i<pushA.length;i++) {
			stack.push(pushA[i]);
			while(stack.isEmpty()==false&&stack.top()==popA[j]){
				stack.pop();
				j++;
			}
		}
		if(stack.isEmpty()) {
			return true;
		}
		else {
			return false;
		}
    }
}

class Stack{
	private Node head;
	private int N;
	public class Node{
		int item;
		Node next;
		public Node(int item,Node next) {
			this.item=item;
			this.next=next;
		}
	}
	
	public Stack() {
		head=new Node(-99,null);
		N=0;
	}
	
	public boolean isEmpty() {
		return N==0;
	}
	
	public void push(int i) {
		Node lastNode = head.next;
		Node newNode = new Node(i,null);
		head.next=newNode;
		newNode.next = lastNode;
		N++;
	}
	
	public int pop() {
		if(head.next==null) {
			return -99;
		}
		Node lastNode = head.next.next;
		Node popNode = head.next;
		head.next=lastNode;
		N--;
		return popNode.item;
	}
	
	public int top() {
		if(head.next==null) {
			return -99;
		}
		else {
			return head.next.item;
		}
	}
}

发表于 2022-07-02 21:22:17 回复(0)
Java
勇敢牛牛不怕难头像 勇敢牛牛不怕难 
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA==null){
            return false;
        }
        if(pushA.length!=popA.length){
            return false;
        }
        int index=0;
        Stack<Integer> stack=new Stack<>();
        //压入操作
        for(int i=0;i<pushA.length;i++){
            if(pushA[i]!=popA[index]){
                stack.push(pushA[i]);
            }else{
                index++;
                //判断前面一个是否一样
                while(!stack.isEmpty()){
                    int val=stack.peek();
                    if(val==popA[index]){
                        index++;
                        stack.pop();
                    }else{
                        break;
                    }
                }
            }
        }
        //弹出操作
        while(!stack.isEmpty()){
            int val=stack.pop();
            if(val==popA[index]){
                index++;
            }else{
                return false;
            }
        }
    
        return true;
        
    }
}

发表于 2022-07-02 20:28:04 回复(0)
Java
班尼跑不死头像 班尼跑不死 
import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
        int j = 0 ;
        for(int i = 0 ; i < pushA.length; i++){
            stack.push(pushA[i]);//现将目标数组入栈
            while(!stack.empty()&&stack.peek() == popA[j]){
                //假如相同就出栈
                stack.pop();
                j++;
                //popA++
            }
        }
        if(stack.empty()){
            //假如栈为空那么就说明相同
            return true;
        }
        return false;
    }
}

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stack = new Stack<>();
        int j = 0 ;
        for(int i = 0 ; i < pushA.length; i++){
            stack.push(pushA[i]);//现将目标数组入栈
            while(!stack.empty()&&stack.peek() == popA[j]){
                //假如相同就出栈
                stack.pop();
                j++;
                //popA++
            }
        }
        if(stack.empty()){
            //假如栈为空那么就说明相同
            return true;
        }
        return false;
    }
}

发表于 2022-06-22 18:04:55 回复(0)
Java
txy_钟琛头像 txy_钟琛 
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (popA == null || pushA == null || popA.length == 0 || pushA.length == 0) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        for (; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }    
}

发表于 2022-05-26 11:47:49 回复(0)
Java
牛客753615531号头像 牛客753615531号
给出栈数组popA设一个指针，入栈过程中遇到值相等则出栈，并将指针移到下一位，不相等则继续入栈。最后pushA读完后，将剩余元素依次出栈，和出栈数组popA当前指针开始一一比较，都相同则可以是弹出序列
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack s=new Stack();
        int length=pushA.length;
        int j=0;
        for(int i=0;i<length;i++){
            s.push(pushA[i]);
            while(s.size()!=0){
            if((int)s.peek()==popA[j]){
                s.pop();
                j++;
            }else{
                break;
            }
            }
        }
        while(s.size()!=0){
            if((int)s.pop()!=popA[j])
                return false;
            j++;
        }
        return true;
    }
}
发表于 2022-05-14 20:49:28 回复(0)
Java
cxzO_o头像 cxzO_o 
import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0||popA.length==0){
              return false;
        }
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushA.length;i++){
            int val=pushA[i];
            stack.push(val);
            while(!stack.empty()&&j<popA.length&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

发表于 2022-05-12 14:24:59 回复(0)
Java
牛客637572510号头像 牛客637572510号 
import java.util.Stack;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA, int [] popA) {
        if (pushA == null || popA == null)return false;
        Stack<Integer> stack = new Stack<Integer>();
        int indexpop = 0;
        int indexpush = 0;
        while (indexpop < pushA.length) {
            while (stack.isEmpty() || indexpush < pushA.length &&
                    stack.peek() != popA[indexpop]) {
                stack.push(pushA[indexpush]);
                indexpush = indexpush + 1;//如果栈顶不是右边的index，就继续压栈
            }
            if (stack.pop() != popA[indexpop]) {
                return false;//如果栈顶不能把右边index取出来，false
            }
            indexpop = indexpop + 1;//一轮取出一个右边index
        }
        if (stack.isEmpty())return true;
        else return false;
    }
}

发表于 2022-03-29 20:45:55 回复(0)
提交观点

问题信息

栈
难度：
266条回答 183788浏览

热门推荐

通过挑战的用户

查看代码

相关试题

栈的压入、弹出序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号