包含min函数的栈

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中调用min,pop,push函数的时间复杂度都是O(1)。

#include <stack>
#include <assert.h>
using namespace std;

template <typename T> class StackWidthMin{
public:
 StackWidthMin(){}
 ~StackWidthMin(){}
 T& top();
 void pop();
 void push(const T& value);
 const T& min(void) const;
 bool empty() const;
 size_t size() const;

private:
 //数据栈，存放栈的所有元素
 stack<T> m_data;
 //辅助栈，存放栈的最小元素
 stack<T> m_min;
};

 template <typename T> bool StackWidthMin<T>::empty() const
 {
  return m_data.empty();
 }
 
  template <typename T> size_t StackWidthMin<T>::size() const
  {
   return m_data.size();
  }
 
  template <typename T> void StackWidthMin<T>::push(const T &value)
  {
   m_data.push(value);
   if (m_min==0||value<m_min.top())
   {
    m_min.push(value);
   }
   else
   {
    m_min.push(m_min.top());
   }
  }
 
  template <typename T> void StackWidthMin<T>::pop()
  {
   assert(m_data.size()>0&&m_min.size()>0);
   m_data.pop();
   m_min.pop();
  }

  template <typename T> T& StackWidthMin<T>::top()
  {
  m_data.top();
  }
 
  template <typename T> const T& StackWidthMin<T>::min(void)
  {
  assert(m_data.size>0&&m_min.size()>0);
  return m_min.top();
  }

本文永久更新链接地址：