面试 16：栈的压入压出队列
我们今天继续来看看周五留下的习题：
面试题：输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如：压入序列为{1，2，3，4，5}，那{4，5，3，2，1} 就是该栈的弹出顺序，而{4，3，5，1，2} 明显就不符合要求；
这道题还是比较容易想到思路，很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。
提前想好测试用例
一样是老方法，我们先准备测试用例：
传入两个 null，或者 1 个 null，或者空数组，此时应该不符合要求；
传入两个不相等的数组，应该直接不符合要求；
分别传入题干的示意值，他们应该分别满足和不满足要求；
传入单个数字，选择一组满足要求的和一组不满足要求的；
思考程序逻辑
判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
然而有的小伙伴还是容易被绕晕，这时候不妨我们可以直接作一个表格来模拟他们的压栈出栈过程，数据就采用我们题设中的数据吧~
用作图和模拟数据更容易给面试官一个你是个喜欢思考的好同事哟~
首先看看我们正确的数据。
| 判断操作 | 操作 | 栈 | 弹出数字 |
|---|---|---|---|
| 栈没数据，push 数组还有数据、压入 | 压入 | 1 | |
| 栈顶是 1，不等于pop[0]，push 数组还有数据、压入 | 压入 | 1、2 | |
| 栈顶是 2，不等于pop[0]，push 数组还有数据、压入 | 压入 | 1、2、3 | |
| 栈顶是 3，不等于pop[0]，push 数组还有数据、压入 | 压入 | 1、2、3、4 | |
| 栈顶是 4，等于pop[0]，弹出数字 4 | 弹出 | 1、2、3 | 4 |
| 栈顶是 3，不等于pop[1]，push 数组还有数据、压入 | 压入 | 1、2、3、5 | |
| 栈顶是 5，等于pop[1]，弹出数字 5 | 弹出 | 1、2、3 | 5 |
| 栈顶是 3，等于pop[2]，弹出数字 3 | 弹出 | 1、2 | 3 |
| 栈顶是 2，等于pop[3]，弹出数字 2 | 弹出 | 1 | 2 |
| 栈顶是 1，等于pop[4]，弹出数字 1 | 弹出 | 1 |
实际上我们在草稿纸上并不需要做这么标准的表格，只要能表现意思即可。
我们仔细观察可以得知，我们判断压入还是弹出甚至是得出确定结论的标准是，先看当前栈顶元素和弹出的数字是否相等，如果相等则直接弹出；如果不相等则直接看看压入数组中还有没有元素，如果有则直接压入到辅助栈；如果已经没有数据则代表第二个序列不是第一个序列的弹出栈。
编写程序代码
实际上我们心中已经大概知道怎么写了。
private static boolean isPushStack(int[] push, int[] pop) {
if (push == null || pop == null || pop.length != push.length)
return false;
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pop.length; i++) {
// 第一步判断栈顶元素是否和 pop[i] 相等
if (!stack.isEmpty() && pop[i] == stack.peek()) {
// 如果相等则直接 pop()
stack.pop();
} else {
// 栈顶和 pop[i] 不相等，则判断 push 数组还有没有数据
// 如果 push 数组没数据了，栈顶元素又不等于 pop[i]，则说明不符合要求
if (j == push.length)
return false;
while (j < push.length) {
// 如果还有数据，则直接 push
stack.push(push[j]);
++j;
// push 后继续判断栈顶元素是否和 pop[i] 相等；
if (pop[i] == stack.peek()) {
// 如果相等则弹出栈，并且推出内层循环
stack.pop();
break;
}
}
}
}
return true;
}
验证测试用例
写毕代码后，我们得用自己事先准备的测试用例测试一下。
测试 1 和测试 2 我们已经考虑到了，这样的情况直接在功能之前就判断，不符合条件的直接返回 false，测试通过。
传入{1，2，3，4，5} 和 {4，5，3，2，1}：
进入循环，i = 0，pop[i] = 4，直接进入 else 语句，开始 push 数据，一直 push 到 j = 3。
此时栈内元素为 {1，2，3，4}，push 里面还剩下 {5}。因为 pop[0] 等于栈顶，所以进入 if 语句，弹出 4，退出 while 循环；
i = 1，栈内元素为{1，2，3}，栈顶元素不等于 pop[1] = 5，进入 else 语句。push 数组还有数据，直接 push，结束后 j = 5，栈内元素为 {1，2，3，5}，栈顶刚好等于 pop[1]，故弹出数字 5，退出 while 循环；
i = 2，栈内元素为{1，2，3}，栈顶元素刚刚等于 pop[2] ，弹出数字 3；
i = 3，栈内元素为 {1，2}，栈顶元素刚等于 pop[3]，弹出数字 2；
i = 4，栈内元素为 {1}，栈顶元素刚刚等于 pop[4]，弹出数字 1；
for 循环能直接执行结束，返回 ture，测试通过。
传入 {1，2，3，4，5} 和 {4，3，5，1，2}：
进入循环，i = 0，pop[i] = 4，由于同上，所以直接进入到上面的步骤 3；
此时 i = 1，栈内元素为 {1，2，3}，因为栈顶元素等于 pop[1]，弹出数字 3；
i = 2，栈内元素为 {1，2}，栈顶元素不等于 pop[2]，进入 else 语句，此时 push 数组还有元素 {5}，所以进入 while 循环。push 后栈内元素为 {1，2，5}，栈顶元素等于 pop[2]，所以弹出数字 5，退出 while 循环；
i = 3，栈内元素为{1，2}，pop[3] = 1，和栈顶元素不相等，所以进入 else 语句，由于 push 里面已经没有了元素，所以直接返回 false，测试通过。
传入 {1} 和 {2}：
进入循环，i = 0，pop[i] = 2，进入 else 语句，不相等，直接进入 while 循环，push 后栈内元素为 {1}，栈顶元素和 pop[i] 不相等，此时 j = 1，不符合 while 循环条件。循环结束，外循环也结束，返回 true。测试不通过。
修复程序逻辑
所以我们现在应该着重处理一下单个数字的情况，分析后明显可以得到，我们要判断这种情况只需要再判断结束 for 循环后栈内是否还有元素和 push 里面还是否有元素即可。
所以在最后增加一个条件判断即可。
public class Test16 {
private static boolean isPushStack(int[] push, int[] pop) {
if (push == null || pop == null || pop.length != push.length)
return false;
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pop.length; i++) {
// 第一步判断栈顶元素是否和 pop[i] 相等
if (!stack.isEmpty() && pop[i] == stack.peek()) {
// 如果相等则直接 pop()
stack.pop();
} else {
// 栈顶和 pop[i] 不相等，则判断 push 数组还有没有数据
// 如果 push 数组没数据了，栈顶元素又不等于 pop[i]，则说明不符合要求
if (j == push.length)
return false;
while (j < push.length) {
// 如果还有数据，则直接 push
stack.push(push[j]);
++j;
// push 后继续判断栈顶元素是否和 pop[i] 相等；
if (pop[i] == stack.peek()) {
// 如果相等则弹出栈，并且推出内层循环
stack.pop();
break;
}
}
}
}
// 增加判断
if (!stack.isEmpty() && j == push.length)
return false;
return true;
}
public static void main(String[] args) {
int[] push = {1, 2, 3, 4, 5};
int[] pop1 = {4, 5, 3, 2, 1};
int[] pop2 = {3, 5, 4, 2, 1};
int[] pop3 = {4, 3, 5, 1, 2};
int[] pop4 = {3, 5, 4, 1, 2};
System.out.println(isPushStack(push, pop1));
System.out.println(isPushStack(push, pop2));
System.out.println(isPushStack(push, pop3));
System.out.println(isPushStack(push, pop4));
int[] push1 = {1};
int[] pop5 = {2};
System.out.println(isPushStack(push1, pop5));
int[] push2 = {1};
int[] pop6 = {1};
System.out.println(isPushStack(push2, pop6));
}
}
上面在代码逻辑上并没有做多少操作，所以我们只需要再传入 {1} 和 {1} 测试就可以了。
直接进入到 while 循环，push 后栈内元素为 {1}，因为栈顶元素刚刚等于 pop[0]，所以推出数字 1。此后栈内无元素，所以直接返回 true。
总结
我亲爱的小伙伴想必也一定在上面的分析中收获到东西了吧，这也是南尘给大家的箴言。
在思路不是很清晰的时候画表或者画图来处理；
在验证测试用例的时候，一定从简单的开始，比如上面，我们其实更加建议先验证单个数字的情况。
拓展延伸
本次学习的方法将非常有效，不信大家可以试试下明天的拓展题。
面试题：从上到下打印二叉树的每个结点，同一层按照从左到右的顺序打印。例如数的结构如下：
1
2 3
4 5 6 7则依次打印 1、2、3、4、5、6、7
—————END—————
我是南尘，只做比心的公众号，欢迎关注我。
推荐阅读：
欢迎关注南尘的公众号：nanchen
做不完的开源，写不完的矫情，只做比心的公众号，如果你喜欢，你可以选择分享给大家。如果你有好的文章，欢迎投稿，让我们一起来分享。