O(1)时间复杂度求栈的最小元素

题目：

   定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

 

思路：
   栈数据结构的特点是先进后出，push和pop操作都是对栈顶元素进行的操作，所以都是常数时间复杂度，即O(1),但是由于栈中数据是无序的，所以仅仅通过栈是无法得到最小元素的，又由于每次出栈和进栈都可能会使栈的最小元素发生变化，所以考虑用一个辅助的栈空间来存储每次进栈和出栈之后的最小元素，为了节省空间，辅助栈中不存储最小元素的值，而存储最小元素的地址或者在数据栈中的索引。

 

代码：
#include
using namespace std;

template class CStack
{
public:
 CStack();
 ~CStack();
 
 void pop(T& value);
 void push(const T& value);
 const T& getMin() const;
private:
 vector _data;
 vector _minIndex;
}

template CStack::CStack()
{
}

template CStack::~CStack()
{
}

template void CStack::pop(T& value)
{
 if(_data.empty())
 {
  return;
 }
 else
 {
  value = _data.back();
  _data.pop_back();
  _minIndex.pop_back();
 }
}

template void CStack::push(T& value)
{
 _data.push_back(value);
 
 if(_minIndex.empty())
 {
  _minIndex.push_back(0);
 }
 else if(value < _data[_minIndex.back()])
 {
  _minIndex.push_back(_data.size()-1);
 }
 else
 {
  _minIndex.push_back(_minIndex.back());
 }
}

template const T&CStack::getMin() const
{
 assert( !_data.empty() );
 assert( !_minIndex.empty() );
 
 return _data[_minIndex.back()];
}