链接：https://www.nowcoder.com/questionTerminal/d0d0cddc1489476da6b782a6301e7dec
来源：牛客网
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[]numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到最后一个元素。
测试样例：
[1,2,3,4,5]
返回：[5,4,3,2,1]
思路：一个临时栈，一个排序栈，如果排序栈中的值小于当前临时栈顶值，就将栈顶值插入其合适位置。
class TwoStacks {
public:
vector<int> twoStacksSort(vector<int> numbers) {
// write code here
vector<int> ret;
if(numbers.size() <= 1)
return numbers;
while(numbers.size() > 0)
{
if(ret.empty())
{
ret.push_back(numbers.back());
numbers.pop_back();
}
int tmp = numbers.back();
numbers.pop_back();
while(!ret.empty() && tmp > ret.back())
{
numbers.push_back(ret.back());
ret.pop_back();
}
ret.push_back(tmp);
}
return ret;
}
};
另一个思路：利用双栈排序。
classTwoStacks{
public:
vector twoStacksSort(vector<int> numbers)
{
stack<int> sta;
for(vector<int>::reverse_iterator riter=numbers.rbegin();riter!=numbers.rend();riter++)
sta.push(*riter);
StackSort(sta);
vector<int> res;
while(!sta.empty())
{
res.push_back(sta.top());
sta.pop();
}
return res;
}
void StackSort(stack<int> &sta)
{
stack<int> help;
while(!sta.empty())
{
int res=sta.top();
sta.pop();
if(help.empty() || res<=help.top())
help.push(res);
else
{
while(!help.empty()&&res>help.top())
{
sta.push(help.top());
help.pop();
}
help.push(res);
}
}
while(!help.empty())
{
sta.push(help.top());
help.pop();
}
}
};
