cc150_3_2

gistfile1.java

/*
 * 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.
* Algorithm:
* use a stack to store the  minum value of the   stack,   
* if push  data  < minstack.top   then push the data to minstack
* if pop() =  minstack.top  then pop  data from minstack
* 

 */
public class StackWithMin_3_2 {

	public static void main(String[] args) {
		StackWithMin testStack = new StackWithMin();
		testStack.push(5);
		testStack.push(3);
		System.out.println("the minum of stack is " +testStack.minum() );
		testStack.push(-1);
		testStack.push(6);
		System.out.println("the minum of stack is " +testStack.minum() );
		testStack.pop();
		testStack.pop();
		System.out.println("the minum of stack is " +testStack.minum() );
		 

	}

}

class StackWithMin{
	StackNode top;
	StackWithMin minStack;
	public StackWithMin (){
		top = null;
	}
	public void  push(int data){
		StackNode  newNode = new StackNode(data);
		if (top  == null){
			top = newNode;
			minStack = new StackWithMin();
			minStack.top =newNode;
		}
		else{
			int min = minStack.top.data;
			if(data<min){
				StackNode  newMinNode = new StackNode(data);
				newMinNode.next = minStack.top;
				minStack.top = newMinNode;
			}
			newNode.next=top;
			top = newNode;
		}
	}
	public  int pop(){
		if(top !=null){
			StackNode  popNode = top;
			top = top.next;
			if(popNode.data == minStack.top.data){
				minStack.top= minStack.top.next;
			}
			return popNode.data;
		}
		return -1;
	}
	public int minum(){
		return minStack.top.data;
	}
}

class StackNode{
	int data;
	StackNode next;
	public StackNode(int data){
		this.data = data;
	}
	
}