首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列
  • 热度指数：756207 时间限制：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
算法知识视频讲解
添加回答
推荐
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 回复(173)
Javascript
牛客341739935号头像 牛客341739935号
function IsPopOrder(pushV, popV)
{
    // write code here
    let stack = [];
    let o = 0; // 出栈索引
    let i = 0; // 入栈索引
    while (i < pushV.length) {
        stack.push(pushV[i]);
        i++;
        while (stack.length > 0 && popV[o] === stack[stack.length - 1]) {
            stack.pop();
            o++;
        }
    }
    return !stack.length;
}
发表于 2022-08-03 13:45:41 回复(0)
Javascript
A-成都搬砖日结包吃不包住头像 A-成都搬砖日结包吃不包住 
function IsPopOrder(pushV, popV) {
  // write code here
    // 还有双指针法可以使用
  let steps = pushV.length + popV.length;
  let stack = [];
  let i = 0;
  while (i < steps) {
    // 执行步骤,先入栈
    if (i < pushV.length) stack.push(pushV[i]);

    // 进行是否出栈判断
    while (stack.length && stack[stack.length - 1] === popV[0]) {
      stack.pop();
      popV.shift();
    }
    i++;
  }
  return !popV.length;
}
发表于 2022-03-09 10:57:17 回复(0)
Javascript
我不吃羊肉头像 我不吃羊肉 
function IsPopOrder(pushV, popV)
{
    // write code here
    let p1 = 0;
    
    let stack = [];
    
    for(let i=0; i < pushV.length; i++) {
        stack.push(pushV[i]);
        
        while (stack && p1 < popV.length && stack[stack.length - 1] === popV[p1]) {
            stack.pop();
            p1++;
        }
    }
   
    if (stack.length === 0) return true;
    
    return false;
    
}

发表于 2022-02-28 10:43:14 回复(0)
Javascript
牛客760559747号头像 牛客760559747号
function IsPopOrder(pushV, popV)
{
    // write code here
    let stack = []
    let value  = popV[0]  //记录该要出栈的值
    while(popV.length){        
        if(pushV.length&&stack[stack.length-1]!==value){    //若栈顶元素不等于value，且还有需要入栈的值
            stack.push(pushV.shift())
        }
        if(stack[stack.length-1]===value){      // 栈顶元素等于要value
            stack.pop()
            popV.shift()
            value = popV[0]
            continue                           // 跳过false判定
        }
        if(!pushV.length) return false         //如果元素已经全部入栈时栈顶元素不等于value
    }
        return true
    
}
module.exports = {
    IsPopOrder : IsPopOrder
};
发表于 2021-12-29 11:37:51 回复(0)
Javascript
果冻~头像 果冻~ 
function IsPopOrder(pushV, popV)
{
    // write code here
    let stack = [];
    for(let i = 0; i < pushV.length; i++){
        stack.push(pushV[i]);
        while(stack.length&&stack[stack.length-1]===popV[0]){
            stack.pop();
            popV.shift();
        }
    }
    return stack.length==0;
}


发表于 2021-09-08 15:26:25 回复(0)
Javascript
十味一心头像 十味一心 
function IsPopOrder(pushV, popV)
{
    // write code here
    if(pushV == null && popV == null) return;
    let stack = [];
    let index = 0;
    
    for(let i = 0;i < pushV.length; i++){
        stack.unshift(pushV[i]);
        while(stack.length && stack[0] == popV[index]){
            index++;
            stack.shift();
        }
    }
    return (stack.length == 0);
}

发表于 2021-09-01 11:15:46 回复(0)
Javascript
牛客512597024号头像 牛客512597024号
js实现

