包含min函数的栈
一、题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
二、解题思路
2.1 核心步骤
把每次的最小元素（之前的最小元素和新压入栈的元素两者的较小值）都保存起来放到另外一个辅助栈里。下图展示了栈内压入3、4、2、1之后接连两次弹出栈顶数字再压入0时，数据栈、辅助栈和最小值的状态。
从表中我们可以看出，如果每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。
2.2 代码实现
import java.util.Stack;
public class Solution {
// 数据栈
Stack<Integer> dataStack = new Stack<Integer>();//存放元素栈
// 辅助栈
Stack<Integer> minStack = new Stack<Integer>();//辅助栈，data栈中每次进入一个元素，min辅助栈就存放当前data栈中的最小元素
///每次压入数据栈数据与最小数据进行比较，如果更小，存入数据栈同时，存入辅助栈，并且最小值设置为该数据
public void push(int node) {
dataStack.push(node);//dataStack栈进入元素
if(minStack.isEmpty()||node<minStack.peek()){
minStack.push(node);
}else{minStack.push(minStack.peek());}
}
//dataStack和minStack弹出元素
public void pop() {
if(dataStack.size()>0&&minStack.size()>0){
dataStack.pop();
minStack.pop();
}
}
//data栈的栈顶元素
public int top() {// 方法的定义需要有返回函数
if(dataStack.size()>0){
return dataStack.peek();
}
return 0;
}
public int min() {
if(minStack.size()>0){
return minStack.peek();//得到元素，不需要弹出
}
return 0;
}
}注意：
何时需要写返回值
//dataStack和minStack弹出元素
public void pop() {
if(dataStack.size()>0&&minStack.size()>0){
dataStack.pop();
minStack.pop();
}
}
//data栈的栈顶元素
public int top() {// 方法的定义需要有返回函数
if(dataStack.size()>0){
return dataStack.peek();
}
return 0;
}