设计一个有getMin()的栈 在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作
规则
创建两个栈空间并进行实例化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 /** * 这个stackData用来保存当前栈中的元素数据 功能与一个正常的栈没有区别 */ private Stack<Integer> stackData; /** * 这个stackMin用来保存每一步的最小元素数据 */ private Stack<Integer> stackMin; // 实例化变量 public MyStack() { this.stackData = new Stack<Integer>(); this.stackMin = new Stack<Integer>(); }
push() 方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 /*** * Tips: * _____ * |_|_|_|push方法向栈中添加元素,返回结果是当前添加的元素 * |_|_|_|push和add都是向栈中添加元素,底层实现也是一样的,都是先将Vector扩容,再添加 * @param 当前数据为newNum */ public void push(int newNum) { //是否为空 if (this.stackMin.isEmpty()) { //对象为空将其压入stackMin中 this.stackMin.push(newNum); //对象不为空时,进行判断比较 } else if (newNum <= this.getmin()) { //压入stackMin中 this.stackMin.push(newNum); } //将其压入当前栈stackData中 this.stackData.push(newNum); }
pop() 方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //用于移除栈顶对象,并作为函数的值返回该对象 public int pop() { //堆为空,抛出异常 if (this.stackData.isEmpty()) { throw new RuntimeException("你的Stack为空!!"); } //在stackData中弹出栈顶元素,记为value int value = this.stackData.pop(); //比较当前stackMin的栈顶元素和value if (value == this.getmin()) { this.stackMin.pop(); } //返回value (栈顶对象Vector对象中的最后一项) return value; }
getmin() 根据规则,stackMin始终记录着stackData中的最小值,所以stackMin的栈顶元素始终是当前stackData中的最小值1 2 3 4 5 6 7 8 9 10 //查询当前栈中的最小值操作 public int getmin() { //如果stackMin栈为空 if (this.stackMin.isEmpty()) { //提示 throw new RuntimeException("你的Stack为空!!"); } //查看栈顶的对象而不移除它 return this.stackMin.peek(); }
End 版权声明:出处《程序员代码面试指南 IT名企算法与数据结构题目最优解 ,左程云著》Xangli2341 进行重新整理编辑, 如有侵权请致邮至我的邮箱
1 2 3 搭这个的初衷就是记录自己学习的笔记. 希望能与大家交流进步 欢迎大家向我提出宝贵的意见
互敲代码,以示友好. 思维碰撞,共创火花.