设计一个有getMin功能的栈、由两个栈组成的队列

1、设计一个有 getMin 功能的栈

【题目】
  实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
1．pop、push、getMin 操作的时间复杂度都是 O(1)。
2．设计的栈类型可以使用现成的栈结构。
【解答】
  在设计时，我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没
有区别，这个栈记为 stackData；另一个栈用于保存每一步的最小值，这个栈记为 stackMin。具
体的实现方式有两种。

第一种实现方案

1、压入数据规则
  假如当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。

• 如果为空，则newNum也压入stackMin。
• 如果不为空，则比较newNum和stackMin栈顶元素哪个小。
• 如果newNum更小或和stackMin栈顶元素相等，则将newNum压入stackMin
• 如果stackMin栈顶元素更小，则stackMin不压入任何元素

举例：依次压入 3、4、5、1、2、1 的过程中，stackData 和 stackMin 的变化如下图所示

2、弹出数据规则
  先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin栈顶元素和value哪个更小。
  通过上文提到的压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶元素既是stackMin栈的最小值也是stackData栈的最小值。所以不会出现value比stackMin栈顶元素更小的情况，value只能大于或等于stackMin的栈顶元素。
  当value值等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value值大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value。
  很显然，压入和弹出的规则是对应的。
3、查询当前栈中的最小值操作
  由上下文的的压入数据规则和弹出数据规则可知，stackMin栈中始终记录着stackData栈中的最小值，所以stackMin栈顶元素始终是当前stackData栈的最小值。
【代码】

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

    public stack(Stack<Integer> stackData, Stack<Integer> stackMin) {
        this.stackData = stackData;
        this.stackMin = stackMin;
    }

    public void push(int newNum) {
        if (this.stackMin.empty()) {
            this.stackMin.push(newNum);
        }
        else if(newNum <= this.getMin()){
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

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

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

    }

第二种实现方案

1、压入数据规则
  假如当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。

• 如果为空，则newNum也压入stackMin。
• 如果不为空，则比较newNum和stackMin栈顶元素哪个小。
• 如果newNum更小或和stackMin栈顶元素相等，则将newNum压入stackMin
• 如果stackMin栈顶元素更小，则把stackMin栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素
  举例：依次压入 3、4、5、1、2、1 的过程中，stackData 和 stackMin 的变化如下图所示。
  
  2、弹出数据规则
    在stackData中弹出元素，弹出的数据记录为value，弹出stackMin中的栈顶元素，返回value。
  很明显可以看出，压入与弹出规则是对应的。
  3、查询当前栈中的最小值操作
    由上下文的的压入数据规则和弹出数据规则可知，stackMin栈中始终记录着stackData栈中的最小值，所以stackMin栈顶元素始终是当前stackData栈的最小值。
  【代码】

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

    public stack1(Stack<Integer> stackData, Stack<Integer> stackMin) {
        this.stackData = stackData;
        this.stackMin = stackMin;
    }

    public void push(int newNum) {
        if (this.stackMin.empty()) {
            this.stackMin.push(newNum);
        } else if (newNum < this.getMin()) {
            this.stackMin.push(newNum);
        } else {
            int newMin = this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.empty()) {
            throw new RuntimeException(" your stack is empty");
        }

        this.stackMin.pop();

        return this.stackData.pop();
    }

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

    }

【点评】
  方案一和方案二其实都是用stackMin栈保存着stackData中每一步的最小值。共同点是所有的操作的时间复杂度都是O（1），空间复杂度都是O（n）。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入稍费时间，但是弹出操作稍省时间。

2、由两个栈组成的队列

【题目】
  编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
【解答】
  栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
  具体的实现是一个栈作为压入栈，在压入数据的时候只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。
  因为数据压入栈的时候顺序是先入后出的，那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1-5依次压入stackPush，bane从stackPush的栈顶到栈底就是5-1，此时依次再讲5-1压入stackPop，那么从stackPop的栈顶到栈底就是1-5.再从stackPop弹出时，顺序就像队列一样，如下图所示。

  听起来很简单，实际上必须要做到两点：
1、如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。
2、如果stackPop不为空，stackPush绝对不能像stackPop中压入数据。
  违反以上两点都会发生错误。
违反情况1举例：1-5依次压入stackPush，stackPush的栈顶到栈底元素是5-1，从stackPush压入到stackPop时，只讲5、4压入了stackPop，stackPush中还剩1、2、3没有压入，如果此时用户想弹出，那么最先弹出的是4，与队列的弹出要求不符。

违反情况2举例：1-5依次压入stackPush，stackPush将所有数据压入到stackPop，此时从stackPop的栈顶到栈底是1-5.此时6-10压入了stackPush，stackPop不为空，stackPush不能向其中压入元素，如果违反情况2，将6-10压入了stackPop，从stackPop栈顶到栈底就变成了6-10,1-5，那么如果此时用户想弹出，那么最先弹出的是6，与队列的弹出要求不符。
  上面介绍了压入的注意事项，那么压入数据的操作何时发生呢？
  这个选择的时机可以有很多，调用add、poll、peek三种方法中的任意一种时发生压入操作都是可以的。只要满足以上两点就不会出错。
【代码】

	public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;

    public Queue(Stack<Integer> stackPush, Stack<Integer> stackPop) {
        this.stackPush = stackPush;
        this.stackPop = stackPop;
    }

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

  每次stackPop栈中只存在一个数据，每次poll之后重新执行pushToPop()函数，再从stackPush中向stackPop压入一个元素。