1.算法-栈和队列

落日映苍穹つ 2021-10-01 11:36 276阅读 0赞

# 题目 #

![18721752-6393b079665c0e6f.png][]

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

[18721752-6393b079665c0e6f.png]: /images/20210918/5ee69c0ab0d1430c9b0102446bb4c28f.png