100-66

제목: 한 창고를 차례로 뒤집다.예를 들어 입력 창고 {1, 2, 3, 4, 5}, 1은 창고 꼭대기에 있습니다.뒤바뀐 창고는 {5, 4, 3, 2, 1}이고 5곳은 창고 꼭대기에 있다.
사고방식: 언뜻 이 제목을 보자마자 첫 번째 반응은 창고에 있는 모든 요소를 하나하나 팝업해서 한 그룹에 넣고 그 다음에 그룹에서 모든 요소를 뒤바꾸어 마지막에 그룹의 모든 요소를 하나하나push로 창고에 넣는 것이다.이때 창고도 뒤바뀌었다.하나의 수조를 뒤바꾸는 것은 매우 쉬운 일이다.그러나 이런 사고방식은 길이가 O(n)인 그룹을 분배하는 것을 보여야 하고 귀속의 특성을 충분히 이용하지 못한다.
우리는 어떻게 귀속할지 다시 한번 고려해 보자.우리는 창고 {1, 2, 3, 4, 5}를 두 부분으로 구성한다. 창고 꼭대기 원소 1과 나머지 부분 {2, 3, 4, 5}이다.만약에 우리가 {2, 3, 4, 5}를 뒤집어서 {5, 4, 3, 2}로 바꾸고 원래의 창고 꼭대기 원소 1을 밑에 놓을 수 있다면 전체 창고는 뒤집어져서 {5, 4, 3, 2, 1}로 변한다.
다음에 우리는 두 가지 일을 고려해야 한다. 첫째, 어떻게 {2, 3, 4, 5}를 거꾸로 해서 {5, 4, 3, 2}로 바꿀 것인가.우리는 {2, 3, 4, 5}를 두 부분으로 구성된다고 보기만 하면 창고 꼭대기 원소 2와 나머지 부분 {3, 4, 5}이다.우리는 {3, 4, 5}를 먼저 뒤집어서 {5, 4, 3}로 만든 다음에 이전의 창고 꼭대기 원소 2를 맨 밑에 놓으면 {5, 4, 3, 2}가 된다.
{3, 4, 5}를 어떻게 거꾸로 하는지... 많은 독자들이 이것이 귀속이라고 생각할 것이다.즉, 매번 창고를 뒤집으려고 시도할 때마다 현재 창고 꼭대기 원소가 팝업되고 나머지 원소로 구성된 창고를 뒤집고 마지막으로 이전의 창고 꼭대기 원소를 나머지 원소로 구성된 창고의 밑에 놓는다.귀속이 끝난 조건은 남은 창고가 이미 비어 있다는 것이다.
하해도 대신의 코드를 붙여라.

// Reverse a stack recursively in three steps:
// 1. Pop the top element
// 2. Reverse the remaining stack
// 3. Add the top element to the bottom of the remaining stack
template<typename T> void ReverseStack(std::stack<T>& stack)
{
    if(!stack.empty())
    {
        T top = stack.top();
        stack.pop();
        ReverseStack(stack);
        AddToStackBottom(stack, top);
    }
}

우리가 고려해야 할 또 다른 일은 하나의 요소 e를 창고의 밑에 놓는 방법, 즉AddToStackBottom을 실현하는 방법이다.이 일은 어렵지 않다. 창고에 있는 원래의 요소를 하나하나 팝업하기만 하면 된다.창고가 비어 있을 때push 요소 e가 창고에 들어갑니다. 창고의 밑에 있습니다.그리고 창고에 있는 원소를 팝의 반대 순서에 따라 하나하나push로 창고에 넣는다.
우리가push 요소 e에 있기 전에 창고에 있는 모든 요소를 팝업했습니다. 나중에 그들을 다시 push로 돌려보낼 수 있도록 저장해야 합니다.우리는 당연히 하나의 수조를 개척해서 할 수 있지만, 이것은 필요없다.우리는 귀속으로 이 일을 할 수 있기 때문에, 귀속 자체가 창고 구조이다.우리는 귀속된 창고로 이 원소들을 저장할 수 있다.다시 붙이기:

// Add an element to the bottom of a stack:
template<typename T> void AddToStackBottom(std::stack<T>& stack, T t)
{
    if(stack.empty())
    {
        stack.push(t);
    }
    else
    {
        T top = stack.top();
        stack.pop();
        AddToStackBottom(stack, t);
        stack.push(top);
    }
}