20240620 算法:利用额外栈实现逆序

题目

题目描述：设计一个算法，将栈中的元素按升序(最大的在top)排列。可另外借用一个栈来实现。

想法

• 感觉就是两个栈栈顶之间的判断和进出

• 相等情况肯定不用处理，原栈大于辅栈，辅栈大于原栈主要就是这两种情况以及如何进行调整的问题

我最主要的问题：如果只有一个栈的话，在遇到违反规则的成员的时候怎样进行调整

申请临时变量算是违反规则吗？

代码实现

stack<int> sort(stack<int> num,stack<int> help)
{
    //判断传入num是否为空
    
    //都取top进行比较
    //可是刚开始的help必然为空，怎样取top呢
    //每一次都判断是否为空再取top
    
    //num不为空，help不为空的情况下不停判断栈顶
    //符合num.top>help.top num就进去Top
    //反之调用swap
    
    while(!num.empty())
    {
        while(!help.empty()&&help.top()>num)
        {
            swap(help.top(),num.top());
            
        }
        
        help.push(num.pop());
        
    }
    
    //倒回去
     while (!help.empty()) {
        num.push(help.top());
        help.pop();
    }
    
    return num;
    
    
}