实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能：
1）pop、push、getMin操作的时间复杂度都是O(1)
2）设计的栈类型可以使用现成的栈结构
package com.harrison.class02; import java.util.Stack; public class Code06_GetMinStack { public static class MyStack1{ public Stack<Integer> stackData; public Stack<Integer> stackMin; public MyStack1() { stackData=new Stack<Integer>(); stackMin=new Stack<Integer>(); } public void push(int newNum) { if(stackMin.isEmpty()) { stackMin.push(newNum); }else if(newNum<=getMin()) { stackMin.push(newNum); } stackData.push(newNum); } public int pop() { if(stackData.isEmpty()) { throw new RuntimeException("栈空了！"); } int value=stackData.pop(); if(value==getMin()) { stackMin.pop(); } return value; } public int getMin() { if(stackMin.isEmpty()) { throw new RuntimeException("栈空了"); } return stackMin.peek(); } } public static class MyStack2{ private Stack<Integer> stackData; private Stack<Integer> stackMin; public MyStack2() { stackData=new Stack<Integer>(); stackMin=new Stack<Integer>(); } public void push(int newNum) { if(stackMin.isEmpty()) { stackMin.push(newNum); }else if(newNum<getMin()) { stackMin.push(newNum); }else { int newMin=stackMin.peek(); stackMin.push(newMin); } stackData.push(newNum); } public int pop() { if(stackData.isEmpty()) { throw new RuntimeException("栈空了！"); } this.stackMin.pop(); return stackData.pop(); } public int getMin() { if(stackMin.isEmpty()) { throw new RuntimeException("栈空了！"); } return stackMin.peek(); } } public static void main(String[] args) { MyStack1 stack1=new MyStack1(); stack1.push(3); System.out.println(stack1.getMin()); stack1.push(4); System.out.println(stack1.getMin()); stack1.push(1); System.out.println(stack1.getMin()); System.out.println(stack1.pop()); System.out.println(stack1.getMin()); System.out.println("======================"); MyStack2 stack2=new MyStack2(); stack2.push(3); System.out.println(stack2.getMin()); stack2.push(4); System.out.println(stack2.getMin()); stack2.push(1); System.out.println(stack2.getMin()); System.out.println(stack2.pop()); System.out.println(stack2.getMin()); } }
