用一个栈实现另一个栈的排序

【题目】
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

  一种实现方式，在排序过程中需要临时增加stack的大小：

void sortStack(stack<T>& stack) {
    if (stack.empty())
        return;
    std::stack<T> tmpStack;
    
    T min = stack.top();
    stack.pop();
    int size = stack.size();
    
    for (int i = size; i >= 0;--i) {
        for (int j = 0; j < i; ++j) {
            T curVal = stack.top();
            stack.pop();
            if (curVal < min) {
                tmpStack.push(min);
                min = curVal;
            }
            else
                tmpStack.push(curVal);
        }
        stack.push(min);
        for (int j = 0; j < i; ++j) {
            stack.push(tmpStack.top());
            tmpStack.pop();
        }
        min = stack.top();
        stack.pop();
    }
    stack.push(min);
}

另外一种无须增加stack的思路是，如果tmpStack不为空，就把stack的top拿出比较，遍历tmpStack，只要tmpStack的top元素比stack的top小，那就push回stack中，直到遇到一个元素大于stack的那个top就停止，然后把那个top值push到tmpStack。这样到最后，再把tmpStack push回 stack就是从大到小的顺序了。
  代码也非常简洁：

#include <stack>

using namespace std;

template <class T>
void sortStack(stack<T>& stack) {
    std::stack<T> tmpStack;
    while (!stack.empty()) {
        T curVal = stack.top();
        stack.pop();
        while (!tmpStack.empty() && tmpStack.top() < curVal) {      
                stack.push(tmpStack.top());
                tmpStack.pop();
        }
        tmpStack.push(curVal);
    }
    while (!tmpStack.empty()) {
        stack.push(tmpStack.top());
        tmpStack.pop();
    }
}