【剑指 offer】包含min函数的栈

描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

• push(value): 将 value 压入栈中
• pop(): 弹出栈顶元素
• top(): 获取栈顶元素
• min(): 获取栈中最小元素

解题思路：

很容易想到，在栈内部保存 min 变量，每次更新的时候，都对 min 变进行更新。
但是，问题是：如果想拿出第二小，第三小的值怎么拿？用上面的办法就不行了
为了满足通用，我们使用一个辅助栈，内部保存元素的个数和数据栈完全一样，不过，辅助栈内部永远保存本次入栈的数为所有数据的最小值（注意：辅助栈内部元素可能会出现“必要性”重复）
我们这里是为了实现算法， 所以就不从 0 开始实现 stack 了
题面说了，保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法，所以，后面的代码对空的检验可有可无

import java.util.Stack;
public class Solution {private Stack<Integer> data_stack = new Stack<>();//数据栈private Stack<Integer> min_stack = new Stack<>();//辅助栈public void push(int node) {data_stack.push(node);if(min_stack.empty() || node < min_stack.peek()){min_stack.push(node);}else{//!min_stack.empty() & node >=min_stack.peek()min_stack.push(min_stack.peek());}}public void pop() {data_stack.pop();min_stack.pop();}public int top() {return data_stack.peek();}public int min() {return min_stack.peek();}
}