算法-13用一个栈实现另一个栈的排序

本文主要是介绍算法-13用一个栈实现另一个栈的排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

输入描述：

输出描述：

示例1

输入：
5
5 8 4 3 6

输出：
8 6 5 4 3

思路

原来的栈为 stack，辅助栈为 help。不断从 stack 中弹出元素，弹出的元素记为 cur。

• 如果 help 为空或 cur 小于 help 的栈顶元素，则将cur直接压入help。
• 如果 cur 大于 help 的栈顶元素，则从 help 一直弹出元素压入stack，直到 cur 小于 help 的栈顶元素。
• stack 为空时，过程结束，此时 help 中元素的顺序从栈顶到栈底为从小到大的顺序，将 help 中的元素依次弹出并压入 stack 就可以实现题目要求的 stack 的顺序。

import java.util.Scanner;
import java.util.Stack;

public class Main{
    
    public static void sortStack(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<>();
        
        Scanner scanner = new  Scanner(System.in);
        int n = scanner.nextInt();
        for(int i=0;i<n;i++){
            stack.push(scanner.nextInt());
        }
        sortStack(stack);
        while(!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
    }
}

这篇关于算法-13用一个栈实现另一个栈的排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！