最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

Python题代码实现_栈的压入弹出序列

XAMPP案例 admin 33浏览 0评论

CA0074

【栈的压入弹出序列】

题目描述

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

思路

1. 引入辅助栈stack(旨在将其与指定弹出序列popV进行比较);

2. 遍历pushV的元素,并将其压入辅助栈stack;

3. 比较stack的末尾元素(即栈顶元素)与popV中首位元素是否相等,若相等则将两个元素都从栈中弹出,继续步骤2的遍历。

# -*- coding:utf-8 -*-class Solution:    def IsPopOrder(self, pushV, popV):        if len(pushV)!=len(popV):   #两栈长度不等不符合题目描述            return False        stack=[]    #引入辅助栈stack        for i in pushV:      #遍历pushV的元素            stack.append(i)    # 将元素追加到stack栈,i始终为栈顶元素/末尾元素            while len(stack)!=0 and stack[-1]==popV[0]:  #stack栈顶元素与popV中首位元素相等                stack.pop()   #stack栈顶元素弹出                popV.pop(0)   #popV首位元素弹出        if len(stack)!=0:     #此时辅助栈中还有元素,则说明popV中还有剩余元素,不可能是压栈序列的弹出序列            return False        return True

测试1:

s=Solution()pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(s.IsPopOrder(pushV,popV))# result:True

运行过程中辅助栈stack和popV的变化:

遍历开始stack:[1] popV:[4, 5, 3, 2, 1]stack:[1, 2] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3, 4] popV:[4, 5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[5, 3, 2, 1]stack:[1, 2, 3, 5] popV:[5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2] popV:[2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1] popV:[1]stack弹出末尾元素,popV弹出首位元素之后stack:[] popV:[]return True

测试2:

s=Solution()pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(s.IsPopOrder(pushV,popV))# result:False
【栈的压入弹出序列】

题目描述

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

思路

1. 引入辅助栈stack(旨在将其与指定弹出序列popV进行比较);

2. 遍历pushV的元素,并将其压入辅助栈stack;

3. 比较stack的末尾元素(即栈顶元素)与popV中首位元素是否相等,若相等则将两个元素都从栈中弹出,继续步骤2的遍历。

# -*- coding:utf-8 -*-class Solution:    def IsPopOrder(self, pushV, popV):        if len(pushV)!=len(popV):   #两栈长度不等不符合题目描述            return False        stack=[]    #引入辅助栈stack        for i in pushV:      #遍历pushV的元素            stack.append(i)    # 将元素追加到stack栈,i始终为栈顶元素/末尾元素            while len(stack)!=0 and stack[-1]==popV[0]:  #stack栈顶元素与popV中首位元素相等                stack.pop()   #stack栈顶元素弹出                popV.pop(0)   #popV首位元素弹出        if len(stack)!=0:     #此时辅助栈中还有元素,则说明popV中还有剩余元素,不可能是压栈序列的弹出序列            return False        return True

测试1:

s=Solution()pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(s.IsPopOrder(pushV,popV))# result:True

运行过程中辅助栈stack和popV的变化:

遍历开始stack:[1] popV:[4, 5, 3, 2, 1]stack:[1, 2] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3] popV:[4, 5, 3, 2, 1]stack:[1, 2, 3, 4] popV:[4, 5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[5, 3, 2, 1]stack:[1, 2, 3, 5] popV:[5, 3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2, 3] popV:[3, 2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1, 2] popV:[2, 1]stack弹出末尾元素,popV弹出首位元素之后stack:[1] popV:[1]stack弹出末尾元素,popV弹出首位元素之后stack:[] popV:[]return True

测试2:

s=Solution()pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(s.IsPopOrder(pushV,popV))# result:False

转载请注明:XAMPP中文组官网 » Python题代码实现_栈的压入弹出序列