题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
解题思路：
（1）主要依靠辅助栈stack，将入栈pushA数据遍历添加到辅助栈stack中，定义入栈标识位index；若辅助栈非stack空且栈顶元素与出栈popA数据的index标识位相同，则辅助栈栈顶元素弹出，且index标识为 +1，若不相同，则继续将入栈pushA数据压入辅助栈，当遍历完入栈pushA数据后，判断辅助栈是否为空，若不为空则说明出栈popA数据不是该栈的弹出序列，反之是该栈的弹出序列
（2）采用双指针i, j和栈 stack来实现，逐个将 pushV 数组的元素入栈，每入栈一个元素，i++；循环判断栈顶元素是否为popped[j]，如果是 j++，stack出栈，继续判断；最后只需判断 指针j 是否等于 数组长度 n来判断popV是否是该栈的弹出序列
举例说明：
以第一种解题思路介绍：
入栈：【1， 2， 3】
出栈：【3， 1， 2】
首先1进入辅助栈，此时index = 0, 栈顶1≠3，继续入栈2，辅助栈：【1， 2】
此时index = 0, 栈顶2≠3，继续入栈3，辅助栈【1， 2， 3】
此时index = 0,栈顶3==3，则3出栈，index = 1, 辅助栈为【1， 2】
此时index = 1, 栈顶2≠1，入栈序列遍历结束，辅助栈为【1， 2】
结果显示出栈序列不是该栈的弹出序列；
图解：
| 步骤 | 操作 | 辅助栈stack | 弹出元素 |
| 1 | 1入栈 | 1 | |
| 2 | 2入栈 | 1，2 | |
| 3 | 3入栈 | 1，2，3 | |
| 4 | 弹出3 | 1，2 | 3 |
| 5 | 下一个弹出的元素应该为1，但是该元素并不在栈顶 且入栈序列已遍历结束，则无法继续即为 | ||
若 出栈：【3， 2， 1】
当3出栈后，index = 1，辅助栈为【1， 2】
此时栈顶2 == 2，则2出栈，index = 2， 辅助栈为【1】
此时栈顶1 == 1，则1出栈 ，入栈序列遍历结束辅助栈为【】
结果显示出栈序列是该栈的弹出序列；
| 步骤 | 操作 | 辅助栈stack | 弹出元素 |
| 1 | 1入栈 | 1 | |
| 2 | 2入栈 | 1，2 | |
| 3 | 3入栈 | 1，2，3 | |
| 4 | 弹出3 | 1，2 | 3 |
| 5 | 弹出2 | 1 | 2 |
| 6 | 弹出1 | | 1 |
代码：
Python3版本：
# -*- coding:utf-8 -*- class Solution: def IsPopOrder(self, pushV, popV): # write code here # 定义辅助栈 stack = [] # 用于标识弹出序列的位置 tmp = 0 for i in range(len(pushV)): stack.append(pushV[i]) # while 条件，判断辅助栈stack的栈顶元素是否等于popV[tmp] while stack and stack[-1] == popV[tmp]: # 符合条件则辅助栈stack弹出栈顶元素 stack.pop() # 标识位 +1 tmp += 1 # 根据stack是否是空栈判断输出结果 return stack == []JAVA版本：
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
// 定义默认返回值
boolean res = false;
// 定义一个辅助栈
Stackstack = new Stack();
// 用于标识弹出序列的位置
int index = 0;
for (int i = 0; i < pushA.length; i++) { stack.push((pushA[i])); while (!stack.isEmpty() && stack.peek() == popA[index]){ // 辅助栈出栈 stack.pop(); index++; } } // 如果辅助栈为空则说明弹出序列正确,若辅助栈不为空则说明弹出序列错误 return stack.isEmpty(); } } 复杂度分析：
时间复杂度O(N)：其中N标识pushV的长度；每个元素最多入栈与出栈各一次
空间复杂度O(N)：辅助栈stack最多同时存储N个元素
