数据结构【栈】（八）：使用栈为另一个栈排序

浅浅的花香味﹌ 2022-03-02 06:36 185阅读 0赞

#### 题目 ####

一个栈中的元素都是整型，现在想将该栈从栈顶到栈底从大到小排列，只允许申请一个栈，除此之外可以申请新的变量，但不能申请额外的数据结构。

#### 思路 ####

使用两个栈和一个变量，把排序栈中的第一个元素压入辅助栈中，  
如果排序栈中新弹出的cur元素比辅助栈的元素大的话，就把辅助栈中的元素压回排序栈，把cur元素压入辅助栈中。不断重复此过程，辅助栈中的元素始终是从小到大排序。

#### 代码实现 ####

public class StackByStackSort {
        public static void sortStackByStack(Stack<Integer> stack) {
            Stack<Integer> help = new Stack<Integer>();
            while (!stack.isEmpty()) {
                int cur = stack.pop();
                while (!help.isEmpty() && help.peek() < cur) {
                    stack.push(help.pop());
                }
                help.push(cur);
            }
            while (!help.isEmpty()) {
                stack.push(help.pop());
            }
        }
    
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<Integer>();
            stack.push(3);
            stack.push(6);
            stack.push(4);
            stack.push(9);
            stack.push(2);
    
            sortStackByStack(stack);
    
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
    
        }
    }

输出结果

9
    6
    4
    3
    2