Crackingcodinginterview(3.2)堆栈实现常量复杂度的min函数

3.2 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. 1. Stack1，push(), pop()时间复杂度:O(n) 2.Stack2,与Stack3,满

3.2 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.

1. Stack1，push(), pop()时间复杂度:O(n)

2.Stack2,与Stack3,满足要求，Stack3更优化，消除了部分冗余

3.堆栈特点，在当前元素为弹出时，当前元素的最小值不会改变

import java.util.Stack;

class Stack1{
	private Node top = null;
	private Node first = null;
	class Node{
	int val;
	Node next;
	Node min;
	public Node(int val){
	this.val = val;
	this.next = null;
	this.min = null;
	}
	}
	//time complexity:O(n) 
	public void push(int val){
	if(top != null){
	Node n = new Node(val);
	n.next = top;
	top = n;

	if(first.val < val){
	//time complexity:O(n)
	Node p = null;
	for(p = first;;p = p.min)
	if(p.min == null || val < p.min.val){
	n.min = p.min;
	p.min = n;
	break;
	}
	
	}else{
	n.min = first;
	first = n;
	}
	
	}else{
	top = new Node(val);
	first = top;
	}
	}
	//time complexity:O(n) 
	public int pop(){
	if(top != null){
	Node n = top;
	top = top.next;
	
	Node p = null;
	if(!n.equals(first)){
	for(p = first;!n.equals(p.min);p = p.min)
	;
	p.min = p.min.min;
	}else{
	first = first.min;
	}	
	return n.val;
	}else{
	return Integer.MIN_VALUE;
	}
	}
	//time complexity:O(1)
	public int min(){
	if(first != null)
	return first.val;
	else
	return Integer.MAX_VALUE;
	}
	public boolean empty(){
	if(top == null)
	return true;
	else
	return false;
	}
}
class Stack2{
	private Node top;
	class Node{
	int val;
	int min;
	Node next;
	public Node(int val, int min){
	this.val = val;
	this.min = min;
	this.next = null;
	}
	}
	public void push(int val){
	if(top != null){
	Node n = new Node(val, val < top.min ? val : top.min);
	n.next = top;
	top = n;
	}else{
	top = new Node(val, val);
	}	
	}
	public int pop(){
	if(top != null){
	Node n = top;
	top = top.next;
	return n.val;
	}else{
	return Integer.MIN_VALUE;
	}
	}
	public int min(){
	if(top != null)
	return top.min;	
	else
	return Integer.MAX_VALUE;
	}
	public boolean empty(){
	if(top == null)
	return true;
	else
	return false;
	}
}
class Stack3{
	private Node top = null;
	private Stack s = new Stack();
	class Node{
	int val;
	Node next;
	public Node(int val){
	this.val = val;
	this.next = null;
	}
	}
	public void push(int val){
	if(top != null){
	Node n = new Node(val);
	n.next = top;
	top = n;
	
	if(s.peek() >= val)
	s.push(val);	
	}else{
	top = new Node(val);
	s.push(val);
	}
	}
	public int pop(){
	if(top != null){
	Node n = top;
	top = top.next;
	if(n.val == s.peek())
	s.pop();
	return n.val;
	}else
	return Integer.MIN_VALUE;
	
	}
	public int min(){
	if(top == null)
	return Integer.MAX_VALUE;
	else
	return s.peek();
	}
	public boolean empty(){
	if(top == null)
	return true;
	else
	return false;
	}
}
public class Solution{
	public static void main(String[] args){
	int[] A = {
	23, 11	, 12, 34, 10, 12, 7, 45, 21,
	12, 6, 12, 5, 85, 4, 3, 2, 1
	};
	//test for Stack1
	Stack1 stack1 = new Stack1();
	for(int i=0;i < A.length;i++){
	stack1.push(A[i]);
	}
	while(!stack1.empty()){
	System.out.print(stack1.pop() + "[" +
	stack1.min() + "]" + " ");
	}
	System.out.println();
	//test for Stack2
	Stack2 stack2 = new Stack2();
	for(int i=0;i < A.length;i++){
	stack2.push(A[i]);
	}
	while(!stack2.empty()){
	System.out.print(stack2.pop() + "[" +
	stack2.min() + "]" + " ");
	}
	System.out.println();
	//test for Stack3
	Stack3 stack3 = new Stack3();
	for(int i=0;i < A.length;i++){
	stack3.push(A[i]);
	}
	while(!stack3.empty()){
	System.out.print(stack3.pop() + "[" +
	stack3.min() + "]" + " ");
	}
	System.out.println();

	}
}