个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 28 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++使用一个栈实现另一个栈的排序算法示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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

题目:

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

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

算法C++代码:

?
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
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);
     }
   }
};

测试用例程序:

?
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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" );
}

运行结果:

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

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

最后此篇关于C++使用一个栈实现另一个栈的排序算法示例的文章就讲到这里了,如果你想了解更多关于C++使用一个栈实现另一个栈的排序算法示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

28 4 0
文章推荐： 如何将numpy二维数组中的np.nan值替换为指定的值
文章推荐： 使用numpy nonzero 找出非0元素
文章推荐： Python机器学习之KNN近邻算法
文章推荐： 如何获取numpy的第一个非0元素索引
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com