// CIS 3023 Fall 2008 - Data Structures 1 
// Stack 
// Problem #3, #4, #5

public class MyStack {
	private Comparable [] elements; 
	private int size=0;
	
	public MyStack(){
		elements = new Comparable[10];
	}
	
	public MyStack(int size){
		elements = new Comparable[size];
	}

	public void push(Object o){
		if(size > elements.length * 2 / 3)
			enlarge();
		
		elements[size++] = (Comparable)o;
	}

	public Comparable pop(){
		size--;
		return elements[size];
	}
	
	public int search(Comparable o){
		for(int i=size-1; i>=0; i--){
			if(o.compareTo(elements[i]) == 0)
				return size-i;
		}
		return -1;
	}
	
	public boolean empty(){
		return (size == 0);
	}
	
	public void enlarge(){
		Comparable [] c = new Comparable[elements.length * 2];
		for(int i=0; i< size; i++){
			c[i] = elements[i];
		}
		elements = c;
	}
	
	public void compress(){
		Comparable [] c = new Comparable[size];
		for(int i=0; i< size; i++){
			c[i] = elements[i];
		}
		elements = c;
	}
	
	// remove Duplicates
	public void removeDuplicates(){
		MyStack temp1 = new MyStack(), temp2 = new MyStack();
		while(!empty()){
			Object o = pop();
			while(!empty()){
				Object o1 = pop();
				if(!o.equals(o1))
					temp2.push(o1);
			}
			temp1.push(o);

			while(!temp2.empty()){
				push(temp2.pop());
			}
		}
		while(!temp1.empty()){
			push(temp1.pop());
		}
	}

	
	public void selectionSort(){
		MyStack temp1 = new MyStack(), temp2 = new MyStack();
		// temp1 is used to store sorted elements
		// temp2 is used to store the elements temporarily in each iteration
		
		while(!empty()){
			Comparable currentMinimum = pop();
			
			while(!empty()){
				Comparable current = pop();
				if(current.compareTo(currentMinimum) < 0){
					temp2.push(currentMinimum); 
					currentMinimum = current;
				}
				else
					temp2.push(current);
			}
			temp1.push(currentMinimum);

			while(!temp2.empty()){
				push(temp2.pop());
			}
		}
		
		while(!temp1.empty()){
			push(temp1.pop());
		}
	}
	

}