C++使用一个栈实现另一个栈的排序算法示例

概述本文实例讲述了C++用一个栈实现另一个栈的排序算法。分享给大家供大家参考，具体如下：

本文实例讲述了C++用一个栈实现另一个栈的排序算法。分享给大家供大家参考，具体如下：

题目：

一个栈中元素类型为整型，现在想将该栈从顶到底按从小到大的顺序排序，只许申请一个辅助栈。

除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

算法C++代码：

class Solution{public:  //借助一个临时栈排序源栈  static voID sortStackByStack(stack<int>& s)  {    stack<int>* stemp = new stack<int>;    while (!s.empty())    {      int cur = s.top();      s.pop();      //当源栈中栈顶元素大于临时栈栈顶元素时，将临时栈中栈顶元素放回源栈      //保证临时栈中元素自底向上从大到小      while (!stemp->empty() && cur > stemp->top())      {        int temp = stemp->top();        stemp->pop();        s.push(temp);      }      stemp->push(cur);    }    //将临时栈中的元素从栈顶依次放入源栈中    while (!stemp->empty())    {      int x = stemp->top();      stemp->pop();      s.push(x);    }  }};

测试用例程序：

#include <iostream>#include <stack>using namespace std;class Solution{public:  //借助一个临时栈排序源栈  static voID sortStackByStack(stack<int>& s)  {    stack<int>* stemp = new stack<int>;    while (!s.empty())    {      int cur = s.top();      s.pop();      //当源栈中栈顶元素大于临时栈栈顶元素时，将临时栈中栈顶元素放回源栈      //保证临时栈中元素自底向上从大到小      while (!stemp->empty() && cur > stemp->top())      {        int temp = stemp->top();        stemp->pop();        s.push(temp);      }      stemp->push(cur);    }    //将临时栈中的元素从栈顶依次放入源栈中    while (!stemp->empty())    {      int x = stemp->top();      stemp->pop();      s.push(x);    }  }};voID printStack(stack<int> s){  while (!s.empty())  {    cout << s.top() << " ";    s.pop();  }  cout << endl;}int main(){  stack<int>* s = new stack<int>;  s->push(5);  s->push(7);  s->push(6);  s->push(8);  s->push(4);  s->push(9);  s->push(2);  cout << "排序前的栈：" << endl;  printStack(*s);  Solution::sortStackByStack(*s);  cout << "排序后的栈：" << endl;  printStack(*s);  system("pasue");}

运行结果：

排序前的栈：2 9 4 8 6 7 5排序后的栈：9 8 7 6 5 4 2

希望本文所述对大家C++程序设计有所帮助。

总结

以上是内存溢出为你收集整理的C++使用一个栈实现另一个栈的排序算法示例全部内容，希望文章能够帮你解决C++使用一个栈实现另一个栈的排序算法示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。