面试题30：包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min,push以及pop的时间复杂度都是o(1)。
python代码：
# coding=utf8 ''' 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用 min、push及pop的时间复杂度都是O(1)。 ''' class Stack(): def __init__(self): self.main_stack = [] # 辅助栈，每次次最小的元素压入辅助栈 self.assist_stack = [] # 记录栈中的最小元素 self._min = None def min(self): return self._min def push(self, data): self.main_stack.append(data) if self._min is None: self._min = data else: if data < self._min: self._min = data # 将最小的元素压入辅助栈 self.assist_stack.append(self._min) def pop(self): if len(self.main_stack) == 0: raise Exception('no data') elif len(self.main_stack) == 1: self.assist_stack.pop() self._min = None return self.main_stack.pop() else: self.assist_stack.pop() self._min = self.assist_stack[-1] return self.main_stack.pop() if __name__ == '__main__': s = Stack() s.push(3) s.push(4) s.push(2) s.push(1) print s.min() s.pop() s.pop() print s.min() s.pop() print s.min() s.pop() print s.min() s.pop()面试题31：栈的压入，弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个顺序是否为栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列{1，2，3，4，5}是某栈的压栈序列，序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列，但{4，3，5，1，2}就不可能是该压栈序列的弹出序列。
思路：
pythond代码：
# -*- coding:utf-8 -*- class Solution: def IsPopOrder(self, pushV, popV): # write code here if len(popV) == 0 or len(pushV) != len(popV): return False stackData = [] for i in pushV: stackData.append(i) while len(stackData) and stackData[-1] == popV[0]: stackData.pop() popV.pop(0) if len(stackData): return False return True
