首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列
  • 热度指数：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)
Python
木有粗面201904101731812头像 木有粗面201904101731812
击败100%运行时间
class Solution:
    def IsPopOrder(self, pushV, popV):
        if len(pushV) == 0:
            return True
        if len(pushV) == 1:
            if pushV == popV:
                return True
            else:
                return False
        stack = []
        popindex = 0
        for i in range(0, len(pushV)):
            stack.append(pushV[i])
            while len(stack) > 0 and stack[-1] == popV[popindex]:
                popindex += 1
                stack.pop()
        return len(stack) == 0
发表于 2022-07-23 16:58:25 回复(0)
Python
wengJJ头像 wengJJ
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)
Python
奋斗的习习张头像 奋斗的习习张 
# -*- 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)
Python
牛客313692148号头像 牛客313692148号
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)
Python
吾三省啊头像 吾三省啊
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if len(pushV) != len(popV) or not pushV:
            return False
        res = []
        for i in range(len(pushV)):
            res.append(pushV[i])
            while res and res[-1] == popV[0] :
                res.pop(-1)
                popV.pop(0)
        return False if res else True
发表于 2021-04-27 12:53:36 回复(0)
Python
Quinn_5400头像 Quinn_5400
关键点:1.根据输入栈、输出栈模拟看是否能还原2.临时栈的可继续操作性判断
我的思路可能不是很优秀哈,凭感觉写的

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        tmpV = []
        while True:
            len1 = len(popV)
            if len(popV)==0:
                return True
            # 模拟tmpV的push操作
            while pushV:
                if pushV[0] <> popV[0]:
                    tmpV.append(pushV[0])
                    pushV.pop(0)
                else:
                    pushV.pop(0)
                    popV.pop(0)
                    break
            # 模拟tmpV的pop操作
            while tmpV:
                if popV[0]==tmpV[-1]:
                    popV.pop(0)
                    tmpV.pop()
                else:
                    break
            # popV无法继续弹出了
            len2 = len(popV)
            if len1 == len2:
                return False

发表于 2021-04-26 12:25:15 回复(0)
Python
牛客541273514号头像 牛客541273514号
用的笨方法 
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if pushV==None&nbs***bsp;popV==None:
            if pushV==None and popV==None:
                return True
            else:
                return False
        n,m=len(pushV),len(popV)
        if n != m:
            return False
        else:
            if set(pushV) != set(popV):
                return False
            first_push=pushV.index(popV[0])
            tmp=pushV[:first_push]
            pushV=pushV[first_push+1:]
            for i in range(1,n):
                if tmp:
                    if popV[i]==tmp[-1]:
                        tmp.pop()
                    elif popV[i] in pushV:
                        tmp+=pushV[:pushV.index(popV[i])]
                        pushV=pushV[pushV.index(popV[i])+1:]
                    else: return False
                elif popV[i] in pushV:
                    tmp+=pushV[:pushV.index(popV[i])]
                    pushV=pushV[pushV.index(popV[i])+1:]
                else: return False
            return True

发表于 2021-04-18 15:35:36 回复(0)
Python
O_胡萝卜_O头像 O_胡萝卜_O
献丑，请多指教，
建立空栈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)
Python
什么题目都蒙对头像 什么题目都蒙对
栈的压入顺序是指12345是依次push到栈的，但并不是说只有push的过程，也有可能是pop的操作，比如push1234后，把4pop出去，再push5，再pop5，再依次pop321，弹出序列是指每次pop出去的元素都当时栈顶的元素。
那么就可以构建一个辅助栈来判断弹出序列是不是和压栈序列对应。首先遍历压栈序列的元素push到辅助栈，判断是不是弹出序列的首元素。如果是，则弹出序列pop首元素，如果不是则继续push，再继续判断。如果辅助栈或者弹出栈为空，则返回true，否则false
发表于 2021-04-08 10:50:10 回复(0)
Python
在下小6头像 在下小6

python解法：
解法1:新建一个栈，将数组A压入栈s中，当栈顶元素等于数组B元素时且栈s不为空时，将s出栈。
循环结束时，判断栈s是否为空，若为空则返回true；

class Solution:
    def IsPopOrder(self, pushV, popV):
        s = []
        i,j = 0,0
        for i in pushV:
            s.append(i)
            # 当栈顶元素等于数组B元素时且栈s不为空时，将s出栈
            while s and s[-1] == popV[j]:
                s.pop()
                j += 1
        return len(s) == 0
发表于 2021-02-23 18:27:34 回复(0)
Python
保洁大哥头像 保洁大哥
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.Stack = []
        
    def push(self,node):
        self.Stack.insert(0,node)
    def pop(self):
        self.Stack.pop(0)
        
    def top(self):
        return self.Stack[0]
    def IsPopOrder(self, pushV, popV):
        j = 0
        for i in range(len(pushV)):
            if pushV[i] != popV[j]:
                self.push(pushV[i])
            else:
                j +=1
                while len(self.Stack):
                    if self.top()!=popV[j]:
                        break
                    else:
                        self.pop()
                        j +=1
        if len(self.Stack):
            return False
        else:
            return True
        # write code here
