首页 > 代码库 > 设计包含min函数的栈
设计包含min函数的栈
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、pop、push的时间复杂度为O(1);
方法：采用一个辅助栈，该栈用来存放最小元素。当进行push操作时，将栈中的最小元素同时push进辅助栈中，当pop操作时同时pop掉辅助栈中的栈顶元素。这样元素栈对应位置的辅助栈中存放的永远是最小元素。
#include<iostream>#include<stack>using namespace std;template<class T>class StackWithMin{public: void push(const T value); void pop(); T min();private: stack<T> dataStack; stack<T> minStack;};template <class T>void StackWithMin<T>::push(T value){ dataStack.push(value); if(minStack.size()==0) { minStack.push(value); } else if(value<minStack.top()) { minStack.push(value); } else { minStack.push(minStack.top()); }}template <class T>void StackWithMin<T>::pop(){ dataStack.pop(); minStack.pop();}template <class T>T StackWithMin<T>::min(){ T p; p=minStack.top(); return p;}int main(){ int t; StackWithMin<int> s; s.push(3); s.push(1); s.push(5); s.push(6); s.push(0); t=s.min(); cout<<"min:"<<t<<endl; s.pop(); t=s.min(); cout<<"min:"<<t<<endl; return 0;}
设计包含min函数的栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。