function IsPopOrder(pushV, popV)
{
    //有俩种情况，第一种刚入栈就出栈，再第一种情况下第二种连续出栈
    let stack=[]//模拟出栈入栈,如果出栈序列是正确的那么出栈完毕后模拟栈应该是空的
    let i=j=0//指针指向出栈入栈
    // 如果pushV[i] != popV[j]， 那么应该将pushV[i]放入栈中， ++i
    // 否则，pushV[i]==popV[j], 说明这个元素是放入栈中立马弹出，所以，++i, ++j，然后应该检查popV[j]
    // 与栈顶元素是否相等，如果相等，++j, 并且弹出栈顶元素
    while(i!=pushV.length){//如果入栈的指针走到了最后就说明入栈完毕，那么栈中剩下的数只有全部出栈了
        if(pushV[i] != popV[j]){
            stack.push(pushV[i])//入栈
             i++
        }
        if(pushV[i]==popV[j]){
            j++//说明刚入栈就出栈了
            i++
            while(stack[stack.length-1]==popV[j]&&j!=pushV.length){//判断是不是连续出栈
                stack.pop()
                j++
            }
        }
    }
    //入栈完毕说明不会再有入栈的对象 所以只需要判断最后出栈的数是不是与栈中的数一样就可以了
    while(j!=pushV.length&&stack.length!=0){
        if(stack[stack.length-1]==popV[j]){
            stack.pop()
        }
        j++
    }
    if(stack.length==0) return true
    return false
}
发表于 2021-08-15 19:40:48 回复(0)
Javascript
牛客822067661号头像 牛客822067661号
js 
function IsPopOrder(pushV, popV)
{

    let x = pushV.indexOf(popV[0]);
    //初始化栈数组
    let stack = pushV.slice(0, x + 1);
    //剩余未入栈数组
    let last = pushV.slice(x + 1);
    //全部入栈
    if(last.length === 0){
        for(let k = 0; k < stack.length; k++){
            if(stack[k]!==popV[stack.length-k-1]){
                return false
            }
        }
    }
    popV.shift();
    stack.pop();
    if(popV.length===0&&last.length!==0){
        return false;
    }
    while(popV.length !== 0){
        //当前栈含有出栈第一个
        if(stack.indexOf(popV[0])!==-1){
            console.log("1:",stack,last,popV)
            if(stack[stack.length-1]!==popV[0]){
                console.log("f1")
                return false  
            }else{
                popV.shift();
                stack.pop();
            }
        }
        //当前栈不含有出栈第一个,进行入栈
        else{
            console.log(stack,last,popV)
            //判断需要入栈几个
            let i = last.indexOf(popV[0]);
            for(let j = 0; j <= i; j++){
                stack.push(last[j])
            }
            if(last[i]!==popV[0]){
                console.log(stack,last,popV)
                console.log("f2")
                return false;
            }
            else{
                last = last.slice(i + 1);
                popV.shift();
                stack.pop();
            }
        }
    }
    return true
}

发表于 2021-08-10 21:40:48 回复(0)
Javascript
webchang头像 webchang
使用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)
JavaScript
别卷啦！头像 别卷啦！

设置辅助栈，压入元素，判断栈顶元素是否等于出栈第一个，相同则出栈，不同则继续入栈 

function IsPopOrder(pushV, popV)
{
    // write code here
    var tmp=[];
    for(var i=0,j=0;i<pushV.length;i++){
        tmp.push(pushV[i]);
        while(tmp.length&&tmp[tmp.length-1]==popV[j]){
            tmp.pop();
            j++;
        }
    }
    return tmp.length==0;
}

发表于 2021-07-04 21:43:27 回复(0)
JavaScript
牛客279835348号头像 牛客279835348号
// javascript版本
function IsPopOrder(pushV, popV) {
            // write code here
            let stack = [];
            let j = 0;
            for (let i = 0; i < pushV.length; i++) {
                if (pushV[i] == popV[j]) {
                    // 立即弹出
                    j++;
                    while (stack.length > 0 && stack[stack.length - 1] == popV[j]) {
                        stack.pop();
                        j++;
                    }
                }else {
                    stack.push(pushV[i]);
                }

                // stack.push(pushV[i]);
                // while (stack.length > 0 && stack[stack.length - 1] == popV[j]) {
                //     stack.pop();
                //     j++;
                // }

            }
            return stack.length == 0;
        }
发表于 2021-04-13 11:42:32 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function IsPopOrder(pushV, popV)
{
    // write code here
    var stack = [];
    var j = 0;
    for(var i = 0;i<pushV.length;i++){
        stack.push(pushV[i]);
        while(j < popV.length && (stack[stack.length-1] == popV[j])){
            stack.pop();
            j++;
        }
    }
    if(stack.length > 0){
        return false;
    }else{
        return true;
    }
}

发表于 2021-03-15 19:04:48 回复(0)
JavaScript
许愿各种offer头像 许愿各种offer 
function IsPopOrder(pushV, popV)
{
    const help = [];
    pushV.forEach(item => {
        help.push(item);
        while(help[help.length - 1] === popV[0] && help.length) {
            help.pop();
            popV.shift();
        }
    })
    return !help.length;
}

