欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法之最小栈求解

程序员文章站 2022-06-08 18:34:33
...

问题描述

设计一个支持 push ,pop ,top 操作,并能提供一个获取最小值的方法getMin() 。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

解题思路

算法之最小栈求解
创建一个类名为Stack,内部依赖两个栈结构(_stack 和_stageStack)。第一个用来存真实的数据;而第二个栈用来存储当前栈中的最小值。

根据题意 新建头文件Stack.hpp,内容如下:

#ifndef Stack_hpp
#define Stack_hpp

#include <stdio.h>
#include <stack>

using namespace std;
class Stack{
private:
    stack<int>* _stack;
    stack<int>* _stageMinStack;
    
public:
    Stack();
    ~Stack();
    void push(int);
    void pop();
    int top();
    int getMin();
    bool empty();
};

#endif /* Stack_hpp */

具体的方法实现,内容如下:


#include "Stack.hpp"

Stack::Stack(){
    _stack = new stack<int>();
    _stageMinStack = new stack<int>();
}

Stack::~Stack(){
    free(_stageMinStack);
    free(_stack);
}

void Stack::pop(){
    if(_stack->empty()){
        return;
    }
    int top = _stack->top();
    //这里是所有判断要出栈的值大于_stageMinStack 栈顶的值,是因为_stageMinStack是绝对递增的
    //_stageMinStack的绝对递增是由其入栈逻辑决定的
    if(top== _stageMinStack->top()){
        _stageMinStack->pop();
    }
    _stack->pop();
}

void Stack::push(int ele){
    if(_stageMinStack->empty()){
        _stageMinStack->push(ele);
        //避免出现一对多的现象
    }else if(ele <= _stageMinStack->top()){
        _stageMinStack->push(ele);
    }
    _stack->push(ele);
}


int Stack::top(){
    if(_stack->empty()) return -1;
    return _stack->top();
}

int Stack::getMin(){
    if(_stageMinStack->empty()) return -1;
    return _stageMinStack->top();
}

bool Stack::empty(){
    return _stack->empty();
}

测试代码

int main(int argc, const char * argv[]) {
    Stack _stack;
    _stack.push(8);
    _stack.push(7);
    _stack.push(9);
    _stack.push(1);
    
    while (!_stack.empty()) {
        cout << _stack.getMin() <<endl;
        _stack.pop();
    }
    return 0;
}