双栈排序

编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构（如数组）。

该栈支持如下操作：push， pop， peek，和isEmpty

如果可以支持两个栈，我们可以每一次遍历栈1，将最小的元素放入栈2，把栈3作为搜索时的缓冲区

但是这里只能使用一个额外栈，那是不是就没有办法了呢？不是的

我们不需要反复搜索栈1来依次获得最小值，假设栈s是要排序的栈，栈r是已排序的栈

s = [5,10,7]

r = [12,8 ,3,1]

栈顶元素5在r中的正确位置应该是3的上面，我们可以先弹出5，反正5是无论如何都要从s压入r的，然后将12和8压入栈s，然后将5压入栈r

注意这是12和8没有在r中了，但是只要我们不改变它们在s中的顺序，重复上面的步骤，12和8一次从s弹出再压入r还是在5的上面，r依然是有序的。

时间复杂度为O（n^2）,空间复杂度O（n）。
 vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
   
         vector<int> vec;
while(!numbers.empty())
{
int temp=numbers.front();
numbers.erase(numbers.begin());
int count=0;
while(vec.size()!=0 && vec.front()>temp)
{
int t=vec.front();
vec.erase(vec.begin());
numbers.insert(numbers.begin(),t);
count++;
}
vec.insert(vec.begin(),temp);
while(count--)
{
int t=numbers.front();
numbers.erase(numbers.begin());
vec.insert(vec.begin(),t);
}
}
return vec;
    }