문제 // 자료구조 // 스택(Stack) // StackSort // toJava

/**
 * [스택정렬]
 *  가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성
 *  추가적으로 하나 정도의 스택은 사용해도 괜찮지만
 *  스택에 보관된 요소를 배열등의 다른 자료구조로 복사할 수 없다
 *  스택 push pop peek isEmpty 를 제공
 *
 * [풀이]
 *  => get()을 제공하면 탐색이 가능
 *  => 지그재그식 처리 큰값이라면 넘기고 작은값이라면 다시 넘어옴
 * */

public class Q05 {

    /* Main */
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(13);
        stack.push(12);
        stack.push(11);
        stack.push(10);
        stack.push(15);
        stack.push(19);
        stack.push(19);
        stack.push(1);
        stack.push(6);
        sortstack(stack);
    }

    /* Sort Stack - 지그재그식 풀이 */
    public static void sortstack(Stack<Integer> stack) {
        Stack<Integer> temp = new Stack();

        // == 스택이 0이 될 때까지 모두 넘어갈 때까지 반복 ==
        while(stack.size() != 0) {
            int top = stack.pop();
            while (true) {
                if(temp.size() == 0) {
                    // == 값이 없음 ==
                    temp.push(top);
                    break;
                }
                else if(top > temp.peek()) {
                    // == 반대로 넘어김 (아래에 작은값이있음) ==
                    stack.push(temp.pop());
                }
                else {
                    // == 정렬에 맞음 (아래에 큰값이있음) ==
                    temp.push(top);
                    break;
                }
            }
        }

        // @Test
        for (int i = 0; i < temp.size(); i++) {
            System.out.printf(temp.get(i) + " ");
        }
    }
}