大廠面試中常問的棧排序

很多大廠的筆試題中都會要求面試者寫一段棧排序，因為棧這個資料結構平時我們用的比較少，導緻很多面試者一下子都有點懵逼，這裡就來給大家解惑一下吧

題目：

1. 一個棧中有10個随機大小的元素，這個是初始棧
2. 可以讓你申請一個空棧作為交換使用
3. 不準使用任何其他資料結構進行存儲
4. 最終按照從小到大的順序輸出原始棧

思路：

1. Stack這個資料結構的核心API我們必須要了解下，不然真的無從下手，Pop，Push，Peek三種核心操作
2. Pop會讓棧頂資料出棧，同時删除原始棧頂的資料
3. Push添加元素到棧頂
4. Peek擷取棧頂元素，但是不删除原始棧頂的資料
5. 棧是典型的先進先出型資料結構，了解核心API後我們就可以發現，其實我們隻需要保證空棧的資料棧底是最小的即可

代碼：

public class StackSort {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < 10; i++) {
            stack.push( new Random().nextInt( 1000 ) );
        }
        Stack<Integer> tempStack = new Stack();
        while (!stack.isEmpty()) {
            Integer t = stack.pop();
            while (!tempStack.isEmpty() && tempStack.peek() > t) {
                stack.push( tempStack.pop() );
            }
            tempStack.push( t );
        }
        stack = tempStack;
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}