发表于 2021-02-03 12:15:19 回复(0)
Python
张浩头像 张浩 
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack=[]
        i,j=0,0
        while i<len(pushV):
            if pushV[i]!=popV[j]:
                stack.append(pushV[i])
                i+=1
            elif pushV[i]==popV[j]:
                i+=1
                j+=1
                while stack and (popV[j]==stack[-1]):
                    stack.pop()
                    j+=1
        if not stack:
            return True
        else:
            return False

发表于 2020-11-29 18:24:06 回复(0)
Python
zhd要到160斤头像 zhd要到160斤 
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        return pushV[0] == popV[::-1][0]
这难道不也是利用了栈的性质吗... 如果是他的出栈 那么他倒过来的第一个肯定是要一样的啊。。。
发表于 2020-11-27 12:23:34 回复(0)
Python
straightup头像 straightup
我的思路是先构建一个辅助栈, 循环pushV的元素, 按照pushV的顺序将其压入辅助栈, 每次压入都根据popV的弹出顺序判断是否需要弹出, 并用index来记录popV弹出元素的下标. 当pushV循环结束, 如果经过压入和弹出操作的辅助栈的翻转和popV index往后的剩余序列相同, 则True(因为前面的元素已经落好位了, 只能按一个顺序逐个弹出), 反之则False. 
class Solution:
    def IsPopOrder(self, pushV, popV):
        stack = []
        index = 0
        for item in pushV:
            stack.append(item)
            if item == popV[index]:
                stack.pop()
                index += 1
        if stack[::-1] == popV[index:]:
            return True
        return False


发表于 2020-10-01 22:45:48 回复(0)
Python
君子不自弃医者不自医头像 君子不自弃医者不自医
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        for i in range(len(pushV)):
            if pushV[i]!=popV[len(pushV)-i-1]:
                return False
            break
            
        return True
发表于 2020-09-15 16:58:13 回复(0)
Python
www_helloworld_cn头像 www_helloworld_cn

逐个匹配出栈字符串的字符：
如果当前栈顶是这个字符，则弹出，匹配下一个出栈字符；
如果当前栈顶不是这个字符，则说明需要继续压栈直到栈顶是这个字符；
如果压栈字符串所有字符压入都没有栈顶是这个字符的情况，说明该出栈序列不正确。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        s = []
        i_push = 0
        i_pop = 0
        while i_push < len(pushV) or i_pop < len(popV):
            while len(s)==0 or s[-1]!=popV[i_pop]:
                if i_push == len(pushV):
                    return False
                s.append(pushV[i_push])
                i_push+=1
            else:
                s.pop()
                i_pop += 1
        if i_pop == len(popV):
            return True
        return False
发表于 2020-08-04 07:39:27 回复(0)
Python
CrucioLzy头像 CrucioLzy 
        # 核心思路： 对于pop出来的每一个数，在他之后出栈的那些元素，如果入栈比他早，那么这些元素
        # 的出栈顺序一定是按其入栈顺序的倒序 出栈的
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if sorted(pushV) != sorted(popV):
            return False
        cur = 0
        for i in range(len(popV)):
            if i <= cur:continue # 判断过的不用再判断了
            order_list = []
            i_in = pushV.index(popV[i])
            for j in range(i,len(popV)):# 遍历它之后的元素
                if pushV.index(popV[j]) < i_in: # 如果入栈顺序比它早
                    order_list.append(pushV.index(popV[j])) # 加入考察的范围
            if order_list == sorted(order_list,reverse=True): # 这些入栈更早的元素 必须严格遵循先入后出
                cur = i
            else:
                return False
        return True

没有高赞答案那么牛逼🤣
发表于 2020-08-03 22:45:45 回复(0)
Python
牛客1349号头像 牛客1349号
python 实现 
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV&nbs***bsp;not popV:
            return
        if len(pushV) != len(popV):
            return
        while pushV:
            if pushV.pop() == popV.pop(0):
                res = True
            else:
                res = False
        return res
    
发表于 2020-07-27 01:41:28 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if pushV == []&nbs***bsp;len(pushV) != len(popV):
            return None
        stack = []
        index = 0
        for i in pushV:
            stack.append(i)
            while stack and stack[-1] == popV[index]:
                stack.pop()
                index += 1
        return True if stack == [] else False
    
              
注意：stack[-1]为什么换成stack[0]不行呢？因为当对于stack不断append时，此时stack由于不等于popV[index]所以不会立刻弹出，也就是说stack此时不止存放一个数。然后我们比的是stack最后的一个数，所以用的是stack[-1]。
发表于 2020-07-24 17:45:20 回复(0)
提交观点

问题信息

栈
难度：
123条回答 173973浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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