스택 뒤집기 (Reverse stack)

스택(stack)이 주어졌을 때, 명시적인 별도의 스택 및 데이터 저장소를 사용하지 않고 스택 내부의 저장 순서를 거꾸로 만들어 보자.
또 다른 스택을 사용할 수 있다면, 원래의 스택에서 pop하여 새로 생성한 스택에 push하면 원하는 결과를 얻을 수 있다. 이 원리를 이용하되 명시적인 데이터 저장소를 사용하지 않는 방법을 고안하면 된다.
답은 간단한데, 함수 호출이 스택을 사용한다는 점에 착안하여 함수의 재귀호출을 사용하여 구현하면 되겠다.

func main() {

    data := []int{1, 2, 3, 4, 5}

    S := stack.Stack{}

    for _, item := range data {

        S.Push(item)

    }

    S.Reverse()

    for !S.IsEmpty() {

        item := S.Top().(int)

        S.Pop()

        fmt.Println(item)

    }

}

func (s *Stack) InsertAtBottom(item interface{}) {

    if s.IsEmpty() {

        s.Push(item)

        return

    }

    t := s.Top()

    s.Pop()

    s.InsertAtBottom(item)

    s.Push(t)

}

func (s *Stack) Reverse() {

    if s.IsEmpty() {

        return

    }

    t := s.Top()

    s.Pop()

    s.Reverse()

    s.InsertAtBottom(t)

}