设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
结合链表一起做。容器vector代替链表
eg: 10，3，3，8，2，6
1.push() ：如果push入栈A的元素小于栈B的栈顶所对应的的元素，则将该元素push入栈B中； 或者第一个元素也直接push入B中
栈A 辅助栈B（ 存放最小值 ）
6 2 min=2
2 2 min=2
8 3 min=3
3 3 min=3
3 3 min=3
10 10 min=10
2.pop() ：栈A删去一个，栈B也删去一个
栈A 辅助栈B
6 min=2
2 min=2
8 2
min=3
3 3 min=3 //注意最小值相等的情况
3 3 min=3
10 10 min=10
3.min() ：直接返回栈B中的最后一个元素
代码：
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
template<typename T>
class CStack //主要包含了min()功能，且时间复杂度为O(1)
{
vector<T> m_data; //用容器来模拟栈
vector<size_t> m_supply; //辅助栈
public:
void Push(T data)
{
if(m_data.empty() || data <= m_data.back() )
m_supply.push_back(data);
m_data.push_back(data);
}
void Pop()
{
assert(!m_data.empty() && !m_supply.empty());
if(m_data.back() == m_supply.back())
m_supply.pop_back();
m_data.pop_back();
}
T min()
{
return m_supply.back();
}
};
int main()
{
CStack<int> stackObj;
stackObj.Push(10);
stackObj.Push(3);
stackObj.Push(3);
stackObj.Push(8);
stackObj.Push(2);
stackObj.Push(6);
cout<<stackObj.min()<<endl;
stackObj.Pop();
stackObj.Pop();
cout<<stackObj.min()<<endl;
return 0;
}