首页 > 代码库 > Min Stack

Min Stack

2024-08-01 22:40:44   225人阅读

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

使用C++编程，其中使用了标准库中的容器stack，使用两个stack，一个用来存放最小优先的栈s1，一个用来存放所以元素s2。

对于push操作，如果x小于等于s1中的栈顶元素，则将x压入s1和s2，否则x大于s1的栈顶元素，则将x只压入s2中。

对于pop操作，如果要出栈，则正常情况下，从s2中弹出栈顶元素，但是当s1的栈顶元素与s2的栈顶元素相同的时候，则需要将s1和s2的栈顶元素都弹出来

对于top操作，访问栈顶元素，只有s2不为空，就可以直接访问栈顶元素

对于getMin擦，从s1中返回的栈顶元素就是最小的元素

C++完整代码如下：

#include<iostream>#include<stack>using namespace std;class MinStack {public:    void push(int x) {        if(s2.empty())        {            s1.push(x);            s2.push(x);            return;        }        int tmp=s1.top();        if(x<=tmp)            s1.push(x);        s2.push(x);    }    void pop() {        if(!s2.empty())        {            if(s1.top()==s2.top())                s1.pop();            s2.pop();        }    }    int top() {        if(!s2.empty())            return s2.top();        return 0;    }//s1为空的时候，s2同样也会为空    int getMin() {        if(!s1.empty())            return s1.top();        return 0;    }private:    stack<int> s1;//存放最小值    stack<int> s2;//存放所有的元素};int main(){    MinStack minstack;    minstack.push(100);    minstack.push(24);    minstack.push(30);    cout<<minstack.getMin()<<endl;}

运行结果：

还有一种比较笨的方法是每次要push一个元素时，将元素x插入在最小栈中，但是这样需要每次将元素插入到正确的位置，因此需要排序所有的元素。

#include<iostream>#include<stack>using namespace std;class MinStack {public:    void push(int x) {        int tmp;        while(!s1.empty())        {            tmp=top();            if(x<=tmp)                break;            else            {                s1.pop();                s2.push(tmp);            }        }        s1.push(x);        while(!s2.empty())        {            tmp=s2.top();            s2.pop();            s1.push(tmp);        }    }    void pop() {        if(!s1.empty())            s1.pop();    }    int top() {        if(!s1.empty())            return s1.top();        return 0;    }    int getMin() {        if(!s1.empty())            return s1.top();        return 0;    }private:    stack<int> s1;    stack<int> s2;};int main(){    MinStack minstack;    minstack.push(1);    minstack.push(2);    minstack.push(3);    cout<<minstack.getMin()<<endl;}

 

Min Stack


联系
我们