发表于 2020-11-29 14:14:46 回复(0)
JavaScript
牛客286450523号头像 牛客286450523号
function IsPopOrder(pushV, popV)
{
    // write code here
    if(pushV.length == 0 || popV.length == 0)
    return false;
    
    const stack=[];
    let index=0;
    for(let i=0;i<pushV.length;i++){
        stack.push(pushV[i]);
        while(stack.length&&stack[stack.length-1]===popV[index]){
            stack.pop();
            index++;
        }
    }
    return stack.length===0;
}
发表于 2020-07-21 14:37:24 回复(0)
JavaScript
阿斯弗123456aa头像 阿斯弗123456aa
function IsPopOrder(pushV, popV)
{
  for (var i = 0; i < pushV.length; i++) {
    if (pushV.indexOf(popV[i]) == -1)
      return false
  }
  if (pushV.length == 1)
  {
    return true;
  }
  else
  {
    var maxIndex = pushV.indexOf(popV[0]);
    for (var i = 1; i < popV.length-1; i++)
    {
      var before = pushV.indexOf(popV[i]);
      var next = pushV.indexOf(popV[i+1]);
      if ((next - before > 0) && (maxIndex - next > 0))
        return false;
      maxIndex = before;
    }
    return true;
  }
}
发表于 2020-07-02 09:45:11 回复(0)
JavaScript
奕※時＾毀￠头像 奕※時＾毀￠ 
function IsPopOrder(pushV, popV)
{
    var res=[];
    var item=popV.shift();//获取popV中第一个的值
    var i,temp;
    for(i=0;i<pushV.length;i++){
        temp=pushV[i];
        if(temp!=item){
            res.push(temp)
        }
        else{
            item=popV.shift();
        }
    }
    for(i=0;i<res.length;i++){
        temp=res[res.length-1-i];
        if(temp!=item)
            return false;
        item=popV.shift();
    }
    return true;
}


发表于 2020-04-29 12:57:31 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/**
 * 我的解题思路：
 * 1.借用一个辅助栈来实现，分析可知，popV的第一个元素为pushV第一个pop的元素
 * 2.遍历pushV，判断元素是否与popV第一个元素相同
 * 3.若相同，则执行popV.pop()，被移除的元素顺序一定正确
 * 4.若不同，则将元素加入辅助栈中
 * 5.遍历完成后，比较辅助栈和popV剩余元素是否互为出入栈规则
 * 注：由于步骤3中已将中途pop的元素移除，剩下的元素一定是按照全部push再全部pop的顺序执行
 *
 * @param {*} pushV 
 * @param {*} popV 
 */
function IsPopOrder(pushV, popV)
{
    // write code here
    const array = [];
    pushV.forEach(item => item === popV[popV.length - 1] ? popV.pop() : array.push(item));
    return array.reverse().join(',') === popV.join(',');
}


/**
 * 评论区TOP的解题思路：
 * 1.核心思路也是使用辅助栈来实现
 * 2.从0遍历pushV，将元素加入到辅助栈中
 * 3.从0遍历popV，判断popV中元素与辅助栈最后一个元素是否相同
 * 4.若相同，则移除辅助栈中最后一个元素，继续遍历popV，若不同，继续遍历pushV
 * 5.两层循环结束后，根据辅助栈是否为空来确定结果
 *
 * @param {*} pushV 
 * @param {*} popV 
 */
function topIsPopOrder(pushV, popV)
{
    // write code here
    const array = [];
    let j = 0;
    pushV.forEach(item => {
        array.push(item);
        while (j < popV.length && popV[j] === array[array.length - 1]) {
            array.pop();
            j++;
        }
    });
    return !array.length;
}

发表于 2020-03-07 14:45:14 回复(0)
JavaScript
火星人再也不用种土豆了头像 火星人再也不用种土豆了 
function IsPopOrder(pushV, popV)
{
    // write code here
    if(pushV.length === 0 || popV.length === 0) return false;//边界判断
    const s = [];//辅助栈

    for(var i=0;i<pushV.length;i++){//以入栈为长度
        s.push(pushV[i]);//将入栈一个一个读入辅助栈
        while( s.length && s[s.length-1] === popV[0]){//当辅助栈不为空且辅助栈顶===出栈栈顶
            s.pop();//将辅助顶弹出
            popV.shift();//弹出出栈栈顶 然后继续比较直到栈顶不相等或者辅助栈为空
        }
    }//遍历结束
    return s.length === 0;//辅助栈为空即为真

}
module.exports = {
    IsPopOrder : IsPopOrder
};

发表于 2019-12-09 14:42:45 回复(1)
提交观点

问题信息

栈
难度：
41条回答 173971浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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