首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列
  • 热度指数：770403 时间限制：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)
Python 3
zhanghualin头像 zhanghualin
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pushV int整型一维数组
# @param popV int整型一维数组
# @return bool布尔型
#
class Solution:
    def IsPopOrder(self, pushV: List[int], popV: List[int]) -> bool:
        # write code here
        pushV_seq = 0
        temp_list_left = []
        temp_list_right = pushV
        for i in range(0, len(popV)):
            try:
                if len(temp_list_right) != 0:
                    pushV_seq = temp_list_right.index(popV[i])
                    temp_list_left = temp_list_left + temp_list_right[:pushV_seq]
                    temp_list_right = temp_list_right[pushV_seq+1:]
                else:
                    if temp_list_left[len(temp_list_left) - 1] == popV[i]:
                        temp_list_left = temp_list_left[: len(temp_list_left) - 1]
                    else:
                        return False
            except:
                try:
                    if temp_list_left[len(temp_list_left) - 1] == popV[i]:
                        temp_list_left = temp_list_left[: len(temp_list_left) - 1]
                    else:
                        return False
                except:
                    return False
            print("第{0}次，左边：{1}，右边{2}".format(i, temp_list_left, temp_list_right))
        return True

发表于 2022-10-11 16:14:45 回复(0)
Python 3
牛客659597453号头像 牛客659597453号
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        self.pushV = pushV
        self.popV = popV
        self.help = []
        n = len(self.pushV)
        for i in self.pushV:
            if self.help == [] or self.help[-1] != self.popV[0] :
                    self.help.append(i)
            while n and self.help:
                if self.help[-1] == self.popV[0]:
                    self.help.pop()
                    self.popV.pop(0)
                    n -= 1
                else:
                    break

        if n ==0:
            return True
        else :
            return False
发表于 2022-09-07 16:39:49 回复(0)
Python 3
初心者托奇头像 初心者托奇
比楼上的python慢一些，index的原因 
stk = []
n = -10000
for i in popV:
    try:
        idx = pushV.index(i)
    except:
        return False
    if idx >= n:
        stk.extend(pushV[n:idx])
        n = idx + 1
    elif stk.pop() != i:
        return False
return True

发表于 2022-08-10 16:27:14 回复(0)
Python 3
学习37头像 学习37
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pushV int整型一维数组 
# @param popV int整型一维数组 
# @return bool布尔型
#
import re, json


class Solution:
    
    def __init__(self):
        self.stack = []
    
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        # 1
        if (len(pushV) == 0) or (len(pushV) != len(popV)):
                return False
        index = 0
        for ele in pushV:
            self.stack.append(ele)
            while len(self.stack) and self.stack[-1] == popV[index]:
                self.stack.pop()
                index += 1
                if index == len(popV):
                    return True
        return False

        #2
#         if (len(pushV) == 0) or (len(pushV) != len(popV)):
#             return False
#         j = 0
#         for i in range(len(pushV)):
#             self.stack.append(pushV[i])
#             i += 1
#             while j < len(popV) and self.stack and self.stack[-1] == popV[j]:
#                 self.stack.pop()
#                 j += 1
#         return False if (self.stack) else True 
    
# inStr = input()
# pList = re.split('(?<=\]),(?=\[)', inStr)
# pushV, popV = json.loads(pList[0]), json.loads(pList[1])
# so = Solution()
# so.IsPopOrder(pushV, popV)
# print(so.IsPopOrder(pushV, popV))
发表于 2022-07-29 16:38:11 回复(0)
Python 3
寒塘渡鹤影X头像 寒塘渡鹤影X 
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        stack = []
        for i in pushV:
            stack.append(i)
            while stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
        return not stack

发表于 2022-07-20 15:32:40 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        n = len(pushV)
        j = 0
        s = []
        for i in range(n):
            while j < n and (len(s) == 0 or s[-1] != popV[i]):
                s.append(pushV[j])
                j += 1
            if s[-1] == popV[i]:
                s.pop()
            else:
                return False
        return True
