[TOC]

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

题目：

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

题解思路：

题解代码：

import java.util.Stack;

public class Problem_05_StackSortStack {

  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(1);
    stack.push(6);
    stack.push(2);
    stack.push(5);
    stack.push(4);
    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());
    System.out.println(stack.pop());

  }

}