cc150_3_6.java

import java.util.Stack;


public class PeakStack {
	
	Stack<Integer> origin;
	Stack<Integer> peak;
	int top_o;
	int top_p;
	
	public PeakStack(){
		origin = new Stack();
		peak = new Stack();
		top_o = -100000;
		top_p = -100000;
		
	}
	
	public void push(Integer item){
		
		if(item >= top_p || (peak.empty() && origin.empty())){
			origin.push(item);
			peak.push(item);
			top_p = item;
			

			return;
		}
		
		if(item < top_p){
			int cnt = 0;
			int temp = (int) peak.pop();
			while(temp > item && !peak.empty()){
				origin.push(temp);
				cnt ++;
				temp = (int) peak.pop();
			}
			
			peak.push(temp > item?temp:item);
			peak.push(item > temp?item:temp);
			while(cnt > 0){
				peak.push(origin.pop());
				cnt --;
			}
			origin.push(item);		
		}
	}
	
	public int pop(){
		int temp = origin.pop();
		int cnt = 0;
		int p_temp = peak.pop();
		while(temp != p_temp){
			origin.push(p_temp);
			cnt ++;
			p_temp = peak.pop();
		}
		while(cnt > 0 ){
			peak.push(origin.pop());
			cnt --;
		}
		
		return temp;
	}
	
	public int peakpop(){
		int p_temp = peak.pop();
		int cnt = 0;
		int temp = origin.pop();
		while(temp != p_temp){
			peak.push(temp);
			cnt ++;
			temp = origin.pop();
		}
		while(cnt > 0 ){
			origin.push(peak.pop());
			cnt --;
		}
		
		return p_temp;
	}
	
	public static void main(String[] args){
		PeakStack test = new PeakStack();
		test.push(2);
		test.push(1);
		test.push(5);
		test.push(7);
		test.push(4);
		

		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.peakpop());
		
	}
}