栈的push、pop序列判定

收藏到CSDN网摘


ACM经常会碰到的一个题目: 给定一个输出序列,判断其是否可能是元素按顺序压栈后的push/pop序列.(假设没有相同元素)

其解法是构造一辅助栈,然后开始扫描输出序列的每一个元素(视为当前元素):

1. 如果辅助栈不为空且栈顶元素就是当前元素,弹出辅助栈顶,并输出
2. 如果辅助栈为空或者栈顶元素不等于当前元素,在原始序列中搜索当前元素,将其之前的所有元素压入辅助栈,并将这些元素从原始序列删除
3. 否则,break循环并返回False
4. 如果中间没有返回,说明扫描输出序列成功结束,返回True.

#! /usr/bin/env python
# coding: utf-8

def testPushPop(ele, ps):
    ori = [x.strip() for x in ele.strip().split()]
    tmp = []
    for c in [x.strip() for x in ps.strip().split()]:
        if tmp and tmp[-1]==c:
            print tmp.pop(), 
        elif ori.count(c)>0:
            tmp.extend(ori[:ori.index(c)+1])
            ori = ori[ori.index(c)+1:]
            print tmp.pop(), 
        else:
            print
            return False
    print
    return True

def main():
    a = '1 2 3 4 5'
    b = '4 5 3 2 1' # yes
    c = '4 3 5 1 2' # no
    a = 'A B C D E F G H I J'
    b = 'C B F G I J H E D A' # yes
    if testPushPop(a,b):
        print 'Yes'
    else:
        print 'No'

if __name__=='__main__':
    main()