判断入栈顺序和出栈顺序是否合理 python实现

朴灿烈づ我的快乐病毒、 2022-05-14 07:37 227阅读 0赞

# 前言 #

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

# 解题思路 #

1.我们申请一个的新的列表stack，依次将入栈序列中的值加入  
2.每次加入stack,我们需要将stack的顶部的数和出栈序列中起始index的数做对比，如果相等，我们将stack中的顶部弹出，并且出栈序列的index依次后移，重复这样的操作，直到值不相等或者出栈序列已经空了为止  
3.最后，我们检验stack中是否为空，如果为空，则入栈和出栈序列是合理的，否则不是合理的

# python code #

#coding:utf-8
    #!/bin/python
    
    import sys
    
    def is_pop_order(pushV, popV):
        if len(pushV) == 0:
            return False
        stack = []
        j = 0
        for i in range(len(pushV)):
            stack.append(pushV[i])
            while j < len(popV) and stack[-1] == popV[j]:
                stack.pop()
                j += 1
        if len(stack) == 0:
            return True
        else:
            return False
    
    
    def main():
        p_push = sys.stdin.readline().strip()
        p_stack = sys.stdin.readline().strip()
        print(is_pop_order(p_push, p_stack))
    
    
    if __name__ == '__main__':
        main()

## test ##

12345
    45321
    
    True

发表评论取消回复

表情：

评论列表（有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-出栈顺序是否正确

1. 判断出栈顺序是否正确给出元素进栈顺序，判断出栈序列是否合法。例如： * 入栈 1,2,3,4,5 * 出栈 4,5,3,2,1 可判断其出栈...

末蓝、/ 2024年04月18日 07:50/ 0 赞/ 66 阅读

相关栈压入和弹出顺序

题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序

柔情只为你懂/ 2024年02月18日 22:20/ 0 赞/ 58 阅读

相关利用Python实现顺序栈

1 问题在常用的数据结构中，有一批结构被称为容器——栈与队列。那该怎么利用Python学习栈这种结构的特性并用Python实现其相关操作呢？ 2 方法栈相对于是一个容

以你之姓@/ 2024年02月17日 10:35/ 0 赞/ 48 阅读

相关判断入栈顺序和出栈顺序是否匹配的问题

class Solution2: def IsPopOrder(self, pushV, popV): stack = []

Love The Way You Lie/ 2022年12月31日 01:22/ 0 赞/ 167 阅读

相关关于顺序栈的退栈和入栈操作

代码 Void main() \{ Stack S;Char x,y; InitStack(S); x='c';y='k'; push(S,x);push(S,

Dear 丶/ 2022年09月14日 11:19/ 0 赞/ 174 阅读

相关判断元素出栈、入栈顺序的合法性

元素出栈、入栈顺序的合法性。如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1），则合法。入栈的序列（1,2,3,4,5），出栈序列为（4,5,2,3,1

ゝ一纸荒年。/ 2022年06月12日 11:39/ 0 赞/ 245 阅读

相关 N个数依次入栈,出栈顺序有多少种

1.基于栈的问题分析我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出： f(1) = 1 //即 1 f(2) = 2//即 12、2

雨点打透心脏的1/2处/ 2022年06月10日 08:41/ 0 赞/ 163 阅读

相关顺序栈的压栈和出栈

include<iostream> using namespace std; const int StackSize=10;

港控/mmm°/ 2022年06月07日 10:50/ 0 赞/ 219 阅读

相关判断入栈顺序和出栈顺序是否合理 python实现

前言输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序

朴灿烈づ我的快乐病毒、/ 2022年05月14日 07:37/ 0 赞/ 228 阅读

相关出栈顺序

之前参加过华北计算机研究所和优酷土豆的笔试，都考到出栈顺序，之前数据结构学的不到位，遇到这类题时，还着实把我愣了一会，现在总结下，省得以后再遇到这类问题，也希望能给遇到同样问题

电玩女神/ 2022年02月01日 01:55/ 0 赞/ 285 阅读