题目：设计一个栈类型，使得在该栈类型中有一个函数min可以得到栈的最小元素，要求这个栈的push、pop、min都是O(1)。
分析：
1. 栈的性质是先进后出，因此一般情况下栈的push、pop的时间是O(1)，但是要求栈的min必须要枚举整个栈，时间复杂度为O(n)
2. 题目要求设计一个栈在O(1)的时间内找到min，我们要想到一个方法来满足，先看一个例子
3. 从下面的表中我们可以很清楚的看到，我么需要维护一个保存min的栈，并且这个栈和我们的数据栈是一起变化的，因此我们可以利用两个栈来模拟实现这个过程
操作 |
栈的元素（左边栈顶） |
最小值 |
|
第一次 |
Push 5 |
5 |
5 |
第二次 |
Push 6 |
6 5 |
5 |
第三次 |
Push 4 |
4 6 5 |
4 |
第四次 |
Push 7 |
7 4 6 5 |
4 |
第五次 |
Push 9 |
9 7 4 6 5 |
4 |
第六次 |
Pop |
7 4 6 5 |
4 |
第七次 |
Pop |
4 6 5 |
4 |
第八次 |
Pop |
6 5 |
5 |
第九次 |
Pop |
5 |
5 |
4. 示例代码
//实现含有min的栈类模板
template <typename T>
class Stack{
public:
Stack(void);
~Stack(void){}
//声明函数
void Push(const T& value);
void Pop(void);
T Min(void);
private:
stack<T> dataStk;
stack<T> minStk;
};
//实现构造函数
template <typename T> Stack<T>::Stack(void){
//清空两个栈
while(!dataStk.empty()){
dataStk.pop();
}
while(!minStk.empty()){
minStk.pop();
}
}
//实现Push
template <typename T> void Stack<T>::Push(const T& value){
dataStk.push(value);
//如果是空栈直接插入，不能通过取栈顶元素比较
if(minStk.empty()){
minStk.push(value);
}
else{
T minValue = minStk.top();
if(minValue > value){
minValue = value;
}
//插入到minStk中
minStk.push(minValue);
}
}
//实现Pop函数
template <typename T> void Stack<T>::Pop(void){
//如果是空栈报异常
if(dataStk.empty()){
throw exception("error");
}
else{
dataStk.pop();
minStk.pop(); //同时删除minStk栈顶元素
}
}
//实现Min函数
template <typename T> T Stack<T>::Min(void){
//如果空栈返回异常
if(minStk.empty()){
throw exception("error");
}
else{
return minStk.top();
}
}
