用一个栈实现另一个栈的排序

电玩女神 2022-07-24 09:22 191阅读 0赞

## 用一个栈实现另一个栈的排序 – 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