看书时遇到这样一道题，挺有趣的数据结构，所以记录下来

实现一个栈，该栈带有出栈(pop)，入栈(push)，取最小元素(getMin)，三个方法。要保证这3个方法的时间复杂度都是O(1)

1.定义两个栈，一个栈自定义栈用于入栈、出栈，一个辅助栈用于动态存放自定义栈的最小值

2.入栈操作，当元素压入 自定义栈 的时候，会判断辅助栈是否为空，
如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入(push) 辅助栈。

因为当第一个元素入栈时，这个唯一的元素也就是自定义栈当前最小的值，所以也压入(push) 辅助栈

3.出栈操作，如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。

代码如下：

如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈

/** * 入栈操作 * @param element 入栈的元素 */ public void push(int element){ mainStack.push(element); //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈 if(minStack.empty()|| element <= minStack.peek()){ //empty() 表示的是测试堆栈是否为空。 //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。 minStack.push(element); } }出栈操作

如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。

/** * 出栈操作 */ public Integer pop(){ //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 if(mainStack.peek().equals(minStack.peek())){ minStack.pop(); } return mainStack.pop(); }获取栈的最小元素(getMin方法)

/** * 获取栈的最小元素 */ public int getMin() throws Exception{ if(mainStack.empty()){ throw new Exception ("stack is empty"); } return minStack.peek(); } 主函数

元素入栈，输出最小值，元素出栈，再输出最小值

public static void main(String[] args) throws Exception { MinStack stack=new MinStack(); stack.push(4); stack.push(9); stack.push(7); stack.push(3); stack.push(8); stack.push(5); System.out.println(stack.getMin()); stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.getMin()); }

运行结果：
3
4

package min_ini;import java.util.Stack;public class MinStack { private Stack<Integer> mainStack=new Stack<Integer>(); private Stack<Integer> minStack=new Stack<Integer>(); /** * 入栈操作 * @param element 入栈的元素 */ public void push(int element){ mainStack.push(element); //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈 if(minStack.empty()|| element <= minStack.peek()){ //empty() 表示的是测试堆栈是否为空。 //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。 minStack.push(element); } } /** * 出栈操作 */ public Integer pop(){ //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 if(mainStack.peek().equals(minStack.peek())){ minStack.pop(); } return mainStack.pop(); } /** * 获取栈的最小元素 */ public int getMin() throws Exception{ if(mainStack.empty()){ throw new Exception ("stack is empty"); } return minStack.peek(); } public static void main(String[] args) throws Exception { MinStack stack=new MinStack(); stack.push(4); stack.push(9); stack.push(7); stack.push(3); stack.push(8); stack.push(5); System.out.println(stack.getMin()); stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.getMin()); }}