设计有一个getMin功能的栈 说明
本文来自左程云老师所著的《程序员面试代码指南》第一章
题目
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
要求
1.pop、push、 getMin操作的时间复杂度都是0(1)。
2.设计的栈类型可以使用现成的栈结构。
方法
在设计上使用两个栈,一个栈用来保存当前栈中的元素,其功能和一个正常的栈
没有区别,这个栈记为stackData;
另一个栈用于保存每一步的最小值,这个栈记为stackMin。
举例
stackData存放3 4 5 1 2 1
则stackMin存放3 1 1
代码实现
import java.util.Scanner;
public class MyStack {
private Stack stackData;
private Stack stackMin;
public static void main(String[] args) {
Scanner cs = new Scanner(System.in);
MyStack stack = new MyStack();
System.out.println("输入数据个数:");
int n = cs.nextInt();
for(int i=0;
i();
stackMin = new Stack();
}
void push(int m) {
stackData.push(m);
if(stackMin.empty()) stackMin.push(m);
else {
if(stackMin.peek()>=m)
stackMin.push(m);
//stackMin栈顶元素大于等于m时加入
}
}
//此后当有元素出栈时,stackData正常出栈,如若出栈元素等于stackMin的栈顶,
//则stackMin栈顶一同出栈,保证实时更新stackMin void pop() {
if(stackData.empty())
throw new RuntimeException("Your empty is empty!");
int a = stackData.pop();
if(a == stackMin.peek()) stackMin.pop();
}
int getMin() {
if(stackData.empty())
throw new RuntimeException("Your empty is empty!");
int a = stackMin.peek();
return a;
}
}
【java|设计有一个getMin功能的栈( java )】说明:只为记录自己每日学习,加油 ~
推荐阅读
- 栈和队列|1.1设计一个有getMin功能的栈
- 日常记录|IDEA中启动TomCat失败,提示: 1099 is already in use 解决办法【实际并未占用】
- java|使用堆内内存HeapByteBuffer的注意事项
- Java|java集合之ArrayList详解
- 数据结构与算法|集合总结--ArrayList、LinkedList、HashMap
- Java|第十二篇(Java集合详解、ArrayList、Vector、LinkedList、Queue、PriorityQueue、Deque、HashSet、TreeSet)
- java|java常用集合详解
- Java|java面试总结(一)java面向对象、arraylist与linkedlist区别、高并发中的集合问题、JDK1.8新特性
- 算法训练营|【算法训练营】 - ⑤ Trie Tree、桶排序、排序总结