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

题目

一个栈中的元素类型为整型, 现在想将栈从顶到底按从大到小的顺序排序, 只需申请一个栈.
除此之外, 可以申请新的变量,但不能申请额外的数据结构, 如何完成排序?

思路

• 利用两个栈+临时变量, 通过比较, 使得辅助栈中元素有序
  申请一个辅助栈, 将原始栈的元素挨个取出, 通过比较最终使得辅助栈内的元素顶->底, 小->大排序.

  然后再将辅助栈的元素pop()并push()到原始栈中即可.

• 实现比较
  假设原始栈stack, 辅助栈helpStack, 变量temp = stack.pop()
  temp与辅助栈helpStack栈顶元素比较:

  • 如果temp小, 则直接入help;
  • 如果temp大, 将helpStack的栈顶元素存回stack中, 直到temp <= helpStack.pop(), 再将temp入栈helpstack

代码实现

public static void sortStackByStack(Stack<Integer> stack) {
    Stack<Integer> helpStack = new Stack<Integer>();

    while (!stack.isEmpty()) {
      int temp = stack.pop();
      while (!helpStack.isEmpty() && helpStack.peek() < temp) {
        stack.push(helpStack.pop());
      }
      helpStack.push(temp);
    }
    while (!helpStack.isEmpty()) {
      stack.push(helpStack.pop());
    }
  }