首页 > 代码库 > Min Stack

Min Stack

2024-08-08 02:15:32   214人阅读

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.
思路：同时维护两个栈，正常的进出都往datastack里进行，push的时候，如果minstack是空的，或者最上面的元素大小比push的元素大，则同时push minstack，这样minstack的top元素永远维持当前栈中最小的元素；pop的时候，先pop datastack，如果datastack的栈顶元素和minstack的栈顶元素一样大，则同时pop minstack。

C：
#include<stdlib.h>
#include<stdio.h>


struct node
{
    int data;
    struct node* down;
};
typedef struct node node;


struct stack
{
    node* top;
    int size;
};
typedef struct stack Stack;


Stack* EmptyStack()
{
    Stack *top = (Stack*)malloc(sizeof(Stack*));
    if(top)
    {
        top->top = NULL;
        top->size = 0;
    }
    return top;
}


void push(Stack* stack,Stack* minstack,int x) {
    node* newtop=(node *)malloc(sizeof(node));
    newtop->data=http://www.mamicode.com/x;>

C++
class MinStack {
private:
    stack<int> datastack;
    stack<int> minstack;
public:
    void push(int x) {
        datastack.push(x);
        if(minstack.empty() || x<=minstack.top())
            minstack.push(x);
    }

    void pop() {
        int data=http://www.mamicode.com/datastack.top();>

Min Stack






























        

            
                
                  
                
                

                    联系

                    我们