【題目】
一個(gè)棧中元素的類型為整型女淑，現(xiàn)在想將該棧從頂?shù)降装磸拇蟮叫〉捻樞蚺判蛱缚觯辉S申請(qǐng)一個(gè)棧陷虎。除此之外，可以申請(qǐng)新的變量鲫竞，但不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)。如何完成排序逼蒙？
??一種實(shí)現(xiàn)方式从绘，在排序過(guò)程中需要臨時(shí)增加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);
}
另外一種無(wú)須增加stack的思路是是牢，如果tmpStack不為空僵井，就把stack的top拿出比較，遍歷tmpStack驳棱，只要tmpStack的top元素比stack的top小批什，那就push回stack中，直到遇到一個(gè)元素大于stack的那個(gè)top就停止社搅，然后把那個(gè)top值push到tmpStack渊季。這樣到最后，再把tmpStack push回 stack就是從大到小的順序了罚渐。
??代碼也非常簡(jiǎn)潔：
#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();
}
}
