java实现带min()方法的栈
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
?
感谢csdn July整理题目和答案http://blog.csdn.net/v_JULY_v/article/details/6057286
?
这里我写的第二题的java 代码实现。
实现原理
入栈时，比较辅助栈栈顶元素大小，如果新增元素小于等于辅助栈栈顶元素，辅助栈同时入栈。出栈时，如果出栈元素等于辅助栈栈顶元素（即出栈元素为最小值），辅助栈同时出栈
例如压栈 5,2,2,1,6,3
栈???? 辅助栈
5???????? 5
2???????? 2
2???????? 2
1???????? 1
6???????
3
?
出栈时
3??????????1
6????????? 1
1??????????2
2????????? 2
2????????? 5
5???????? null
?
一、定义节点类，添加了遍历和添加方法，在本题目中使用不到
package cn.edu.cqupt.mircrosoft100;public class MinStack {private AssistStack assistStack=new AssistStack();//辅助栈，实现O（1）min函数private Node top;public void push(int value){Node add = new Node(value);if(null==top){top=add;assistStack.push(value);return;}add.setNext(top);top=add;refresh();}public void refresh(){int temp = top.getValue();if(temp<=assistStack.getTop().getValue())assistStack.push(temp);}public Integer pop(){Integer temp = top.getValue();if(null==temp)return null;if(temp==assistStack.getTop().getValue())assistStack.pop();top=top.getNext();return temp;}public Integer getMin(){if(null==assistStack.getTop())return null;return assistStack.getTop().getValue();}public static void main(String args[]){MinStack minStack =new MinStack();minStack.push(5);minStack.push(2);minStack.push(3);minStack.push(3);minStack.push(6);System.out.println("min:"+minStack.getMin());System.out.println("pop:"+minStack.pop()); System.out.println("min:"+minStack.getMin());System.out.println("pop:"+minStack.pop()); System.out.println("min:"+minStack.getMin());System.out.println("pop:"+minStack.pop()); System.out.println("min:"+minStack.getMin());System.out.println("pop:"+minStack.pop()); System.out.println("min:"+minStack.getMin());System.out.println("pop:"+minStack.pop()); System.out.println("min:"+minStack.getMin());}}?