题面

用一个栈实现另外一个栈的顶到底降序排序

要求:不能使用额外的数据结构,但可以使用新的变量。

思路(给定栈s, 辅助栈help)

1. 遍历给定栈(出栈),栈顶出栈cur,与help栈顶比较,如果大于辅助栈顶元素值,那么辅助栈栈顶元素出栈至s栈,直到help栈顶元素值<=cur

2. help压入cur

2. s栈空时,排序结束,help栈元素出栈至s栈,排序结束。

(如果要求升序,那么只要将大小比较符号改反即可)

 1 void sort(stack<int> &s)
 2 {
 3     stack<int> help;
 4     while (!s.empty())
 5     {
 6         int cur = s.top();
 7         s.pop();
 8         while (!help.empty() && cur > help.top())//如果要求从顶到底升序,改成 < 即可
 9         {
10             int tmp = help.top();
11             s.push(tmp);
12             help.pop();
13         }
14         help.push(cur);
15     }
16     while (!help.empty())
17     {
18         int a = help.top();
19         s.push(a);
20         help.pop();
21     }
22 }