用一个栈实现另一个栈的排序

题目

有一个待排序的栈,现在想将该栈从顶到底按照从大到小的顺序排序,只允许申请一个栈。除此之外,可以申请新的变量,但不能申请新的数据结构。

实现

/**
    * 使用一个帮助栈对传入的栈进行拍戏
    *
    * @param stack 待排序的 stack
    * @param <T>   泛型
    */
   /**
    * 使用一个帮助栈对传入的栈进行拍戏
    *
    * @param stack 待排序的 stack
    * @param <T>   泛型
    */
   public static <T extends Comparable<T>> void sort(Stack<T> stack) {
       Stack<T> helpStack = new Stack<>();
       while (!stack.isEmpty()) {
           T currentElement = stack.pop();
           while (!helpStack.isEmpty() && currentElement.compareTo(helpStack.peek()) > 0) {
               stack.push(helpStack.pop());
           }
           helpStack.push(currentElement);
       }

       while (!helpStack.isEmpty()) {
           stack.push(helpStack.pop());
       }
   }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券