import java.util.Stack;

class ClassExercise10 {

	public static void main(String[] args) {
		Stack s = new Stack();
		s.push("a");
		s.push("b");
		s.push("a");
		s.push("c");
		s.push("b");
		
		removeDuplicates(s);
		System.out.println("After duplicates are removed: ");
		while(!s.empty())
			System.out.println((String) s.pop());
		
		S s1 = new S();
		s1.push("c");
		s1.push("a");
		s1.push("g");
		s1.push("b");
		s1.push("a");

		System.out.println("\nAfter sorting the stack: ");
		s1.selectionSort();
		while(!s1.empty())
			System.out.println((String) s1.pop());

	}

	// inefficient method
	// you can implement it more efficiently  
	// tip: first sort the Stack!
	public static void removeDuplicates(Stack list){
		Stack temp1 = new Stack(), temp2 = new Stack();
		while(!list.empty()){
			Object o = list.pop();
			while(!list.empty()){
				Object o1 = list.pop();
				if(!o.equals(o1))
					temp2.add(o1);
			}
			temp1.add(o);

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

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

	public void push(Comparable o){
		if(size > elements.length * 2 / 3)
			enlarge();
		
		elements[size++] = 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;
	}
	
	public void selectionSort(){
		S temp1 = new S(), temp2 = new S();
		// 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());
		}
	}
	
	
	
}