page contents
首页 问答
正文

如何根据入栈序列判断可能的出栈序列？

轩辕小不懂 发布于 2022-03-24 16:31
阅读 422
收藏 0
答案 1
分类：人工智能
  • 人工智能
  • python
  • 编程论坛

    • 输入两个整数序列，其中一个序列表示栈的push（入）顺序，判断另一个序列有没有可能是对应的pop（出）顺序。

    默认排序 时间排序
    3362
    Nen
    Nen
    - 程序员

    分析与解答：假如输入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一个pop序列，但5、3、4、1、2就不可能是它的一个pop序列。主要思路是使用一个栈来模拟入栈顺序，具体步骤如下。

    1）把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动到第二个元素。

    2）如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。

    3）如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop序列。图9-9给出一个合理的pop序列的判断过程。

    请先 登录 后评论
    轩辕小不懂
    1 关注
     
    轩辕小不懂
    提出于 2022-03-24 16:31
    全部

    轩辕小不懂 的其他提问

    类似问题

    运行时异常与一般异常有何异同？
    1 回答
    422 阅读
    String 和StringBuffer的区别？
    2 回答
    422 阅读
    怎样将字符串中第一个字母大写？
    3 回答
    422 阅读
    在Python中如何生成一个随机数？
    1 回答
    422 阅读
    Python中的不可变集合（frozenset）是什么？
    1 回答
    422 阅读
    在Python中怎样获取输入？
    1 回答
    422 阅读