- import java.util.EmptyStackException;
- //实现一个栈,满足min() pop() push()方法的时间复杂度都为O(1).( min()返回栈中最小元素)
- public class MinStack {
- private Entry current;
- public MinStack() {
- current = new Entry();
- current.min = Integer.MAX_VALUE;
- current.next = current;
- }
- public int min() {
- if(isEmpty()) {
- throw new EmptyStackException();
- }
- return current.min;
- }
- public int pop() {
- if(isEmpty()) {
- throw new EmptyStackException();
- }
- int val = current.value;
- current = current.next;
- return val;
- }
- public void push(int val) {
- Entry e = new Entry();
- e.value = val;
- e.min = Math.min(val, current.min);
- e.next = current;
- current = e;
- }
- public boolean isEmpty() {
- return current == current.next;
- }
- static class Entry {
- int value;
- int min;
- Entry next;
- }
- public static void main(String[] args) {
- MinStack stack = new MinStack();
- for(int i=0;i<10;i++) {
- int random = (int)(Math.random() * 100);
- System.out.print(random + " ==== ");
- stack.push(random);
- System.out.println(stack.min());
- }
- System.out.println();
- System.out.println();
- System.out.println();
- while(!stack.isEmpty()) {
- System.out.print(stack.pop() + " ==== ");
- System.out.println(stack.min());
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2407201410054.html
来源: http://www.codesnippet.cn/detail/2407201410054.html