[Stack] 스택 정렬

스택정렬

입력받은 스택이 있습니다.
새로운 스택을 생성하여 정렬을 진행합니다.
정렬된 스택이 결과로 출력됩니다.

스택정렬 구현

• while(!stack.isEmpty())
  • stack.top 인스턴스 변수의 값이 -1(=empty) 아니라면 반복해서 실행합니다.
• 조건 1. if(!newStack.isEmpty() && value >= newStack.top())
  • newStack이 비어있지 않고 newStack.top 값이 stack.top(=value) 보다 큰 경우, newStack에 stack의 top(=value)을 push 합니다.
• 조건 2. else
  • while (!newStack.isEmpty() && newStack.top() > value)
    • newStack이 비어있지 않고 newStack.top이 stack.top(=value) 보다 크다면 반복해서 stack에 newStack의 top을 push 합니다.
  • while문이 종료되면 newStack에 stack.top(=value) 값을 push 합니다.

  public void sortedStack(Stack stack){

    Stack<Integer> newStack = new Stack<>(stack.getMaxSize());

    while (!stack.isEmpty()){
      int value = (int) stack.pop();

      if(!newStack.isEmpty() && value >= newStack.top()){
        newStack.push(value);
      } else {
        while (!newStack.isEmpty() && newStack.top() > value){
          stack.push(newStack.pop());
        }
        newStack.push(value);
      }
    }
  }

실행결과

  @Test
  public void sortedStack(){
    Stack<Integer> stack = new Stack<>(6);
    stack.push(1);
    stack.push(100);
    stack.push(10);
    stack.push(1000);
    stack.push(2);
    stack.push(200);
    sortedStack(stack);

    String res = "";
    while (!stack.isEmpty()){
      res+=stack.pop() + " ";
    }

    Assert.assertEquals("1 2 10 100 200 1000 ", res);
  }