面试题 03.05. 栈排序

解题思路

最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中
1.题意中，要求只可使用一个临时栈来存放数据，不可使用其他数据结构（int[]/list）
2.用一个栈来存储已排序的数据，最小的元素在栈顶，最大的元素在栈底
3.push操作时，将已排序栈迭代出栈，并且把出栈的元素，入栈到临时栈，直到找到元素大于x的元素或者已排序栈为空，停止出栈
4.停止出栈之后，先将刚刚出栈的大于x的元素，入栈到排序栈，然后将x入栈，然后再将临时栈元素一一入栈到排序栈
5.pop或者peer或者isEmpty操作，直接对已排序栈进行相应栈操作即可

解题遇到的问题

无

后续需要总结学习的知识点

1.用liist或者deque去实现？
2.deque源码如何实现的？

##解法
import java.util.Stack;

class SortedStack {
    Stack<Integer> sortStack = null;
    Stack<Integer> tempStack = null;

    public SortedStack() {
        sortStack = new Stack<Integer>();
        tempStack = new Stack<Integer>();
    }

    public void push(int val) {
        tempStack.clear();

        while (!sortStack.isEmpty()) {
            int temp = sortStack.pop();
            if (temp > val) {
                sortStack.push(temp);
                break;
            } else {
                tempStack.push(temp);
            }
        }

        sortStack.push(val);

        while (!tempStack.isEmpty()) {
            sortStack.push(tempStack.pop());
        }
    }

    public void pop() {
        if (sortStack.isEmpty()) {
            return;
        }
        sortStack.pop();
    }

    public int peek() {
        if (sortStack.isEmpty()) {
            return -1;
        }
        return sortStack.peek();
    }

    public boolean isEmpty() {
        return sortStack.isEmpty();
    }
}