剑指Offer面试题:20.栈的压入、弹出序列

一、题目:栈的压入、弹出序列

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

二、解题思路

2.1 核心步骤

正确的弹出序列

不正确的弹出序列

  通过分析以上序列,可以得出:

  • 如果下一个弹出的数字刚好是栈顶数字,那么直接弹出
  • 如果下一个弹出的数字不在栈顶,我们把压栈序列中还没有入栈的数字压入辅助栈,直到把下一个需要弹出的数字压入栈顶为止。
  • 如果所有的数字都压入栈了仍然没有找到下一个弹出的数字,那么该序列不可能是一个弹出序列。

2.2 代码实现

    public static bool IsPopOrder(int[] pushOrder, int[] popOrder, int length)
    {
        bool possible = false;

        if (pushOrder != null && popOrder != null && length > 0)
        {
            int nextPush = 0; // 指向下一个要push的元素的index
            int nextPop = 0;  // 指向下一个要pop的元素的index
            int pop = 0;      // 指向popOrder的首个元素的index
            int push = 0;     // 指向pushOrder的首个元素的index

            Stack<int> stackData = new Stack<int>();
            while (nextPop - pop < length)
            {
                // 当辅助栈的栈顶元素不是要弹出的元素
                // 先压入一些数字入栈
                while (stackData.Count == 0 || stackData.Peek() != popOrder[nextPop])
                {
                    // 如果所有数字都压入辅助栈了,退出循环
                    if (nextPush - push == length)
                    {
                        break;
                    }

                    stackData.Push(pushOrder[nextPush]);
                    nextPush++;
                }

                // 说明没有匹配成功
                if (stackData.Peek() != popOrder[nextPop])
                {
                    break;
                }

                stackData.Pop();
                nextPop++;
            }

            if (stackData.Count == 0 && nextPop - pop == length)
            {
                possible = true;
            }
        }

        return possible;
    }

三、单元测试

3.1 功能测试

    [TestMethod]
    public void OrderTest1()
    {
        int length = 5;
        int[] push = { 1, 2, 3, 4, 5 };
        int[] pop = { 4, 5, 3, 2, 1 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), true);
    }

    [TestMethod]
    public void OrderTest2()
    {
        int length = 5;
        int[] push = { 1, 2, 3, 4, 5 };
        int[] pop = { 3, 5, 4, 2, 1 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), true);
    }

    [TestMethod]
    public void OrderTest3()
    {
        int length = 5;
        int[] push = { 1, 2, 3, 4, 5 };
        int[] pop = { 4, 3, 5, 1, 2 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), false);
    }

    [TestMethod]
    public void OrderTest4()
    {
        int length = 5;
        int[] push = { 1, 2, 3, 4, 5 };
        int[] pop = { 3, 5, 4, 1, 2 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), false);
    }

3.2 特殊输入测试

    // push和pop序列只有一个数字且不同
    [TestMethod]
    public void OrderTest5()
    {
        int length = 1;
        int[] push = { 1 };
        int[] pop = { 2 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), false);
    }

    // push和pop序列只有一个数字且相同
    [TestMethod]
    public void OrderTest6()
    {
        int length = 1;
        int[] push = { 1 };
        int[] pop = { 1 };

        Assert.AreEqual(StackHelper.IsPopOrder(push, pop, length), true);
    }

    // NULL指针
    [TestMethod]
    public void OrderTest7()
    {
        Assert.AreEqual(StackHelper.IsPopOrder(null, null, 0), false);
    }

3.3 测试结果

  (1)测试通过情况

  (2)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-12(02)总结Scanner,String

(6)字符串的案例 A:模拟用户登录 B:字符串遍历 C:统计字符串中大写,小写及数字字符的个数 D:把字符串的首字母转成大写,其他小写 E:把int...

424100
来自专栏微信公众号:Java团长

Java动态代理机制详解

在学习Spring的时候,我们知道Spring主要有两大思想,一个是IoC,另一个就是AOP,对于IoC,依赖注入就不用多说了,而对于Spring的核心AOP来...

14610
来自专栏柠檬先生

zepto 基础知识(1)

1.$() 的用法。   获取元素     $('div') //获取所有页面中的div元素     $('#foo') // 获取ID ...

21580
来自专栏小小挖掘机

举一反三-Pandas实现Hive中的窗口函数

1、Hive窗口函数 我们先来介绍一下Hive中几个常见的窗口函数,row_number(),lag()和lead()。 row_number() 该函数的格式...

42560
来自专栏前端儿

JS实现简易的计算器

自认脑袋不够大,就实现一个普通版本的吧(支持正负数加减乘除等基本连续的运算,未提供括号功能)

1.1K10
来自专栏Android干货

源码浅谈(二):java中的 Integer.parseInt(String str)方法

一、parseInt方法 ,可以看到默认又调用了parseInt(s,10) ,  第二个参数为基数,默认10 ,当然也可以自己设置 

31510
来自专栏快乐八哥

JavaScript中匿名函数的困惑

函数字面量(function literal):处理事件的无名函数(nameless function)。函数字面量有时也称为匿名函数(anonymous fu...

19270
来自专栏Java编程

Java动态代理机制详解

在学习Spring的时候,我们知道Spring主要有两大思想,一个是IoC,另一个就是AOP,对于IoC,依赖注入就不用多说了,而对于Spring的核心AOP来...

48510
来自专栏lgp20151222

排序算法对比,步骤,改进,java代码实现

发现是时候总结一番算法,基本类型的增删改查的性能对比,集合的串并性能的特性,死记太傻了,所以还是写在代码里,NO BB,SHOW ME THE CODE!

10320
来自专栏猿人谷

不用加减乘除做加法

题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、×、÷四则运算符号。 分析: 第一步:不考虑进位对每一位相加。0加0、1加1的结果都是0,0加1...

22970

扫码关注云+社区

领取腾讯云代金券