首页 > 代码库 > 栈、队列系列之实现一个包含min函数的栈
栈、队列系列之实现一个包含min函数的栈
问题:实现一个栈,除了push、pop操作外,还包括函数min实现返回栈中最小值的功能,要求时间复杂度均为O(1)
思路:增加一个辅助栈,将每次入栈操作后栈的最小元素(之前最小元素和新入栈元素的较小值)都保存在辅助栈里
实现:
#include <iostream> #include <stack> #include <assert.h> using namespace std; template <typename T> class StackWithMin { public: StackWithMin(){} //构造函数 ~StackWithMin(){} //析构函数 T& top(); const T& top() const; //取栈顶元素 void pop(); //删除栈顶元素 void push(const T& value); //将元素压入栈 const T& min() const; //取栈中最小元素 bool empty() const; size_t size(); private: stack<T> m_data; stack<T> m_min; //辅助栈 }; template <typename T> void StackWithMin<T>::push(const T &value) //入栈 { m_data.push(value); if(m_min.size()==0 || value<m_min.top()) //如果比辅助栈栈顶元素小,压入辅助栈中 { m_min.push(value); } else //否则将当前最小值再压入一遍 { m_min.push(m_min.top()); } } template <typename T> void StackWithMin<T>::pop() //出栈 { assert(m_data.size()>0 && m_min.size()>0); m_data.pop(); m_min.pop(); } template <typename T> const T& StackWithMin<T>::min() const //返回栈中最小值 { assert(m_data.size()>0 && m_min.size()>0); return m_min.top(); } template <typename T> const T& StackWithMin<T>::top() const //返回栈顶元素 { return m_data.top(); } template <typename T> bool StackWithMin<T>::empty() const { return m_data.empty(); } template <typename T> size_t StackWithMin<T>::size() { return m_data.size(); } void test_StackWithMin() { StackWithMin<int> test_stack; test_stack.push(3); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.push(4); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.push(2); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.push(1); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.pop(); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.pop(); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; test_stack.push(0); cout<<"栈中最小元素为:"<<test_stack.min()<<endl; } int main() { test_StackWithMin(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。