设计一个算法，将一个栈中的元素排序
需积分: 9 176 浏览量
2022-07-25
16:57:56
上传
评论
收藏 617KB PDF 举报
——
目录
问题重述
分析
题目延伸
1 问题
设计一个算法，将一个栈中的元素排序，要求最多使用一个辅助栈及少量变量，并分析算法的时间性能。
2 分析
类似汉诺塔问题，元素需要在原始栈和辅助栈之间来回出栈、入栈。首先将原始栈中元素出栈，然后条件性压入辅
助栈，当新出栈元素不满足压入辅助栈条件时，可以考虑将辅助栈中元素出栈，重新压入原始栈，以此完成辅助栈中
元素顺序的调换。
我们将要排序的栈记为stack，申请的辅助栈记为stemp。在stack上执行pop操作，弹出的元素记为cur
如果cur小于或等于stemp的栈顶元素，则将cur直接压入stemp；
如果cur大于stemp的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于stemp的栈顶
元素，再将cur压入stemp。
一直执行以上操作，直到stack中的全部元素都压入到stemp。最后将stemp中的所有元素逐一压入stack，即完成
排序。
代码实现：
2n1zyQu3gR
class Solution
{
public:
//借助一个临时栈排序源栈
static void sortStackByStack(stack<int>& s)
{
1
2
3
4
5
6
C++
将一个栈中的元素排序
评论0