剑指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）代码覆盖率
正文到此结束
