定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中调用min,pop,push函数的时间复杂度都是O(1)。
#include
#include
using namespace std;
template 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 m_data;
?//辅助栈,存放栈的最小元素
?stack m_min;
};
?template bool StackWidthMin::empty() const
?{
? return m_data.empty();
?}
?
? template size_t StackWidthMin::size() const
? {
? ?return m_data.size();
? }
?
? template void StackWidthMin::push(const T &value)
? {
? ?m_data.push(value);
? ?if (m_min==0||value? ?{
? ? m_min.push(value);
? ?}
? ?else
? ?{
? ? m_min.push(m_min.top());
? ?}
? }
?
? template void StackWidthMin::pop()
? {
? ?assert(m_data.size()>0&&m_min.size()>0);
? ?m_data.pop();
? ?m_min.pop();
? }
? template T& StackWidthMin::top()
? {
? m_data.top();
? }
?
? template const T& StackWidthMin::min(void)
? {
? assert(m_data.size>0&&m_min.size()>0);
? return m_min.top();
? }