题目

image.png

解题思路

这题需要将原先无序的栈进行排序，变成从栈顶到栈底大到小排序，且只允许申请一个栈，即一个变量来实现，基于此，可以创建一个哨兵栈，将原栈中的元素按照从小到大排序，然后再将之重新入栈即可。
哨兵栈的设计思路：
哨兵栈从小到大排序，那么其栈顶永远是其最小值，将哨兵栈中的栈顶和原stack中的栈顶pop比较，如果小于原栈中的pop数据，那么将哨兵栈栈顶弹出，弹出所有小于pop的元素，并将之重新压入原栈，直到哨兵栈中栈顶大于pop或者哨兵栈为空。

code

package com.pl.arithmetic.zo.stack.stack5;

import java.util.Stack;

/**
 * <p>
 *
 * @Description:
 * </p>
 * @ClassName MyStack5
 * @Author pl
 * @Date 2021/2/9
 * @Version V1.0.0
 */
public class MyStack5 {

    /**
     * 反转一个stack，可以通过维护一个哨兵stack，本题需要stack从大到小输出，那么维护一个哨兵队列从栈顶到栈底按照从小到大入栈。
     *
     * @param stack
     * @return void
     * @exception
     * @author silenter
     * @date 2021/2/9 10:12
    */
    public void sortByDescStack(Stack<Integer> stack){
        //栈顶到栈底按照从小到大排序
        Stack<Integer> flagStack = new Stack<>();
        while (!stack.empty()){
            Integer pop = stack.pop();
            //将pop和flagStack中的元素比较，如果小于pop，从flagStack中弹出，即弹出flagStack中所有小于pop的元素，直到栈顶大于pop或者哨兵栈为空。
            //既然哨兵栈是从小到大排列的，那么哨兵队列的栈顶永远都是最小的，循环直到栈顶元素大于pop
            while (!flagStack.empty()&&flagStack.peek()<pop){
                //将哨兵stack中弹出的元素重新压入stack
                stack.push(flagStack.pop());
            }
            //除了哨兵stack中为空这种情况，哨兵stack能够入栈的条件就是，栈顶大于pop
            flagStack.push(pop);
        }
        //此时哨兵中一定是从小到大排列的
        while (!flagStack.empty()){
            stack.push(flagStack.pop());
        }
    }
}