栈的压入、弹出序列

未匹配的标注

题目描述

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

分析

  1. 借用一个辅助的栈,遍历压栈序列。
  2. 辅助栈先放入压栈序列的第一个,在判断是否和出栈序列的第一个值相等。
  3. 如果相等,则辅助栈弹出,然后压栈序列向后移动一位。然后继续比较辅助栈栈顶是否和出栈序列当前元素相等。
  4. 如果不相等,在继续将压栈序列压入辅助栈。
  5. 最后判断辅助栈是否为空,即全部弹出。是的话,说明出栈序列是弹出序列。

代码

<?php
namespace app\index\controller;

class Test 
{
    public function test()
    {
        $pushArr = [1, 2, 3, 4, 5];      // 入栈序列
        $popArr  = [4, 5, 3, 2, 1];      // 出栈序列
        $length  = count($pushArr);      // 入栈的长度
        $j       = 0;                    // 出栈序列的下标
        $stack   = new \SplStack();      // 辅助栈

        // 循环入栈序列
        for ($i = 0; $i < $length; $i++) {
            $stack->push($pushArr[$i]);   // 先根据入栈序列压入辅助栈

            // 出栈序列长度等于入栈序列长度 && 辅助栈栈顶等于出栈序列当前元素
            while ($j < $length && $stack->top() == $popArr[$j]) {
                $stack->pop();  // 弹出辅助栈栈顶
                $j++;           // 出栈序列指向下一个
            }
       }
        // 如果辅助栈清空,说明 popArr 是弹出序列
        if ($stack->isEmpty()) echo true;
        echo false;
    }
}

笔记

SplStack 类:通过使用一个双向链表来提供栈的主要功能。

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~