Day5-线性表-栈-最小栈问题
一 先唠两句
本来昨天就应该更新栈的问题了，可为什么没有更新呢？
因为我忘了
而且今天本来按照之前说的，应该更两篇的，但是今天只有一篇盒饭，还不是因为最近需求排的紧，加班加点干活，大哥们见谅
二 上车！
设计一个栈，支持如下操作：
push（x）：将元素x压入栈中
pop（）：弹出栈顶元素
top（）：返回栈顶元素
getMin（）：返回栈中最小的元素
三 冷静分析
前提：栈，先进后出的数据结构，c++标准STL支持，需要“#include<stack>”
前三个操作都好说，都是常规操作
怎么实现，实时获取最小值？
这就需要用到栈、队列中的一个常规思想：再用一个栈（or队列）
引入另外一个栈，即最小栈，它的栈顶元素实时都是最小的
怎么实现呢？
冷静分析：
首先我们需要知道，最小栈和数据栈需要保持相同个数的元素？
为啥呢？
当数据栈弹出栈顶元素时，最小栈也要同时弹出栈顶，此时的栈顶，仍然为最小元素。这就保持了，不管数据栈执行什么操作，最小栈的栈顶，都是最小元素。
那么
数据栈压栈的时候，若压栈的这个数，小于等于当前最小栈栈顶元素，即它应该是新的最小值，那么最小栈压栈；
数据栈压栈的时候，若压栈的这个数，大于当前最小栈栈顶元素，则取出当前最小栈栈顶元素，讲该元素压入最小栈栈顶。
即，数据栈压栈时，最小栈也要压栈，压入当前的最小元素
有点拗口是不是，我举个例子~
第一次，栈空时，来了个-3，数据栈压栈，最小栈压栈
第二次，来了个-5，数据栈压栈-5，-5<-3，最小栈压栈-5
此时我getMin，最小栈栈顶是-5，没毛病~
第三次，来了个0，数据栈压栈0，0>-5，则最小栈再压栈当前的最小元素，即-5
第四次，我执行pop，弹出栈顶，最小栈也要弹，-5弹出
第五次，我再执行pop，最小栈再弹-5，此时最小栈栈顶是-3，getMin也是-3，没毛病
四 完整代码及运行结果
//
// Created by renyi on 2019/6/3.
//
#include <iostream>
#include <stack>
using namespace std;
class MinStack{
public:
MinStack(){
}
void push(int x){
_data.push(x);//数据栈正常把元素压栈
if(_min.empty()){
_min.push(x);//如果最小栈是空，没元素，直接压栈
} else{
if (x > _min.top()){
x = _min.top();//如果x大于最小栈的栈顶，则取出最小栈的栈顶，赋值给x，以便后面的压栈
}
_min.push(x);//不管怎样，都会将当前最小的元素压栈，保证和数据栈元素个数相同
}
}
void pop(){
_data.pop();//出栈，大家都出栈，保持元素个数相同
_min.pop();
}
int top(){
return _data.top();//top就正常返回数据栈的栈顶
}
int getMin(){
return _min.top();//getmin就是返回最小栈的栈顶
}
private:
stack<int> _data;//数据栈
stack<int> _min;//最小栈
};
int main(){
MinStack minStack;
minStack.push(-3);//先压栈3，此时getmin应该是-3
printf("top:[%d]\n", minStack.top());
printf("min:[%d]\n\n", minStack.getMin());
minStack.push(-5);//此时getmin应该是-5
printf("top:[%d]\n", minStack.top());
printf("min:[%d]\n\n", minStack.getMin());
minStack.push(-7);//此时getmin应该是-7
printf("top:[%d]\n", minStack.top());
printf("min:[%d]\n\n", minStack.getMin());
minStack.pop();//此时执行了pop（），-7出栈了，getmin应该是-5
printf("top:[%d]\n", minStack.top());
printf("min:[%d]\n\n", minStack.getMin());
minStack.push(0);//0入栈，此时getmin还是-5
printf("top:[%d]\n", minStack.top());
printf("min:[%d]\n\n", minStack.getMin());
return 0;
}
运行结果为：
五 总结一下
栈，队列的重要思想：再用一个
最小栈的思想：保持同步操作，你压栈我也压栈，你出栈，我也出栈
好了，明天继续，再拖更我就出来挨打
