首页 > 试题广场 >

栈的压入、弹出序列

[编程题]栈的压入、弹出序列

热度指数：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

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)

Python 3

GuoGuoCaptital

关键：先一个一个加入栈中。每次加入一个后，只要栈顶等于popV值，意味着要stack 要pop掉

发表于 2025-05-09 22:50:59 回复(0)

Python 3

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号

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @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

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

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号

非递归，双指针

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @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号

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

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

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

# -*- 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)

提交观点

问题信息

栈

难度：

17条回答 4179收藏 183737浏览

通过挑战的用户

查看代码

想笑

2023-03-11 00:50:32
王安迅

2023-03-10 20:38:13
牛客51281...

2023-03-07 14:56:03
牛客12405...

2023-03-07 11:04:02
胖布布

2023-03-04 15:16:26

栈的压入、弹出序列

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题