河南公司网站建设/视频号推广

采用两个双端队列实现，一个存数据，一个是辅助栈，存第一个栈的最小元素的地址，实现技巧在于辅助栈存放的是第一个栈的最小元素的地址，难度在于使用模板实现。

#include <deque>
#include <assert.h>
#include <iostream>

using namespace std;

template <typename T>class CStackWithMin
{
public:
 CStackWithMin(void){}
 virtual ~CStackWithMin(void){}

 T& top(void);
 const T&top(void)const;

 void push(const T& value);
 void pop(void);

 const T& min(void) const;

 const T& size(void) const;

private:
 deque<T> m_data;//the element of the stack
 deque<size_t> m_minIndex; //the index of minimum elements
};

template<typename T> T& CStackWithMin<T>::top()
{
 return m_data.back();
}

template<typename T> const T& CStackWithMin<T>::top() const
{
 return m_data.back();
}

template<typename T> void CStackWithMin<T>::push(const T& value)
{
 m_data.push_back(value);

 if (m_minIndex.size()==0)
 {
  m_minIndex.push_back(0);
 }
 else
 {
  if(value<m_data[m_minIndex.back()])
   m_minIndex.push_back(m_data.size()-1);
  else
   m_minIndex.push_back(m_minIndex.back());
 }
}

template<typename T> void CStackWithMin<T>::pop()
{
 m_data.pop_back();

 m_minIndex.pop_back();
}

template<typename T>const T& CStackWithMin<T>::min()const
{
 assert(m_data.size()>0);
 assert(m_minIndex.size()>0);

 return m_data[m_minIndex.back()];
}

template<typename T>const T& CStackWithMin<T>::size() const
{
 assert(m_data.size()>0);
 assert(m_minIndex.size()>0);

 return m_data.size();
}

int main()
{
 CStackWithMin<int> cs;

 cs.push(3);
 cs.push(4);
 cs.push(2);
 cs.push(1);
 cs.push(5);
 cs.push(6);
 cs.push(0);
 cout<<"cs.size() = "<<cs.size()<<endl;
 int len=cs.size();
 for (int i=0; i<len; i++)
 {
  cout<<"cs.min() = "<<cs.min()<<endl;
  cout<<"cs.top() = "<<cs.top()<<endl;
  cs.pop();
 }

 return 0;
}