Stack_Queue 栈实现min函数 @CareerCup

原文：

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

译文：

实现一个栈，除了push和pop操作，还要实现min函数以返回栈中的最小值。 push，pop和min函数的时间复杂度都为O(1)。

用一个额外的栈保存最小值，push时，如果要push的值小等于当前最小值，则也push到最小栈中。

pop时，如果pop出的值等于当前最小值，则也把当前最小值pop出。

package Stack_Queue;

import java.util.Stack;

public class S3_2 {

	static Stack<Integer> min = new Stack<Integer>();
	static Stack<Integer> stack = new Stack<Integer>();

	// 如果要push的值小等于当前最小值，则也push到最小栈中
	public static void push(int data) {
		stack.push(data);
		if(min.isEmpty() || data<=min.peek()) {
			min.push(data);
		}
	}

	// 如果pop出的值等于当前最小值，则也把当前最小值pop出
	public static int pop() {
		int res = stack.pop();
		if(res == min.peek()) {
			min.pop();
		}
		return res;
	}
	
	public static int getMin() {
		return min.peek();
	}
	
	public static void main(String[] args) {
		push(2);
		push(6);
		push(4);
		push(1);
		push(5);
		
		System.out.println(getMin());
		pop();
		System.out.println(getMin());
		pop();
		System.out.println(getMin());
		pop();
		System.out.println(getMin());
		pop();
		System.out.println(getMin());
		pop();
	}
}

Stack_Queue 栈实现min函数 @CareerCup,布布扣,bubuko.com

Stack_Queue 栈实现min函数 @CareerCup

原文：http://blog.csdn.net/fightforyourdream/article/details/20211169