一、栈和队列

[1] 设计一个有getMin功能的栈

题目：
实现一个特殊的栈，在实现栈的基础功能上，再实现返回栈中最小元素的操作。
要求：
pop、push、getMin的操作时间复杂度都是O(1)。
设计的栈类型可以使用现成的栈结构。

public class MyStack1 {

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    // 初始化
    public MyStack1() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }

    // 压栈
    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum < this.getMin()) {
            this.stackMin.push(newNum);
        } else {
            this.stackMin.push(getMin());
        }
        this.stackData.push(newNum);
    }

    // 弹栈
    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("your statck is empty");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("your statck is empty");
        }
        return this.stackMin.peek();
    }
}

另一种设计：

public class MyStack2 {

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    // 初始化
    public MyStack2() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }

    // 压栈
    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum <= this.getMin()) {
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

    // 弹栈
    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("your statck is empty");
        }
        int value = this.stackData.pop();
        if (value == this.getMin()) {
            this.stackMin.pop();
        }
        return value;
    }

    public int getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("your statck is empty");
        }
        return this.stackMin.peek();
    }
}

[2] 由两个栈组成的队列

题目：
编写一个类，用两个栈实现队列，支持队列的基本操作(add,poll,peek)。

public class TwoStacksImplementQueue {

    public static class TwoStacksQueue {
        public Stack<Integer> stackPush;
        public Stack<Integer> stackPop;

        public TwoStacksQueue() {
            stackPush = new Stack<Integer>();
            stackPop = new Stack<Integer>();
        }

        public void add(int pushInt) {
            stackPush.push(pushInt);
        }

        public int poll() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
            return stackPop.pop();
        }

        public int peek() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
            return stackPop.peek();
        }
    }

}

[3] 用递归函数和栈操作逆序一个栈

题目：
一个栈依次压人1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个站转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

public int getAndRemoveLastEmlement(Stack<Integer> stack) {
    int result = stack.pop();
    if (stack.isEmpty()) {
        return result;
    } else {
        // 调用链上的last返回是一致的
        int last = getAndRemoveLastEmlement(stack);
        stack.push(result);
        return last;
    }
}

public void reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) {
        return;
    }
    // 获取栈底的值，返回顺序 1 2 3 
    int value = getAndRemoveLastEmlement(stack);
    reverse(stack);
    stack.push(value);
}

[4] 用一个栈实现另一个栈的排序

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

public int getAndRemoveLastEmlement(Stack<Integer> stack) {
    int result = stack.pop();
    if (stack.isEmpty()) {
        return result;
    } else {
        // 调用链上的last返回是一致的
        int last = getAndRemoveLastEmlement(stack);
        stack.push(result);
        return last;
    }
}

public void reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) {
        return;
    }
    // 获取栈底的值，返回顺序 1 2 3 
    int value = getAndRemoveLastEmlement(stack);
    reverse(stack);
    stack.push(value);
}