栈的面试题---对栈进行升序排列

原文链接：https://blog.csdn.net/qq_37964547/article/details/80701630

1、题目描述
请编写一个程序，按升序对栈进行排序，要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
vector数组numbers中的第一个元素就是栈顶元素，升序排列，即栈顶元素最大

2、解题思路
看到这个题，因为可以申请一个栈用来存放临时数据，所以我们可以这样想：
由于栈先进后出的特性，先将原来栈中的数据存放到临时数据栈中，并且保证临时栈中的数据是降序排列的，这一过程完成之后，再将临时数据栈中的元素依次push到返回栈中即可。
具体实现步骤：
（1）申请一个数据栈s用来存放numbers中的数据，再申请一个临时栈tmp用来存放临时数据
（2）比较s栈弹出的栈顶元素top与tmp的栈顶元素，并进行相应的操作，以确保tmp栈中的数据是降序的，具体比较过程如下：
当s栈不为空时：

条件 具体操作
若tmp栈为空或者top<=tmp.top（） 就将top元素push到tmp栈中
若tmp栈不为空并且top>tmp.top（） 将tmp中比top小的元素都push到s栈中，最后再将top元素push到tmp栈中
（3）此时tmp栈中的栈顶元素为最小值，将tmp栈中的元素依次弹出到s栈中，再将s栈中的元素依次弹出并保存到一个vector数组中。
操作演示图：

3、代码实现：
class TwoStacks {
public:
vector<int> twoStacksSort(vector<int> numbers) {
// write code here
int size=numbers.size();
stack<int>s;
stack<int>tmp;
vector<int> res;
for(int i=size-1;i>=0;i--)
s.push(numbers[i]);
while(!s.empty())
{
int top=s.top();
s.pop();
if(tmp.empty()||top<=tmp.top())
tmp.push(top);
else{
while(!tmp.empty()&&top>tmp.top())
{
s.push(tmp.top());
tmp.pop();
}
tmp.push(top);
}
}
while(!tmp.empty())
{
s.push(tmp.top());
tmp.pop();
}
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Shining-LY
关注

————————————————
版权声明：本文为CSDN博主「Shining-LY」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37964547/article/details/80701630