栈和队列|1.1设计一个有getMin功能的栈栈|队列|数据结构|算法|面试

【栈和队列|1.1设计一个有getMin功能的栈】【题目】：设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】：

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

【解答】

第一种设计方案： stackMin压入栈时，稍节省空间，但弹出操作稍费时间。

public class MyStack1 { private Stack stackData; //定义两个私有类型的栈，防止栈数据被更改； private Stack stackData; public MyStack1()//在公有方法中，创建两个新对象; { this. stackData = https://www.it610.com/article/new Stack(); this. stackMin = new Stack(); }public void push(int newNum)//入栈操作； { if(this.stackMin.isEmpty())//第一种情况：先判断stackMin栈是否为空； { this. stackMin. push(newNum); //若stackMin栈为空，则将newNum压入stackMin栈中； } else if(newNum <= this.getMin())//第二种情况：若newNum小于或等于栈中获得的最小值； { this. stackMin. push(newNum); //若newNum小于或等于栈中所获得的最小值，则将newNum也压入stackMin栈中； } this. stackData. push(newNum); //若不符合以上两种入栈情况，则将newNum压入stackData栈中； }public int pop()//出栈操作； { if(this.stackData.isEmpty())//先判断stackData栈中的数据是否为空； { throw new RuntimeException("Your stack is empty."); //若为stackData栈中数据为空，则抛出运行时异常，并提示"栈为空"; } int value = https://www.it610.com/article/this. stackData. pop(); //value表示栈顶元素; if(value == this.getMin())//如果value栈顶元素等于栈中所获得的最小值，则stackMin中的元素出栈; { this. stackMin. pop(); } return value; //否则，返回value栈顶元素中的值; }public int getMin()//定义一个公有的getMin()方法，来获取栈中的最小值; { if(this.stackMin.isEmpty())//判断stackMin栈中是否为空； { throw new RuntimeException("Your stack is empty.")//若stackMin栈中为空，则抛出运行时异常，并提示"栈为空"; } return this. stackMin. peek(); //否则，使用peek()查询并返回stackMin栈中的最小值，peek()只是返回栈顶元素，但它不在堆栈中删除读取的数据元素; }}

第二种设计方案： stackMin压入栈时，稍消耗空间，但弹出操作稍节省时间。

public class MyStack2 { private Stack stackData; //定义两个私有类型的栈，防止栈数据被更改； private Stack stackMin; public MyStack2()//在公有方法中，创建两个新对象; { this. stackData = https://www.it610.com/article/new Stack(); this. stackMin = new Stack(); } public void push(int newNum)//入栈操作； { if(this.stackMin.isEmpty())//第一种情况：先判断stackMin栈是否为空； { this.stackMin.push(newNum); //若stackMin栈为空，则将newNum压入stackMin栈中； } else if(newNum < this.getMin())//第二种情况：若newNum小于栈中获得的最小值； { this.stackMin.push(newNum); //若newNum小于栈中所获得的最小值，则将newNum也压入stackMin栈中； } else//第三种情况：取出最小值重复压入栈中； { int newMin = this.stackMin.peek(); this.stackMin.push(newMin); } this.stackData.push(newNum); //若不符合以上三种入栈情况，则将newNum压入stackData栈中； } public int pop()//出栈操作； { if(this.stackData.isEmpty())//先判断stackData栈中的数据是否为空； { throw new RuntimeException("Your stack is empty."); //若为stackData栈中数据为空，则抛出运行时异常，并提示"栈为空"; } this.stackMin.pop(); //stackMin种数据出栈； return this.stackData.pop(); //依次把栈中的数据执行出栈操作； } pubilc int getMin()//定义一个公有的getMin()方法，来获取栈中的最小值; { if(this.stackMin.isEmpty())//判断stackMin栈中是否为空； { throw new RuntimeException("Your stack is empty.")//若stackMin栈中为空，则抛出运行时异常，并提示"栈为空"; } return this. stackMin. peek(); //否则，使用peek()查询并返回stackMin栈中的最小值，peek()只是返回栈顶元素，但它不在堆栈中删除读取的数据元素; } }