[Daily]用一个栈实现另一个栈的排序

【问题】

• 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

【分析】

• 利用栈访问的特性（FILO），将每一个数放在正确的位置，直到stack栈为空，最后将help一并压入stack栈中。
• help应为所要求有序数列的逆序（因为最后要压入stack中）
• 算法步骤解析：
  • cur ：int 辅助变量
  • help : stack 辅助栈
  • 如果cur小于或等于help的栈顶元素，则将cur直接压入help；
  • 如果cur大于help的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。
  • 一直执行以上操作，直到stack中的全部元素都压入到help。最后将help中的所有元素逐一压入stack，即完成排序。

【源代码】

• 实现语言：C++
• 源代码

/*用一个栈实现另一个栈的排序*/ 
#include<iostream>
#include<stack>
using namespace std;void SortByStack(stack<int> &pstack)
{stack<int> temp;  //临时整型栈 int cur;          //临时int类型变量 while(!pstack.empty()){cur=pstack.top();pstack.pop();  //获取栈顶元素并出栈while(!temp.empty()&&temp.top()<cur){pstack.push(temp.top()); temp.pop();}temp.push(cur);}while(!temp.empty()){pstack.push(temp.top());temp.pop();}
}int main()
{stack<int> p_Stack;p_Stack.push(6);p_Stack.push(7);p_Stack.push(5);p_Stack.push(3);p_Stack.push(8);p_Stack.push(6);SortByStack(p_Stack);cout<<"排序之后："<<endl; while(!p_Stack.empty()){cout<<p_Stack.top()<<" ";p_Stack.pop();}
}

• 控制台截图