首页 > 代码库 > 微软100题系列之-----设计包含min函数的栈
微软100题系列之-----设计包含min函数的栈
题意:
定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
思路:定义两个栈,一个用来记录数据的插入和删除,一个用来存储最小值的变化
代码如下:
template <class T> class Stack { public: Stack(int len=100); T Min(); T Pop(); void Push(T val); private: T top1,top2; T *stack1,*stack2; //stack2用来存储最小值的栈 }; template <class T> Stack<T>::Stack(int len) { top1 = top2 = -1; stack1 = new T[len] ; stack2 = new T[len] ; } template <class T> T Stack<T>::Min() { return stack2[top2]; } template <class T> T Stack<T>::Pop() { T temp = stack1[top1--] ; if(stack2[top2] == temp) top2--; return temp; } template <class T> void Stack<T>::Push(T val) { stack1[++top1] = val ; if(top2 == -1) stack2[++top2] = val; else if(val <= stack2[top2]) stack2[++top2] = val ; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。