问题描述：
定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
双倍空间实现：
保存2个栈，分别是元素和当前最小值。
压缩空间实现：
？
代码实现：
package oschina.IT100;/** * @project: oschina * @filename: IT2.java * @version: 0.10 * @author: JM Han * @date: 17:08 2015/10/20 * @comment: design a stack that has min function which could return the min element at anytime * @result: */import java.util.Stack;class MinStack{ Stack stacks, mins; MinStack(){ stacks = new Stack (); mins = new Stack (); } void push(Integer x){ stacks.push(x); //use <= instead of < for duplicate element if(mins.isEmpty() || x <= mins.peek()) mins.push(x); } void pop(){ Integer x = stacks.pop(); if(x == mins.peek()) mins.pop(); } Integer peek(){ return stacks.peek(); } Integer getMin(){ return mins.peek(); }}public class IT2 { public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(6); minStack.push(2); minStack.push(3); minStack.push(1); minStack.push(1); minStack.push(5); minStack.push(8); System.out.println("Content of stack: \n" + minStack.stacks); System.out.println("min value of stack: \n" + minStack.getMin()); System.out.println("Content of mins: \n" + minStack.mins); minStack.pop(); minStack.pop(); minStack.pop(); System.out.println("Content of mins: \n" + minStack.mins); System.out.println("min value of stack: \n" + minStack.getMin()); }} 输出：
Content of stack: [6, 2, 3, 1, 1, 5, 8]min value of stack: 1Content of mins: [6, 2, 1, 1]Content of mins: [6, 2, 1]min value of stack: 1