【题目】
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
一种实现方式，在排序过程中需要临时增加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();
}
}
