【题目】

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，

只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。

如何完成排序？

【题解】

将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。

·如果cur小于或等于help的栈顶元素，则将cur直接压入help；

·如果cur大于help的栈顶元素，则将help的元素逐一弹出，

逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。

一直执行以上操作，直到stack中的全部元素都压入到help。

最后将help中的所有元素逐一压入stack，即完成排序。

【代码】

1 #pragma once 2 #include 
     
       3 #include 
      
        4  5 using namespace std; 6  7 //一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序， 8 //只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。 9 //如何完成排序？10 //11 //我的想法就是有n个数，那就倒腾n次，每次找到一个最小值12 //将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。13 //·如果cur小于或等于help的栈顶元素，则将cur直接压入help；14 //·如果cur大于help的栈顶元素，则将help的元素逐一弹出，15 //    逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。16 //一直执行以上操作，直到stack中的全部元素都压入到help。17 //    最后将help中的所有元素逐一压入stack，即完成排序。18 19 20 21 void stackSort(stack
       
        &s)22 {23     if (s.size() < 2)24         return;25     stack
        
         h;26     while (!s.empty())27     {28         int a = s.top();29         s.pop();30         while (!h.empty() && a > h.top())//当原栈顶元素大于h栈顶元素，将h栈数据全部弹出31         {32             s.push(h.top());33             h.pop();34         }35         h.push(a);36     }37     while (!h.empty())//排好的数据返回给原栈38     {39         s.push(h.top());40         h.pop();41     }42 }43 44 45 void printStack(stack
         
          s)46 {47     while (!s.empty())48     {49         cout << s.top() << " ";50         s.pop();51     }52     cout << endl;53 }54 55 void Test()56 {57     stack
          
           s;58 s.push(5);59 s.push(2);60 s.push(3);61 s.push(4);62 s.push(1);63 printStack(s);64 stackSort(s);65 printStack(s);66 }