栈和队列问题：设计一个有 getMin 功能的栈

【知识点】

　　栈是一个先进后出(FILO-First In Last Out)的数据结构，队列是一种先进先出(FIFO-First In First Out)的数据结构。

【题目】

　　实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

pop、push、getMin 操作的时间复杂度都是 O(1)。
设计的栈类型可以使用现成的栈结构。

【难度】

　　一星

【解答】

　　在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为 stackData;另一个栈用于保存每一步的最小值，这个栈记 stackMin.

压入数据规则(push)

　　假设当前数据为 newNum, 先将其压入 stackData。然后判断 stackMin 是否为空:

　　1). 如果为空, 则 newNum 也压入 stackMin。

　　2). 如果不为空，则比较 newNum 和 stackMin 的栈顶元素哪一个更小：如果 newNum 更小或两者相等，则 newNum 也压入 stackMin; 如果 stackMin 的栈顶元素更小，则 stackMin 不压入任何内容。这样处理的结果，则是 stackMin 的栈顶元素一定为 stackMin 中的最小值。

弹出数据规则(pop)

　　先在 stackData 中弹出栈顶元素，记为 value。然后比较当前 stackMin 的栈顶元素和 value, 从上面压入数据规则知道，stackMin 的栈顶元素一定为 stackMin 中的最小值，所以value 一定大于等于 stackMin 栈顶元素。当 value 等于 stackMin 的栈顶元素时，stackMin 弹出栈顶元素；当 value 大于 stackMin 的栈顶元素， stackMin 不弹出任何元素。结果返回 value。

查询当前栈中的最小值(getMin)

　　根据上述压入规则可知，该结果应该返回 stackMin 的栈顶元素.

　　具体实现见如下代码：

 import java.util.Stack;

 public class MyStack {

     private Stack<Integer> stackData;

     private Stack<Integer> stackMin;

     //压入数据

     public void push(int newNum){

         stackData.push(newNum);

         if(stackMin.isEmpty()){

             stackMin.push(newNum);

         }else{

             int minValue = stackMin.peek();

             if(newNum <= minValue){

                 stackMin.push(newNum);

             }

         }

     }

     //弹出数据

     public int pop(){

         if(stackData.isEmpty()){//栈为空则抛出异常

             throw new RuntimeException("该栈不存在任何元素！");

         }

         int value = stackData.pop();

         int minValue = stackMin.peek();

         if(value == minValue){

             stackMin.pop();

         }

         return value;

     }

     //查询最小元素

     public int getMin(){

         if(stackMin.isEmpty()){//栈为空则抛出异常

             throw new RuntimeException("该栈不存在任何元素！");

         }

         return stackMin.peek(); //peek 方法可以返回栈顶元素, 而不会弹出栈顶元素

     }

 }

巴特西

栈和队列问题：设计一个有 getMin 功能的栈

最新文章

热门文章