cc150_3.6

gistfile1.java

package cc150;
/*
 * 3.6 Write a program to sort a stack in ascending order (with biggest items on top).
You may use at most one additional stack to hold items, but you may not copy
the elements into any other data structure (such as an array). The stack supports
the following operations: push, pop, peek, and isEmpty.

Algorithm:
 set  two stacks  mainStack and  helpStack
  the helpStack  store the  data  that bigger then pushed data;
  push  function :
     
   1. if the pushed data  > mainStack.top.data 
         compare it with helpStack
             repeat 
               if  pushed data > helpstack.top
                    pop it from helpstak and push it to  mainstak
            until pushed data >=   helpstack.top
  2.  if the pushed data < manistack.top.data
     repeat pop mainstack top and push it to  helpstack 
     
  3.   finally push the data to the  mainstack 
  
 pop function 
	 1.if helpstack  top is not  null repeat to   
	    pop the data from helpstack  one by one to main stackl until 
	 2.pop the top;
 peak function  
    similar to pop
 isEmpty  rturn  main.top ==null and help.top ==null;    
 */
public class AscendStack_3_6 {

	public static void main(String[] args) {
		AscendStack testStack = new AscendStack();
		testStack.push(15);
		testStack.push(25);
		testStack.push(2);
		testStack.push(5);
		testStack.push(67);
		testStack.push(98);
		testStack.push(25);
		while(!testStack.isEmpty()){
			System.out.println(testStack.peak());
			testStack.pop();
		}
	}

}

class AscendStack extends BaseStack{
	BaseStack helpStack;
	
	public AscendStack(){
		super();
	    helpStack = new BaseStack();
	}
	public void push (int data){
		if(super.isEmpty()){
			super.push(data);
		}
		if(data < super.peek()){
			while(!super.isEmpty() && data<super.peek() )
			 {
				helpStack.push(super.pop().data);
			} 
			
		}
		else if(data > super.peek()){
			while(!helpStack.isEmpty() && helpStack.peek()<data ){
				super.push(helpStack.pop().data);
			}
		}
		super.push(data);
	}
	public AscendNode pop(){
		while(!helpStack.isEmpty()){
			super.push(helpStack.pop().data);
		}
		return super.pop();
		
	}
	public int peak(){
		while(!helpStack.isEmpty()){
			super.push(helpStack.pop().data);
		}
		return super.peek();
	}
	public boolean isEmpty(){
		return super.isEmpty() && helpStack.isEmpty();
	}
}
class AscendNode{
	int data;
	AscendNode next;
	public AscendNode(int data){
		this.data = data;
	}
}
class BaseStack{
	AscendNode top;
	
	public BaseStack(){
		top =null;
	}
	public  void push(int data){
		AscendNode newNode = new AscendNode(data);
		if(top !=null)
			newNode.next= top;
		top = newNode;
	}
	public AscendNode pop(){
		if(top!=null){
			AscendNode popdata = top;
			top = top.next;
			return popdata;
		}
		return null;
	}
	public int peek(){
		if(top!=null){
			return top.data;
		}
		return Integer.MIN_VALUE;
	}
	public boolean isEmpty(){
		return top==null;
	}
	
}