【25】实现一个含有min函数的栈的通用模板

题目：设计一个栈类型，使得在该栈类型中有一个函数min可以得到栈的最小元素，要求这个栈的push、pop、min都是O(1)。

分析：

1. 栈的性质是先进后出，因此一般情况下栈的push、pop的时间是O(1)，但是要求栈的min必须要枚举整个栈，时间复杂度为O(n)

2. 题目要求设计一个栈在O(1)的时间内找到min，我们要想到一个方法来满足，先看一个例子

3. 从下面的表中我们可以很清楚的看到，我么需要维护一个保存min的栈，并且这个栈和我们的数据栈是一起变化的，因此我们可以利用两个栈来模拟实现这个过程

操作

栈的元素（左边栈顶）

最小值

第一次

Push 5

5

第二次 

Push 6

6 5

第三次

Push 4

4 6 5

4

第四次

Push 7

7 4 6 5

第五次

Push 9

9 7 4 6 5

第六次

Pop

第七次

第八次

第九次

4. 示例代码