document.write('假如输入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一个pop序列，但5、3、4、1、2
就不可能是它的一个pop序列。
主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：
(1)把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动
到第二个元素；
(2)如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。
(3)如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这
个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop
序列。下图给出一个合理的pop序列的判断过程。
在上图中，(1)～(3)三步，由于栈顶元素不等于pop序列第一个元素3，因此，1，2，3依次入栈，当3入
栈后，栈顶元素等于pop序列的第一个元素3，因此，第(4)步执行3出栈，接下来指向第二个pop序列2，且
栈顶元素等于pop序列的当前元素，因此，第(5)步执行2出栈；接着由于栈顶元素4不等于当前pop序列5，
因此，接下来(6)和(7)两步分别执行4和5入栈；接着由于栈顶元素5等于pop序列的当前值，因此，第(8)步
执行5出栈，接下来(9)和(10)两步栈项元素都等于当前pop序列的元素，因此，都执行出栈操作。最后由于
栈为空，同时pop序列都完成了遍历，因此，{3，2，5，4，1}是一个合理的出栈序列。
实现代码如下：
class Stack:
#模拟栈
def __init__(self):
selfitems=[]
#判断栈是否为空
def empty(self):
return len(self.items)==0
#返回栈的大小
def size(self):
return len(self.items)
#返回栈顶元素
def peek(self):
if not self.empty():
return self.items[len(self.items)-1]
else:
return None
#弹栈
def pop(self):
if len(self.items)＞0:
return self.items.pop()
else:
print "栈已经为空"
return None
#压栈
def push(self,item):
self.items.append(item)
def isPopSerial(push,pop):
if push==None or pop==None:
return False
pushLen=len(push)
popLen=len(pop)
if pushLen!=popLen:
return False
pushIndex=0
popIndex=0
stack=Stack()
while pushIndex＜pushLen:
#把push序列依次入栈,直到栈顶元素等于pop序列的第一个元素
stack.push(push[pushIndex])
pushIndex+=1
#栈顶元素出栈, pop序列移动到下一个元素
while (not stack.empty()) and stack.peek()==pop[popIndex]:
stack.pop()
popIndex+=1
#栈为空, 且pop序列中元素都被遍历过
return stack.empty() and popIndex==popLen
if __name__=="__main__":
push="12345"
pop="32541"
if isPopSerial(push,pop):
print pop+"是"+push+"的一个pop序列"
else:
print pop+"不是"+push+"的一个pop序列"
程序的运行结果为：
32541是12345的一个pop序列
算法性能分析：
这种方法在处理一个合理的pop序列的时候需要操作的次数最多，即把push序列进行一次压栈和出栈操
作，操作次数为2N，因此，时间复杂度为O(N)，此外，这种方法使用了额外的栈空间，因此，空间复杂度
为O(N)。
');
![\"360截图20190815223146746.jpg\"](\"http://www.alatiku.com/d/file/shiti/a1026d51c511351f7ec99e4c12ce58e2.jpg\")