设计包含min函数的栈

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)

做法是利用一个辅助栈。利用这道题正好把c++模板那里复习下，发现好久不碰忘得都差不多了....

代码如下：

代码

//实现一个有min方法的堆//方法：利用一个辅助栈记录已有的最小元素，当主栈更新时，辅助栈同时更新#include<iostream>#include<algorithm>#include<stack>using namespace std;template<class T> class Stack{  //自己定义的栈private:    stack<T> s; //主栈    stack<T> minS; //辅助栈public:    bool empty(void);    T pop(void);    void push(T elem);    //T top(void);    T min(void);};template<class T> T Stack<T>::pop(void){    T elem=s.top();    s.pop();    minS.pop();    return elem;}template<class T> T Stack<T>::min(void){    return minS.top();}template<class T> void Stack<T>::push(T elem){   //关键    s.push(elem);    if(minS.empty()){minS.push(elem);}  //若是首元素则进辅助栈    else{                               //若不是则与辅助栈顶元素比较        T temp=minS.top();        if(temp<elem) minS.push(temp);        else minS.push(elem);    }}template<class T>bool Stack<T>::empty(void){    return s.empty();}int main(void){    Stack<int> my;    my.push(4);    cout<<my.min()<<endl;    my.push(8);    cout<<my.min()<<endl;    my.push(0);    cout<<my.min()<<endl;    my.pop();    cout<<my.min()<<endl;    system("pause");    return 0;}

原文链接: https://www.cnblogs.com/aLittleBitCool/archive/2011/01/15/1936466.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