发表于 2022-05-06 17:35:16 回复(0)
Python 3
小小小小燃头像 小小小小燃 
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        self.data = []
        lens = len(pushV)
        for idx in range(lens):
                         
            # 压盏
            self.data.append(pushV[0])
            pushV.remove(pushV[0])
            
            # 如果 栈顶元素 和 popV 头元素一致则 pop 
            while  len(self.data) >= 1 and self.data[-1] == popV[0]  :
                self.data = self.data[:-1]
                popV = popV[1:]
        
        return len(self.data) == 0

发表于 2022-04-10 10:49:19 回复(0)
Python 3
牛客247371678号头像 牛客247371678号

非递归，双指针

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pushV int整型一维数组 
# @param popV int整型一维数组 
# @return bool布尔型
#
class Solution:


    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        if len(pushV) == 0 and len(popV) == 0:
            return True
        pr_push = 0
        pr_pop = 0
        stack_size = len(pushV)
        t = []
        while pr_push < stack_size and pr_pop < stack_size:
            size_t = len(t)
            if pushV[pr_push] == popV[pr_pop]:
                pr_push += 1
                pr_pop += 1
                continue
            if size_t > 0 and t[-1] == popV[pr_pop]:
#                 pr_push += 1
                pr_pop += 1
                t.pop()
                continue
            t.append(pushV[pr_push])
            pr_push += 1
        while t:
            n_pop = t.pop()
            if n_pop != popV[pr_pop]:
                return False
            pr_pop +=1 
        return True
发表于 2022-03-08 21:08:17 回复(0)
Python 3
菜鸡尼欧头像 菜鸡尼欧
模拟压入和弹出的过程, 看最后是否都能够弹出 

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pushV int整型一维数组 
# @param popV int整型一维数组 
# @return bool布尔型
#
class Solution:
    
    def __init__(self):
        self.stack = []
    
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        # 模拟压入和弹出的过程, 看最后是否都能够弹出
        if not pushV&nbs***bsp;not popV&nbs***bsp;len(pushV) != len(popV):
            return False
        for ele in pushV:
            self.stack.append(ele)
            while self.stack and self.stack[-1] == popV[0]:
                self.stack.pop(-1)
                popV.pop(0)
        if not popV:
            return True
        return False
                
            
            
            


发表于 2022-02-16 22:24:05 回复(0)
Python 3
牛客76750477号头像 牛客76750477号
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        TmpSet = pushV
        for n in popV:
            if n not in TmpSet:
                return False
            count = pushV.index(n)
            TmpSet = []
 
            if count == 0:
                TmpSet.extend(pushV[count+1:])
            else:
                TmpSet.extend(pushV[count-1:])
            del pushV[count]
        return True
发表于 2022-02-10 16:39:07 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def IsPopOrder(self , pushed: List[int], popped: List[int]) -> bool:
        # write code here
        stack1=[]
        j=0
        for i in pushed:
            stack1.append(i)
            while stack1 and stack1[-1]==popped[j]:
                stack1.pop()
                j+=1
        return len(stack1)==0

发表于 2022-01-27 08:54:47 回复(0)
Python 3
闲良头像 闲良
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        while len(popV)>1:
            p = popV[0]
            popV = popV[1:]
            idx = pushV.index(p)
            l = pushV[:idx]
            r = pushV[idx+1:]
            pushV = l + r
            if popV[0] in r:
                continue
            if popV[0] != l[-1]: 
                return False
        return popV==pushV
发表于 2022-01-07 21:30:08 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
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)
Python 3
明明铭头像 明明铭

Python 模拟弹栈

class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        i, j = 0, 0
        while(i < len(pushV)):
            stack.append(pushV[i])
            i += 1
            while(stack and stack[-1] == popV[j]):
                stack.pop()
                j += 1
        return i == j
发表于 2021-08-12 19:03:25 回复(0)
Python 3
tantantansq头像 tantantansq 
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        q=[]
        i,j=0,0
        while j<len(popV): 
            if len(q)==0&nbs***bsp;q[-1]!=popV[j]:   #只能压入
                if i==len(pushV):
                    return False 
                q.append(pushV[i])
                i+=1
            else:   #弹出
                q.pop()
                j+=1
        return True
                

发表于 2021-08-08 19:45:20 回复(0)
提交观点

问题信息

栈
难度：
16条回答 176061浏览

热门推荐

通过挑战的用户

查看代码

相关试题

栈的压入、弹出序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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