目录
一.栈
1.Java中关于栈的API
Stack<Object> stack = new Stack<>();
入栈 stack.push(1)
出栈 stack.pop();
栈顶元素 stack.peek()
栈的元素个数 stack.size()
栈是否为空 stack.empty()
二.队列
可以使用双端队列实现,因为Queue是一个接口,无法直接实现
三.双端队列
双端队列,既可以实现栈的功能,也可以实现队列的功能
1.ArrayDeque
ArrayDeque是基于动态数组实现的
作为栈使用的常用的操作
入栈操作:
deque.push(1) deque.addFirst(1) deque.offerFirst(1)
出栈操作
deque.removeFirst() deque.remove() deque.pop()
查看栈顶元素
deque.peek() deque.peekFirst()
作为队列使用的常用的操作
入队列操作:
deque.add(1) deque.addLast(1) deque.offerLast(1) deque.offer(1)
出队列操作:
deque.poll() deque.removeLast()
查看队列末端操作:
deque.peekLast()
查看双端队列的长度
int size = deque.size();
判断队列是否为空
boolean empty = deque.isEmpty();
2.LinkedList
LinkedList是基于链表实现的
与ArrayDeque几乎一样
四.优先队列
1.大顶堆小顶堆
堆:堆是一种非线性结构,可以把堆看作一棵二叉树,也可以看作一个数组
大顶堆:每个节点的值都大于或等于其左右孩子的值
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆:每个节点的值都小于或等于其左右孩子的值
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2].
2.堆的基本操作
这里拿小顶堆举例
上浮+添加元素
上浮是往二叉堆添加元素用到的操作,它其实是不断的调整k的位置为父元素的位置直到满足条件为止
// 用数组表示堆
Object []objs = new Object[10];
/**
* 上浮:
* k表示堆的最后一个位置;
* obj表示将要插入的元素。
*/
private void siftUp(int k, Object obj) {
// 1. 判断k是否为根元素的位置0,如果是则直接赋值
while(k>0) {
// 2. 获取父元素的位置,parent = (k-1)/2
int parent = (k-1) >>> 1;
// 3. 如果父元素的优先级大于等于obj,跳出循环并插入obj
if(objs[parent] >= obj) {
break;
}
// 4. 如果父元素的优先级小于obj,将父元素赋值到k的位置,更改k为父元素的位置,继续循环
objs[k] = objs[parent];
k = parent;
}
// 5. 为obj赋值
objs[k] = obj;
}
/**
* 添加元素,不考虑数组扩容的情况。
* 假设size表示当前堆包含的元素个数(注意不一定等于上面定义的10)
*/
public void add(Object obj) {
if(size==0) {
objs[0] = obj;
} else {
siftUp(size, obj);
size++;
}
}
下沉+删除
// 用数组表示堆
Object []objs = new Object[10];
/**
* k被删除元素的位置;
* obj堆的最后一个元素;
* 假设size为当前堆包含元素的个数(不一定是上面定义的10)
*/
private void siftDown(int k, Object obj) {
// 1. 找到最后一个元素的父节点的位置, (最后一个元素位置-1) / 2
int parent = (size-1-1) >>> 1;
// 2. 判断k是否在父节点位置之后,如果在之前则需要下沉操作
while(k <= parent) {
// 3.获取k的左右子节点的位置
int left = k<<<2 +1;
int right = left+1;
// 4.选择左右子节点中优先级最高的一个
int best;
if (objs[left] > objs[right]) {
best = left;
} else {
best = right;
}
// 5.判断obj和best的优先级谁高。如果obj优先级高,则跳出循环直接赋值,否则继续下沉
if (obj >= objs[best]) {
break;
}
objs[k] = objs[best];
k = best;
}
// 6.赋值
objs[k] = obj;
}
/**
* 删除第p个元素。
*/
public void remove(int p) {
// 1.获取最后一个元素
Object obj = objs[size-1];
// 2.如果p不等于最后一个元素
if (p != size-1) {
// 3.把最后一个元素和p进行下沉操作
siftDown(p, obj);
if(objs[p] == obj) {
// 4. 上浮
siftUp(p, obj);
}
}
size--;
}
3.常见的方法
初始化
//小顶堆
PriorityQueue<Integer> queue = new PriorityQueue<>();
//大顶堆
PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->b-a);
入队列
queue.add(1) queue.offer(1)
出队列
queue.remove() queue.poll()
其他基本和上面的一样
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/101050.html