2023-09-13
530
原创
Java数据结构和算法(代码版)-2
Java数据结构和算法(代码版)-2
B树
package com.lzlg.study.algorithm.new2023.btree;
import java.util.Arrays;
/
* B树,特性有:
* 1.非叶子节点的孩子树称为度(degree)或阶(order)-用m指代
* 2.非叶子节点最多有m个孩子
* 3.除根节点和叶子节点,其他节点至少有ceil(m/2)-[m除以2向上取整]个孩子
* 4.所有的叶子节点都在同一层
* 5.每个非叶子节点由n个关键字和n+1个指针组成,其中n的范围是[ceil(m/2)-1, m-1]
* 孩子数量: [ceil(m/2), m]
* 关键字数: [ceil(m/2)-1, m-1]
* 6.同一层的节点按关键字升序排列
*
* @author lzlg
* 2023/7/31 9:53
*/
public class BTree {
// 树的根节点
BNode root;
// 树的最小度数
int minDegree;
// 节点的key数组的最大数量
final int MAX_KEYS;
// 节点的key数组的最小数量
final int MIN_KEYS;
public BTree() {
// 默认最小度数为2
this(2);
}
public BTree(int minDegree) {
// 最小度数
this.minDegree = minDegree;
// 创建根节点
this.root = new BNode(this.minDegree);
// 最大的key数量是最小度数的两倍-1
MAX_KEYS = this.minDegree * 2 - 1;
// 最小的key数量是最小度数-1
MIN_KEYS = this.minDegree - 1;
}
/
* 删除指定key的节点
*
* @param key 指定key
*/
public void remove(int key) {
doRemove(root, key, null, 0);
}
/
* 递归删除指定key的节点
*
* @param node 当前节点
* @param key 指定key
* @param parent 当前节点的父节点
* @param index 当前节点在父节点的children的下标
*/
private void doRemove(BNode node, int key, BNode parent, int index) {
int i = 0;
// 从当前节点中查找key
while (i < node.keyCount) {
// 注意这里的循环退出条件是>=
// 包括两种情况:
// 1.找到了key,此时i就是key对应的当前节点keys的下标
// 2.没找到key,如果当前节点是叶子节点,则是没找到
// 如果当前节点是非叶子节点,则需要到孩子节点中查找,此时i是孩子节点的下标
if (node.keys[i] >= key) {
break;
}
i++;
}
// 如果当前节点是叶子节点
if (node.leaf) {
// 如果没找到,则直接返回
if (!found(node, key, i)) {
return;
}
// 如果找到了,则从当前节点中删除key
// 此时i就是key对应的当前节点keys的下标
node.removeKey(i);
// 删除key后,可能要进行调整
} else {// 如果当前节点不是叶子节点
// 如果没找到,则递归到孩子节点进行查找和删除
if (!found(node, key, i)) {
// 此时i是孩子节点的下标
doRemove(node.children[i], key, node, i);
// 删除key后,可能要进行调整
} else {
// 如果找到了,则进行删除
// 删除时需要找到后继叶子节点,进行key的替换,然后删除后继节点
// 此时需要在i+1的孩子节点上查找后继叶子节点
BNode s = node.children[i + 1];
// 直到找到是叶子节点的后继
while (!s.leaf) {
s = s.children[0];
}
// 进行key的替换
int sKey = s.keys[0];
node.keys[i] = sKey;
// 将后继节点删除
doRemove(node.children[i + 1], sKey, node, i + 1);
// 删除key后,可能要进行调整
}
}
// 如果小于最小的度数,则进行调整
if (node.keyCount < MIN_KEYS) {
balance(parent, node, index);
}
}
/
* 删除节点后进行平衡调整
*
* @param parent 父节点
* @param node 当前节点
* @param index 当前节点在父节点的下标
*/
private void balance(BNode parent, BNode node, int index) {
// 如果当前节点已经是根节点,则不进行调整
// 因为根节点的keyCount可以小于最小度数
if (node == root) {
// 情况4:如果根节点的keyCount为0,则将根节点的孩子节点变为根节点
// 因为要留着根节点,所以有判断root.children[0] != null保留无数据的根节点(刚创建时的状态)
if (root.keyCount == 0 && root.children[0] != null) {
root = root.children[0];
}
return;
}
// 找到当前节点的左兄弟
BNode left = parent.childLeftSibling(index);
// 找到当前节点的右兄弟
BNode right = parent.childRightSibling(index);
// 情况1:如果左边兄弟富裕,则从左边兄弟借一个
if (left != null && left.keyCount > MIN_KEYS) {
// 先将父节点中的index-1(因为要从左边挪动一个到父节点,父节点挪动一个到当前节点)
// 的key插入到当前节点keys的头部
node.insertKey(parent.keys[index - 1], 0);
// 如果左边兄弟节点不是叶子节点
// 则需要把左边兄弟节点的最右边的孩子节点删除
// 并插入到当前节点children的头部
if (!left.leaf) {
node.insertChild(left.removeRightMostChild(), 0);
}
// 从左边兄弟节点keys中删除最后一个,并赋值给父节点中的index-1
parent.keys[index - 1] = left.removeRightMostKey();
return;
}
// 情况2:如果右边兄弟富裕,则从右边兄弟借一个
if (right != null && right.keyCount > MIN_KEYS) {
// 将父节点的下标为index的key转移到当前节点最后
node.insertKey(parent.keys[index], node.keyCount);
// 如果右边兄弟不是叶子节点
// 需要右边兄弟最左边的孩子节点删除
// 并插入到新节点的最后
if (!right.leaf) {
node.insertChild(right.removeLeftMostChild(), node.keyCount + 1);
}
// 将右边兄弟最左边的key删除,并赋值给父节点的下标为index的key
parent.keys[index] = right.removeLeftMostKey();
return;
}
// 情况3:如果左右兄弟都不富裕,则进行合并,使用靠左合并的方法
// 如果左边兄弟不为null,则合并到左边兄弟
if (left != null) {
// 先从父节点中删除当前节点
parent.removeChild(index);
// 将父节点的index-1的key删除并插入到左边兄弟的最右侧
left.insertKey(parent.removeKey(index - 1), left.keyCount);
// 然后将当前节点的keys和children都转移到左边兄弟
node.moveToTarget(left);
} else {// 否则合并到自身
// 从父节点中删除右边兄弟
parent.removeChild(index + 1);
// 父节点中删除index指定的key并插入到当前节点中
node.insertKey(parent.removeKey(index), node.keyCount);
if (right != null) {
// 将删除的右边兄弟的keys和children都转移到当前节点
right.moveToTarget(node);
}
}
}
/
* 是否在当前节点中找到指定key
*
* @param node 当前节点
* @param key 指定key
* @param i 下标
* @return 结果
*/
private boolean found(BNode node, int key, int i) {
return i < node.keyCount && node.keys[i] == key;
}
/
* 添加或更新指定的key
*
* @param key 指定key
*/
public void put(int key) {
doPut(root, key, null, 0);
}
/
* 添加或更新指定的key
*
* @param node 节点
* @param key 指定key
*/
private void doPut(BNode node, int key, BNode parent, int index) {
int i = 0;
while (i < node.keyCount) {
// 如果找到了,则进行更新(因为没有value,所以这里没有操作)
if (node.keys[i] == key) {
// 更新操作
return;
}
// 如果遇到比key大的,则直接跳出循环
// 此时i的值就指向待插入的位置下标
if (node.keys[i] > key) {
break;
}
i++;
}
// 如果当前节点是叶子节点,则进行插入
if (node.leaf) {
// 进行插入
node.insertKey(key, i);
// 插入之后,需判断当前节点的keyCount是否达到MAX_KEYS
// 如果达到则需要进行分裂
} else {// 不是叶子节点,则进行递归
// 此时i值就是孩子节点数组的下标
doPut(node.children[i], key, node, i);
// 非叶子节点也有可能keyCount达到MAX_KEYS
// 如果达到则需要进行分裂
}
// 进行分裂操作
if (node.keyCount == MAX_KEYS) {
split(node, parent, index);
}
}
/
* 进行分离,步骤如下:
* 1.创建一个新的节点
* 2.将待分裂节点的右半部分(范围从最小度数到keys数组末尾)转移到新节点上
* 3.更新新节点和分裂节点的节点数量(keyCount)
* 4.将分裂节点下标为minDegree的元素插入到父节点中
* 插入父节点的下标即为当前分裂节点在父节点中的下标(index)
* 5.将新节点插入到父节点孩子节点数组中
* 插入的下标为当前分裂节点在父节点中的下标(index)+1
* <p>
* 两种特殊情况:
* 1.如果分裂节点是根节点(parent为null)
* 则先创建一个新的根节点,且将分裂节点加入到新根节点,替换旧根节点和赋值给父节点
* 并按上述步骤操作即可
* 2.如果分裂节点是非叶子节点,则在步骤2时,需把相应的孩子节点也转移过去
*
* @param child 孩子节点(也是需分裂的节点)
* @param parent 父节点
* @param index 孩子节点在父节点的下标
*/
private void split(BNode child, BNode parent, int index) {
// 特殊情况:如果是根节点
if (parent == null) {
// 创建新的根节点
BNode newRoot = new BNode(minDegree);
// 新的根节点一定不是叶子节点
newRoot.leaf = false;
// 需要将孩子节点插入到新根节点
newRoot.insertChild(child, 0);
// 替换旧根节点
this.root = newRoot;
// 父节点是新的根节点
parent = newRoot;
}
// 创建新孩子节点
BNode newChild = new BNode(minDegree);
// 孩子节点和新孩子节点在同一层,因此是否叶子节点的leaf属性保持一致
newChild.leaf = child.leaf;
// 将孩子节点的数据转移一部分到新节点中
System.arraycopy(child.keys, minDegree, newChild.keys, 0, minDegree - 1);
// 特殊情况2:
// 如果孩子节点不是叶子节点,则需要拷贝孩子节点的孩子节点
if (!child.leaf) {
// 注意这里复制的数量是minDegree(最小度数)
System.arraycopy(child.children, minDegree, newChild.children, 0, minDegree);
}
// 更新新孩子节点的有效key数量
newChild.keyCount = minDegree - 1;
// 将孩子节点中间的元素插入到父节点中
parent.insertKey(child.keys[minDegree - 1], index);
// 更新孩子节点的有效key数量
child.keyCount = minDegree - 1;
// 将新孩子节点插入到父节点中
parent.insertChild(newChild, index + 1);
}
/
* 判断是否包含指定key
*
* @param key 指定key
* @return 结果
*/
public boolean contains(int key) {
// 能找到不为null则是包含
return root.get(key) != null;
}
/
* 节点类
*/
static class BNode {
// 关键字数组,用于查找定位,是升序的
int[] keys;
// 孩子节点,有可能有多个
BNode[] children;
// 有效的关键字数量
// keyCount+1是孩子节点最大的数量
int keyCount;
// 是否是叶子节点,默认是true
boolean leaf;
// 最小度数
int minDegree;
public BNode(int minDegree) {
if (minDegree < 2) {
throw new IllegalArgumentException("最小度数:" + minDegree + "非法");
}
this.minDegree = minDegree;
// 默认是叶子节点
this.leaf = true;
// 孩子节点的数量是最小度数的2倍(B树性质)
this.children = new BNode[this.minDegree * 2];
// 关键字的数量是最小度数的2倍-1(B树性质)
this.keys = new int[this.minDegree * 2 - 1];
}
@Override
public String toString() {
// 只返回keys数组的有效部分
return Arrays.toString(Arrays.copyOfRange(keys, 0, keyCount));
}
/
* 通过key查找指定的节点
*
* @param key 关键字key
* @return 节点
*/
BNode get(int key) {
int i = 0;
// 找到指定key的节点
while (i < keyCount) {
// 如果当前节点的keys中有对应key的,则返回该当前节点
if (keys[i] == key) {
return this;
}
// 找到比指定key大的
if (keys[i] > key) {
break;
}
i++;
}
// 如果当前节点是叶子节点,且在上面的循环中没有找到,则直接返回null
if (leaf) {
return null;
}
// 如果当前节点是非叶子节点,则在孩子节点中进行查找
// 退出循环时的i值就是孩子节点的下标
return children[i].get(key);
}
/
* 向指定index下标插入key
*
* @param key 关键字key
* @param index 下标
*/
void insertKey(int key, int index) {
// 把从index到数组尾的元素移动
System.arraycopy(keys, index, keys, index + 1, keyCount - index);
// 移动完成后,将key放入到指定下标
keys[index] = key;
// 数组元素数量加1
keyCount++;
}
/
* 向指定index下标插入孩子节点
*
* @param child 孩子节点
* @param index 下标
*/
void insertChild(BNode child, int index) {
// 把从index到数组尾的元素移动
System.arraycopy(children, index, children, index + 1, keyCount - index);
// 移动完成后,将child放入到指定下标
children[index] = child;
// 数组元素数量的维护交给方法insertKey进行维护了,这里就不增加了
}
/
* 删除指定下标的key
*
* @param index 指定下标
* @return 被删除的key
*/
int removeKey(int index) {
// 被删除的key值
int removed = keys[index];
// 移动元素把下标为index的位置覆盖
System.arraycopy(keys, index + 1, keys, index, keyCount - index - 1);
// 减少关键字数量
keyCount--;
return removed;
}
/
* 删除最左边的key(第一个)
*
* @return 被删除的key
*/
int removeLeftMostKey() {
return removeKey(0);
}
/
* 删除最右边的key(最后一个)
*
* @return 被删除的key
*/
int removeRightMostKey() {
return removeKey(keyCount - 1);
}
/
* 删除指定下标的孩子节点
*
* @param index 下标
* @return 孩子节点
*/
BNode removeChild(int index) {
BNode child = children[index];
// 注意这里最后一个参数不再减1,因为移动key的时候已经做过了
System.arraycopy(children, index + 1, children, index, keyCount - index);
// help GC
children[keyCount] = null;
return child;
}
/
* 删除最左边的child(第一个)
*
* @return 被删除的child
*/
BNode removeLeftMostChild() {
return removeChild(0);
}
/
* 删除最右边的child(最后一个)
*
* @return 被删除的child
*/
BNode removeRightMostChild() {
// 注意这里最后一个参数不再减1,因为移动key的时候已经做过了
return removeChild(keyCount);
}
/
* 找到指定下标孩子节点的左兄弟
*
* @param index 下标
* @return 左兄弟
*/
BNode childLeftSibling(int index) {
// 如果大于0,则有左兄弟,否则没有
return index > 0 ? children[index - 1] : null;
}
/
* 找到指定下标孩子节点的右兄弟
*
* @param index 下标
* @return 右兄弟
*/
BNode childRightSibling(int index) {
// 如果等于keyCount,则没有右兄弟,否则有
return index == keyCount ? null : children[index + 1];
}
/
* 将节点的keys和children转移到目标节点上
*
* @param target 目标节点
*/
void moveToTarget(BNode target) {
// 起始添加的位置
int start = target.keyCount;
// 如果不是叶子节点,则移动孩子节点
if (!leaf) {
// 进行copy,要比移动keys多移动一位
System.arraycopy(children, 0, target.children, start, keyCount + 1);
// for (int i = 0; i < keyCount; i++) {
// target.children[start + i] = children[i];
// }
}
// 进行copy移动
System.arraycopy(keys, 0, target.keys, start, keyCount);
// 目标的keyCount增加当前节点的keyCount
target.keyCount += keyCount;
// 移动keys
// for (int i = 0; i < keyCount; i++) {
// // 移动完成后,还得增加目标的keyCount
// target.keys[target.keyCount++] = keys[i];
// }
}
}
}
package com.lzlg.study.algorithm.new2023.btree;
import java.util.LinkedList;
/
* 测试
*
* @author lzlg
* 2023/7/31 12:54
*/
public class TestBTree {
public static void main(String[] args) {
testBtree();
}
private static void testMoveTarget() {
BTree.BNode node = new BTree.BNode(2);
node.leaf = false;
node.keyCount = 2;
node.keys = new int[]{2, 3, 0};
node.children = new BTree.BNode[]{
new BTree.BNode(2),
new BTree.BNode(2),
new BTree.BNode(2)
};
System.out.println(node);
System.out.println("==================");
BTree.BNode target = new BTree.BNode(2);
node.moveToTarget(target);
System.out.println(target);
}
private static void testBtree() {
BTree tree = new BTree();
tree.put(1);
tree.put(2);
tree.put(3);
tree.put(4);
tree.put(5);
tree.put(6);
tree.put(7);
tree.put(8);
tree.put(9);
tree.put(10);
tree.put(11);
print(tree.root);
System.out.println("=============================");
tree.remove(2);
print(tree.root);
System.out.println("=============================");
}
private static void print(BTree.BNode node) {
if (node == null) {
return;
}
LinkedList<TestNode> queue = new LinkedList<>();
queue.offer(new TestNode(node, null));
int count = 1;
while (!queue.isEmpty()) {
// 下一层的元素数量
int nextCount = 0;
for (int i = 0; i < count; i++) {
// 弹出栈顶元素
TestNode pop = queue.pop();
System.out.print(pop + "\t");
// 将孩子节点加入到队列中
for (int j = 0; j <= pop.node.keyCount; j++) {
if (pop.node.children[j] != null) {
nextCount++;
queue.offer(new TestNode(pop.node.children[j], pop.node));
}
}
}
// 换行
System.out.println("--------------------------------");
count = nextCount;
}
}
private static class TestNode {
// 当前节点
BTree.BNode node;
// 父节点
BTree.BNode parent;
public TestNode(BTree.BNode node, BTree.BNode parent) {
this.node = node;
this.parent = parent;
}
@Override
public String toString() {
return parent == null ? node.toString()
: "parent: " + parent + ", keys: " + node.toString() + "\n";
}
}
}
栈
package com.lzlg.study.algorithm.new2023.stack;
import java.util.Iterator;
/
* 使用数组实现栈
* 数组的头部是栈底,尾部是栈顶
*
* @author lzlg
* 2023/7/23 10:14
*/
public class ArrayStack<T> implements MyStack<T> {
// 数组
private final T[] array;
// 栈顶指针下标
private int top;
@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("栈不能为空");
}
this.array = (T[]) new Object[capacity];
this.top = 0;
}
/
* 压栈
*
* @param element 待添加元素
* @return 是否成功
*/
@Override
public boolean push(T element) {
if (isFull()) {
return false;
}
// array[top] = element;
// top++;
// 可简写成
array[top++] = element;
return true;
}
/
* 出栈
*
* @return 出栈元素
*/
@Override
public T pop() {
if (isEmpty()) {
return null;
}
// T element = array[top - 1];
// top--;
// return element;
// 可简写成
return array[--top];
}
/
* 查看栈顶
*
* @return 栈顶元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
return array[top - 1];
}
/
* 栈是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return top == 0;
}
/
* 栈是否满
*
* @return 结果
*/
@Override
public boolean isFull() {
return top == array.length;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = top;
@Override
public boolean hasNext() {
return p > 0;
}
@Override
public T next() {
// T element = array[p - 1];
// p--;
// return element;
// 可简写成
return array[--p];
}
};
}
}
package com.lzlg.study.algorithm.new2023.stack;
import java.util.Iterator;
/
* 使用链表实现栈
*
* @author lzlg
* 2023/7/23 10:21
*/
public class LinkedListStack<T> implements MyStack<T> {
// 栈容量
private final int capacity;
// 栈中实际元素的数量
private int size;
// 栈头节点(是哨兵节点)
private final Node<T> head;
public LinkedListStack(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("栈不能为空");
}
this.capacity = capacity;
this.size = 0;
this.head = new Node<>(null, null);
}
/
* 压栈
*
* @param element 待添加元素
* @return 是否成功
*/
@Override
public boolean push(T element) {
if (isFull()) {
return false;
}
// 让链表头部插入元素
head.next = new Node<>(element, head.next);
size++;
return true;
}
/
* 出栈
*
* @return 出栈元素
*/
@Override
public T pop() {
if (isEmpty()) {
return null;
}
Node<T> first = head.next;
// 移出头部节点
head.next = first.next;
size--;
return first.element;
}
/
* 查看栈顶
*
* @return 栈顶元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
return head.next.element;
}
/
* 栈是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
// return size == 0;
// 可写成
return head.next == null;
}
/
* 栈是否满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == capacity;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node<T> p = head.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public T next() {
T element = p.element;
p = p.next;
return element;
}
};
}
/
* 节点类
*/
private static class Node<T> {
T element;
Node<T> next;
public Node(T element, Node<T> next) {
this.element = element;
this.next = next;
}
}
}
package com.lzlg.study.algorithm.new2023.stack;
/
* 自定义栈接口
* 栈结构是只在一端进行操作的数据结构,此一端称为栈顶,另一端称为栈底
*
* @author lzlg
* 2023/7/23 10:10
*/
public interface MyStack<T> extends Iterable<T> {
/
* 压栈
*
* @param element 待添加元素
* @return 是否成功
*/
boolean push(T element);
/
* 出栈
*
* @return 出栈元素
*/
T pop();
/
* 查看栈顶
*
* @return 栈顶元素
*/
T peek();
/
* 栈是否为空
*
* @return 结果
*/
boolean isEmpty();
/
* 栈是否满
*
* @return 结果
*/
boolean isFull();
}
package com.lzlg.study.algorithm.new2023.stack;
/
* 测试栈
*
* @author lzlg
* 2023/7/23 10:20
*/
public class MyStackTest {
public static void main(String[] args) {
MyStack<Integer> stack = new LinkedListStack<>(3);
stack.push(1);
System.out.println(stack.peek());
stack.push(2);
System.out.println(stack.peek());
stack.push(3);
System.out.println(stack.peek());
stack.push(4);
System.out.println(stack.peek());
System.out.println("打印所有栈元素:");
for (Integer element : stack) {
System.out.println(element);
}
}
}
package com.lzlg.study.algorithm.new2023.stack.quiz;
import com.lzlg.study.algorithm.new2023.stack.LinkedListStack;
import com.lzlg.study.algorithm.new2023.stack.MyStack;
/
* 计算逆波兰表达式-后缀表达式
* 所有的输入都是合法的,无须担心异常情况
* 中缀表达式,就是平常使用的,如 a * b + c
* 后缀表达式,则是运算符写在数值后面的: a b * c +
*
* @author lzlg
* 2023/7/23 11:05
*/
public class CalculateReversePolishNotation {
/
* 计算逆波兰表达式
*
* @param tokens 表达式字符串数值
* @return 计算结果
*/
public static int calculate(String[] tokens) {
// 创建栈
MyStack<Integer> stack = new LinkedListStack<>(Integer.MAX_VALUE);
int right;
int left;
for (String token : tokens) {
switch (token) {
// 遇到运算符,从栈中弹出两个数字,进行运算
// 预算完成还需将结果压入栈中
case "+":
// 注意,第一个弹出的是运算符右边的
right = stack.pop();
left = stack.pop();
stack.push(left + right);
break;
case "-":
// 注意,第一个弹出的是运算符右边的
right = stack.pop();
left = stack.pop();
stack.push(left - right);
break;
case "*":
// 注意,第一个弹出的是运算符右边的
right = stack.pop();
left = stack.pop();
stack.push(left * right);
break;
case "/":
// 注意,第一个弹出的是运算符右边的
right = stack.pop();
left = stack.pop();
stack.push(left / right);
break;
default:
// 遇到数字,则压入栈中
stack.push(Integer.parseInt(token));
break;
}
}
// 最后栈顶保存的就是最终的运算结果
return stack.pop();
}
public static void main(String[] args) {
String[] tokens1 = {"2", "1", "+", "3", "*"};
System.out.println("计算结果为: " + calculate(tokens1));
String[] tokens2 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
System.out.println("计算结果为: " + calculate(tokens2));
}
}
package com.lzlg.study.algorithm.new2023.stack.quiz;
import com.lzlg.study.algorithm.new2023.stack.ArrayStack;
import com.lzlg.study.algorithm.new2023.stack.MyStack;
/
* 检测是否是有效的括号
* 一个字符串只有三种括号: {}, [], ()
* 假如字符串是({}),则是有效的,如果是([[则不是有效的
*
* @author lzlg
* 2023/7/23 10:44
*/
public class CheckValidBracket {
/
* 判断字符串是否有效
* 使用栈
* 遍历字符串种的字符,当遇到一个左括号时,压入栈一个相应的右括号
* 当遇到一个右括号时,和栈顶的括号进行比较,如果不相等,则字符串不是有效的
* 如果循环结束,栈不为空,则字符串不是有效的
*
* @param s 字符串
* @return 结果
*/
public static boolean isValid(String s) {
if (s == null || s.length() == 0 || s.length() == 1) {
return false;
}
int strLen = s.length();
MyStack<Character> stack = new ArrayStack<>(strLen);
for (int i = 0; i < strLen; i++) {
char c = s.charAt(i);
// 遇到一个左括号时,压入栈一个相应的右括号
if (c == '{') {
stack.push('}');
} else if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else {// 右括号情况
// 如果一开始遇到的就是右括号,此时栈为空且字符串一定无效
if (stack.isEmpty()) {
return false;
}
// 查看栈顶的括号是否相等
if (c == stack.peek()) {
// 如果相等,弹出栈顶括号
stack.pop();
} else {
// 如果不等,则直接返回false
return false;
}
}
}
// 循环结束,如果栈为空,则是有效的字符串
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("{()}"));
System.out.println(isValid("{]"));
System.out.println(isValid("{()["));
System.out.println(isValid("[(])"));
System.out.println(isValid(")("));
}
}
package com.lzlg.study.algorithm.new2023.stack.quiz;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import com.lzlg.study.algorithm.new2023.stack.ArrayStack;
import com.lzlg.study.algorithm.new2023.stack.MyStack;
import java.util.Iterator;
/
* 双栈模拟队列
* 一个栈是队头,负责出队
* 一个栈是队尾,负责入队
*
* @author lzlg
* 2023/7/23 12:19
*/
public class DoubleStackQueue<T> implements MyQueue<T> {
// 队头栈
private final MyStack<T> headStack;
// 队尾栈
private final MyStack<T> tailStack;
public DoubleStackQueue() {
headStack = new ArrayStack<>(Integer.MAX_VALUE);
tailStack = new ArrayStack<>(Integer.MAX_VALUE);
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// push到队尾的栈中
tailStack.push(element);
return false;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
// 如果队头栈为空,则从队尾弹出元素加入到队头
if (headStack.isEmpty()) {
while (!tailStack.isEmpty()) {
headStack.push(tailStack.pop());
}
}
return headStack.pop();
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队头栈为空,则从队尾弹出元素加入到队头
if (headStack.isEmpty()) {
while (!tailStack.isEmpty()) {
headStack.push(tailStack.pop());
}
}
return headStack.peek();
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return headStack.isEmpty() && tailStack.isEmpty();
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return headStack.isFull() || tailStack.isFull();
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return null;
}
}
package com.lzlg.study.algorithm.new2023.stack.quiz;
import com.lzlg.study.algorithm.new2023.stack.LinkedListStack;
import com.lzlg.study.algorithm.new2023.stack.MyStack;
/
* 中缀表达式转后缀表达式
* 中缀表达式: 1+2*3
* 后缀表达式: 123*+
*
* @author lzlg
* 2023/7/23 11:42
*/
public class InfixToSuffix {
/
* 中缀表达式转后缀表达式
* 遍历字符串中的字符
* 1.如果遇到不是运算符,则直接添加到新字符串中
* 2.如果遇到的是运算符:
* 1)如果栈为空,则直接入栈
* 2)如果栈不为空,则弹出比当前运算符相同或高的运算符并添加到新字符串中,然后当前运算符入栈
* 如果栈顶的运算符的优先级比当前运算符低,则直接入栈
* 3.如果遇到的是括号:
* 1)如果是左括号,直接入栈,左括号的优先级比其他运算符优先级低
* 2)如果是右括号,则弹出直到左括号的所有运算符并添加到新字符串中,且还要弹出左括号
*
* @param infix 中缀
* @return 后缀
*/
public static String infixToSuffix(String infix) {
MyStack<Character> stack = new LinkedListStack<>(Integer.MAX_VALUE);
// 新字符串
StringBuilder sb = new StringBuilder();
// 数组长度
int len = infix.length();
// 遍历字符串所有字符
for (int i = 0; i < len; i++) {
char c = infix.charAt(i);
switch (c) {
case '+':
case '-':
case '*':
case '/':
// 遇到运算符,如果栈为空,则直接入栈
if (stack.isEmpty()) {
stack.push(c);
} else {
// 如果当前运算符的优先级高于栈顶的,则直接入栈
if (priority(c) > priority(stack.peek())) {
stack.push(c);
} else {
// 把所有大于或等于当前运算符优先级的运算符弹出,并添加到新字符串中
while (!stack.isEmpty() && priority(c) <= priority(stack.peek())) {
sb.append(stack.pop());
}
// 循环退出后,把当前运算符入栈
stack.push(c);
}
}
break;
case '(':
// 遇到左括号,直接入栈
stack.push(c);
break;
case ')':
// 遇到右括号,则弹出直到左括号的运算符,并添加到新字符串中
while (stack.peek() != '(') {
sb.append(stack.pop());
}
// 循环退出,弹出栈中的左括号
stack.pop();
break;
default:
// 遇到的是数字,直接添加到系字符串中
sb.append(c);
break;
}
}
// 如果栈不为空,则弹出栈中所有运算符,并添加到新字符串中
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
/
* 获取优先级
*
* @param c 字符
* @return 优先级
*/
static int priority(char c) {
switch (c) {
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
case '(':
return 0;
default:
throw new IllegalArgumentException("非法运算符: " + c);
}
}
public static void main(String[] args) {
String infix = "(2+1)*3";
System.out.println("中缀表达式为: " + infix);
System.out.println("后缀表达式为: " + infixToSuffix(infix));
System.out.println("==================");
infix = "4+(9/5)";
System.out.println("中缀表达式为: " + infix);
System.out.println("后缀表达式为: " + infixToSuffix(infix));
System.out.println("==================");
infix = "(1+(9/5+1)*6+5)*1+0+4+2*3+8-7";
System.out.println("中缀表达式为: " + infix);
System.out.println("后缀表达式为: " + infixToSuffix(infix));
}
}
package com.lzlg.study.algorithm.new2023.stack.quiz;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import com.lzlg.study.algorithm.new2023.queue.SecondArrayQueue;
import com.lzlg.study.algorithm.new2023.stack.MyStack;
import java.util.Iterator;
/
* 使用单个队列模拟栈
* 在压栈时,如果队列为空,则直接添加
* 如果队列不为空,则先把新元素添加到队列中,然后把队列中旧元素依次出队再入队
*
* @author lzlg
* 2023/7/23 12:34
*/
public class SingleQueueStack<T> implements MyStack<T> {
// 队列
private final MyQueue<T> queue;
// 记录元素数量
private int size;
public SingleQueueStack() {
queue = new SecondArrayQueue<>(Integer.MAX_VALUE);
size = 0;
}
/
* 压栈
*
* @param element 待添加元素
* @return 是否成功
*/
@Override
public boolean push(T element) {
queue.offer(element);
// 循环次数是原先队列中的元素数量
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
size++;
return true;
}
/
* 出栈
*
* @return 出栈元素
*/
@Override
public T pop() {
size--;
return queue.poll();
}
/
* 查看栈顶
*
* @return 栈顶元素
*/
@Override
public T peek() {
return queue.peek();
}
/
* 栈是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return queue.isEmpty();
}
/
* 栈是否满
*
* @return 结果
*/
@Override
public boolean isFull() {
return queue.isFull();
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return null;
}
}
队列
package com.lzlg.study.algorithm.new2023.queue.block;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
/
* 使用双锁实现阻塞队列
* 这样添加和删除操作不会争抢同一把锁
*
* @author lzlg
* 2023/7/25 10:43
*/
public class DoubleLockBlockQueue<T> implements MyBlockQueue<T> {
// 元素数组
private final T[] array;
// 头指针下标
private int head;
// 尾指针下标
private int tail;
// 元素数量,这里使用AtomicInteger因为使用了两个锁
// 而poll和offer方法都会对size进行修改,因此会产生size修改不正确问题
private AtomicInteger size;
// 头部操作使用的锁
private final ReentrantLock headLock;
// 头部操作的等待条件
private final Condition headCondition;
// 尾部操作使用的锁
private final ReentrantLock tailLock;
// 尾部操作的等待条件
private final Condition tailCondition;
@SuppressWarnings("unchecked")
public DoubleLockBlockQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列容量不能为空");
}
array = (T[]) new Object[capacity];
head = 0;
tail = 0;
size = new AtomicInteger(0);
// 头部锁的初始化
headLock = new ReentrantLock();
headCondition = headLock.newCondition();
// 尾部锁的初始化
tailLock = new ReentrantLock();
tailCondition = tailLock.newCondition();
}
/
* 添加元素到尾部
*
* @param element 元素
* @throws InterruptedException 打断异常
*/
@Override
public void offer(T element) throws InterruptedException {
tailLock.lockInterruptibly();
// 记录size修改前的值
int prevSize;
try {
// 如果队列已满,则进入等待
while (isFull()) {
tailCondition.await();
}
// 添加元素到数组尾部
array[tail] = element;
// 如果尾部指针的下标+1等于数组长度,则置为0
if (++tail == array.length) {
tail = 0;
}
// 进行size的增加
prevSize = size.getAndIncrement();
// 错误1:不能直接写成下面的
// 因为headCondition配对的锁是headLock
// 需要在headLock的加锁和解锁上进行唤醒
// headCondition.signal();
// 错误2:会操作死锁
// 因为是在tailLock的加锁和解锁之间,需要写在tailLock的加锁和解锁之外
// headLock.lock();
// try {
// headCondition.signal();
// } finally {
// headLock.unlock();
// }
// 如果之前的size+1小于数组长度,则添加当前元素后
// 队列中还有空间进行添加操作,则继续唤醒其他添加操作的等待线程进行处理
if (prevSize + 1 < array.length) {
tailCondition.signal();
}
} finally {
tailLock.unlock();
}
// 唤醒头部操作等待的线程
// 如果是下面的代码,则性能不高,因为当队列不满不空时是无须进行如下操作的
// headLock.lock();
// try {
// headCondition.signal();
// } finally {
// headLock.unlock();
// }
// 如果size之前是0,则进行头部操作条件的唤醒
// 使用这个判断条件则性能较高,只在队列空时添加第一个元素时唤醒
if (prevSize == 0) {
headLock.lock();
try {
headCondition.signal();
} finally {
headLock.unlock();
}
}
}
/
* 添加元素到尾部,有时间限制
*
* @param element 元素
* @param timeout 等待时间
* @param unit 时间单位
* @throws InterruptedException 打断异常
*/
@Override
public boolean offer(T element, long timeout, TimeUnit unit) throws InterruptedException {
return false;
}
/
* 删除头部元素
*
* @return 头部元素
* @throws InterruptedException 打断异常
*/
@Override
public T poll() throws InterruptedException {
headLock.lockInterruptibly();
// 记录之前的size
int prevSize;
// 返回的元素
T element;
try {
// 如果队列已空,则进入等待
while (isEmpty()) {
headCondition.await();
}
// 取出头部元素
element = array[head];
// help GC
array[head] = null;
// 如果尾部指针head+1等于数组长度,则置为0
if (++head == array.length) {
head = 0;
}
// 进行size的减少
prevSize = size.getAndIncrement();
// 错误1:不能直接写成下面的
// 因为tailCondition配对的锁是tailLock
// 需要在tailLock的加锁和解锁上进行唤醒
// tailCondition.signal();
// 错误2:会操作死锁
// 因为是在headLock的加锁和解锁之间,需要写在headLock的加锁和解锁之外
// tailLock.lock();
// try {
// tailCondition.signal();
// } finally {
// tailLock.unlock();
// }
// 如果之前的size>1则取出当前元素后
// 队列中还有元素,则继续唤醒其他删除操作的等待线程进行处理
if (prevSize > 1) {
headCondition.signal();
}
} finally {
headLock.unlock();
}
// 唤醒尾部操作等待的线程
// 如果是下面的代码,则性能不高,因为当队列不满不空时是无须进行如下操作的
// tailLock.lock();
// try {
// tailCondition.signal();
// } finally {
// tailLock.unlock();
// }
// 如果size是数组长度,则进行尾部操作条件的唤醒
// 使用这个判断条件则性能较高,只在队列满时删除一个元素时唤醒
if (prevSize == array.length) {
tailLock.lock();
try {
tailCondition.signal();
} finally {
tailLock.unlock();
}
}
return element;
}
/
* 删除头部元素,有时间限制
*
* @param timeout 等待时间
* @param unit 时间单位
* @return 头部元素
* @throws InterruptedException 打断异常
*/
@Override
public T poll(long timeout, TimeUnit unit) throws InterruptedException {
return null;
}
/
* 队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size.get() == 0;
}
/
* 队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size.get() == array.length;
}
@Override
public String toString() {
return Arrays.toString(array);
}
}
package com.lzlg.study.algorithm.new2023.queue.block;
import java.util.concurrent.TimeUnit;
/
* 阻塞队列接口
*
* @author lzlg
* 2023/7/25 9:17
*/
public interface MyBlockQueue<T> {
/
* 添加元素到尾部
*
* @param element 元素
* @throws InterruptedException 打断异常
*/
void offer(T element) throws InterruptedException;
/
* 添加元素到尾部,有时间限制
*
* @param element 元素
* @param timeout 等待时间
* @param unit 时间单位
* @throws InterruptedException 打断异常
*/
boolean offer(T element, long timeout, TimeUnit unit) throws InterruptedException;
/
* 删除头部元素
*
* @return 头部元素
* @throws InterruptedException 打断异常
*/
T poll() throws InterruptedException;
/
* 删除头部元素,有时间限制
*
* @param timeout 等待时间
* @param unit 时间单位
* @return 头部元素
* @throws InterruptedException 打断异常
*/
T poll(long timeout, TimeUnit unit) throws InterruptedException;
/
* 队列是否为空
*
* @return 结果
*/
boolean isEmpty();
/
* 队列是否已满
*
* @return 结果
*/
boolean isFull();
}
package com.lzlg.study.algorithm.new2023.queue.block;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
/
* 单锁实现阻塞队列
* 使用单锁实现的缺点,在队列没满也没空时,添加和删除共用一把锁,造成不能同时进行
*
* @author lzlg
* 2023/7/25 9:21
*/
public class SingleLockBlockQueue<T> implements MyBlockQueue<T> {
// 数组
private final T[] array;
// 头指针下标
private int head;
// 尾指针下标
private int tail;
// 元素数量
private int size;
// 锁对象
private final ReentrantLock lock;
// 头部删除时条件
private final Condition headCondition;
// 尾部添加时条件
private final Condition tailCondition;
@SuppressWarnings("unchecked")
public SingleLockBlockQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = (T[]) new Object[capacity];
head = 0;
tail = 0;
size = 0;
lock = new ReentrantLock();
headCondition = lock.newCondition();
tailCondition = lock.newCondition();
}
/
* 添加元素到尾部
*
* @param element 元素
* @throws InterruptedException 打断异常
*/
@Override
public void offer(T element) throws InterruptedException {
// 使用可打断的锁
lock.lockInterruptibly();
try {
// 如果队列已满,则进行等待
// 使用while循环,防止假唤醒造成的错误
while (isFull()) {
tailCondition.await();
}
// 在数组尾部添加元素
array[tail] = element;
// 如果尾指针下标加1大于等于数组长度,则置为0
if (++tail == array.length) {
tail = 0;
}
size++;
// 唤醒删除poll操作的条件
headCondition.signal();
} finally {
lock.unlock();
}
}
/
* 添加元素到尾部,有时间限制
*
* @param element 元素
* @param timeout 等待时间
* @param unit 时间单位
* @throws InterruptedException 打断异常
*/
@Override
public boolean offer(T element, long timeout, TimeUnit unit) throws InterruptedException {
// 使用可打断的锁
lock.lockInterruptibly();
try {
// 如果队列已满,则进行等待
long time = unit.toNanos(timeout);
// 使用while循环,防止假唤醒造成的错误
while (isFull()) {
// 如果等待时间已经用完,还没获得锁,则返回false不再进行等待
if (time <= 0) {
return false;
}
// 这里使用有等待时间的方法
// 该方法的返回值是剩余等待的时间
// 需要更新等待时间,否则等待时间一直是offer方法传入的时间数
time = tailCondition.awaitNanos(time);
}
// 在数组尾部添加元素
array[tail] = element;
// 如果尾指针下标加1大于等于数组长度,则置为0
if (++tail == array.length) {
tail = 0;
}
size++;
// 唤醒删除poll操作的条件
headCondition.signal();
return true;
} finally {
lock.unlock();
}
}
/
* 删除头部元素
*
* @return 头部元素
* @throws InterruptedException 打断异常
*/
@Override
public T poll() throws InterruptedException {
// 使用可打断的锁
lock.lockInterruptibly();
try {
// 如果队列已空,则进行等待
while (isEmpty()) {
headCondition.await();
}
// 取出头部元素
T element = array[head];
// 如果head指针下标+1等于数组长度,则置为0
if (++head == array.length) {
head = 0;
}
size--;
// 通知offer方法可以进行添加元素
tailCondition.signal();
return element;
} finally {
lock.unlock();
}
}
/
* 删除头部元素,有时间限制
*
* @param timeout 等待时间
* @param unit 时间单位
* @return 头部元素
* @throws InterruptedException 打断异常
*/
@Override
public T poll(long timeout, TimeUnit unit) throws InterruptedException {
// 使用可打断的锁
lock.lockInterruptibly();
try {
// 等待时间
long time = unit.toNanos(timeout);
// 如果队列已空,则进行等待
while (isEmpty()) {
// 如果等待时间已过,还没获得锁,则返回null
if (time <= 0) {
return null;
}
// 等待时间需更新
time = headCondition.awaitNanos(time);
}
// 取出头部元素
T element = array[head];
// help GC
array[head] = null;
// 如果head指针下标+1等于数组长度,则置为0
if (++head == array.length) {
head = 0;
}
size--;
// 通知offer方法可以进行添加元素
tailCondition.signal();
return element;
} finally {
lock.unlock();
}
}
/
* 队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
@Override
public String toString() {
return Arrays.toString(array);
}
}
package com.lzlg.study.algorithm.new2023.queue.block;
/
* 测试阻塞队列
*
* @author lzlg
* 2023/7/25 8:55
*/
public class TestBlockQueue {
public static void main(String[] args) throws Exception {
MyBlockQueue<String> queue = new DoubleLockBlockQueue<>(3);
new Thread(() -> {
try {
queue.offer("work1");
System.out.println(queue);
queue.offer("work2");
System.out.println(queue);
queue.offer("work3");
System.out.println(queue);
// queue.offer("work4", 5000, TimeUnit.MILLISECONDS);
// System.out.println(queue);
queue.offer("work4");
System.out.println(queue);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "t1").start();
// TimeUnit.MILLISECONDS.sleep(2000);
queue.poll();
}
}
package com.lzlg.study.algorithm.new2023.queue;
import java.util.Iterator;
/
* 使用环形数组实现队列,环形数组是个逻辑结构
* 方式3的扩展: 使用头尾指针,但是头尾指针不再指向数组元素的下标,而是一直增长
* 使用位运算代替取模运算
* a = b * x + c (其中, a, b, c, x都是整数)
* 当除数b是2的幂时, 可通过按位与 a & (b - 1) 得出余数c
* 比如 13 = 4 * 3 + 1 而 4 = 2^2
* 13 的二进制形式是 0000 1101
* 4-1即3的二进制形式是 0000 0011
* 按位与后是 0000 0001 即等于1也就是余数
* <p>
* 如果要使用上面方法,就必须保证数组的长度是2的幂
*
* @author lzlg
* 2023/7/22 11:02
*/
public class FastThirdArrayQueue<T> implements MyQueue<T> {
// 存储元素的数组
private final T[] array;
// 头指针
private int head;
// 尾指针
private int tail;
@SuppressWarnings("unchecked")
public FastThirdArrayQueue(int capacity) {
// 1.方式1: 传入的容量必须是2的幂,2的幂与其减1的数字按位与等于0
// 比如8的二进制是 0000 1000
// 8-1即7的二进制是 0000 0111
// 按位与则是 0000 0000 即是0
if ((capacity & (capacity - 1)) != 0) {
throw new IllegalArgumentException("容量必须是2的幂");
}
// 2.方式2: 找到比传入的capacity大的2的幂
// 使用对数运算,使用对数的换底公式
// 需要减1,防止因为是capacity原本就是2的幂造成结果不正确
// int n = ((int) (Math.log10(capacity - 1) / Math.log10(2))) + 1;
// 创建数组,注意数组长度是容量
array = (T[]) new Object[capacity];
head = 0;
tail = 0;
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// 如果队列已满,则不能添加
if (isFull()) {
return false;
}
// 使用(尾指针&数组长度-1)下标来存储元素
array[tail & array.length - 1] = element;
// 保证尾指针增长
tail++;
return true;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出(头指针&数组长度-1)下标的元素
T element = array[head & array.length - 1];
// 保证头指针增长
head++;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出(头指针&数组长度-1)下标的元素
return array[head & array.length - 1];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
// 当头尾相等时,则队列为空
return head == tail;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
// 头尾的差值等于数组长度时,则队列已满
return (tail - head) == array.length;
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
// 使用指针p辅助访问
int p = head;
@Override
public boolean hasNext() {
// 当p等于尾指针下标时,则已经访问完
return p != tail;
}
@Override
public T next() {
T element = array[p & array.length - 1];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue;
import java.util.Iterator;
/
* 使用环形数组实现队列,环形数组是个逻辑结构
* 使用的是方式1: 使用头尾指针,并舍弃一个数组位置作为判空和判满的条件依据
*
* @author lzlg
* 2023/7/22 11:02
*/
public class FirstArrayQueue<T> implements MyQueue<T> {
// 存储元素的数组
private final T[] array;
// 头指针下标
private int head;
// 尾指针下标
private int tail;
@SuppressWarnings("unchecked")
public FirstArrayQueue(int capacity) {
// 创建数组,注意数组长度是容量+1,要留一个位置作为判空和判满的条件依据
array = (T[]) new Object[capacity + 1];
head = 0;
tail = 0;
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// 如果队列已满,则不能添加
if (isFull()) {
return false;
}
// 使用尾指针下标存储元素
array[tail] = element;
// 移动尾指针,为防止数组越界,故%上数组长度
tail = (tail + 1) % array.length;
return true;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出头指针下标的元素
T element = array[head];
// 移动头指针,为防止数组越界,故%上数组长度
head = (head + 1) % array.length;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出头指针下标的元素
return array[head];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return head == tail;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return (tail + 1) % array.length == head;
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
// 使用指针p辅助访问
int p = head;
@Override
public boolean hasNext() {
// 当p等于尾指针下标时,则已经访问完
return p != tail;
}
@Override
public T next() {
T element = array[p];
p = (p + 1) % array.length;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue;
import java.util.Iterator;
/
* 使用单向循环哨兵链表实现队列
*
* @author lzlg
* 2023/7/22 10:05
*/
public class MyLinkedListQueue<T> implements MyQueue<T> {
// 头指针,始终指向哨兵节点
private final Node<T> head;
// 尾指针,指向最新插入的节点
private Node<T> tail;
// 队列元素个数
private int size;
// 队列容量
private final int capacity;
public MyLinkedListQueue() {
this(Integer.MAX_VALUE);
}
public MyLinkedListQueue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("队列不能为空");
}
this.capacity = capacity;
this.size = 0;
// 创建头节点,作为哨兵节点
this.head = new Node<>(null, null);
// 将尾节点指向头节点
this.tail = head;
// 将尾节点的next指向头节点,构成环
tail.next = head;
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// 如果队列已满,则不能添加
if (isFull()) {
return false;
}
// 创建新节点,新节点的next指向tail,新节点将作为尾节点
Node<T> added = new Node<>(element, head);
// 将新节点添加到尾部
tail.next = added;
// 移动尾指针,将新节点作为新的尾节点
tail = added;
size++;
return true;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
if (isEmpty()) {
return null;
}
// 找到第一个节点(非哨兵)
Node<T> first = head.next;
// 因为要删除,因此移动head的next指向first的next
head.next = first.next;
// 考虑到一个元素的情况,此时删除的是队尾节点,因此还需移动尾指针
if (first == tail) {
tail = head;
}
size--;
// 返回元素
return first.element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队列为空,则返回null,否则返回队头的next中的元素
return isEmpty() ? null : head.next.element;
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return head == tail;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == capacity;
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node<T> p = head.next;
@Override
public boolean hasNext() {
return p != head;
}
@Override
public T next() {
T element = p.element;
p = p.next;
return element;
}
};
}
/
* 链表节点类
*/
private static class Node<T> {
// 节点元素值
T element;
// 下个节点指针
Node<T> next;
public Node(T element, Node<T> next) {
this.element = element;
this.next = next;
}
}
}
package com.lzlg.study.algorithm.new2023.queue;
/
* 自定义队列接口
* 插入的一端为队尾,删除的一端为队头
*
* @author lzlg
* 2023/7/22 10:00
*/
public interface MyQueue<T> extends Iterable<T> {
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
boolean offer(T element);
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
T poll();
/
* 查看队头元素
*
* @return 队头元素
*/
T peek();
/
* 判断队列是否为空
*
* @return 结果
*/
boolean isEmpty();
/
* 判断队列是否已满
*
* @return 结果
*/
boolean isFull();
}
package com.lzlg.study.algorithm.new2023.queue.priority;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import java.util.Iterator;
/
* 使用大顶堆实现优先级队列
* 大顶堆的特性: 父节点的值总比左右孩子的大
*
* @author lzlg
* 2023/7/24 11:23
*/
@SuppressWarnings("unchecked")
public class BigHeapPriorityQueue<T extends Priority> implements MyQueue<T> {
// 数组
private final Priority[] array;
// 元素数量
private int size;
public BigHeapPriorityQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = new Priority[capacity];
size = 0;
}
/
* 队尾插入
* 一个child下标指向数组中下标为size的位置,然后开始调整堆
* 1.比较父节点的优先级,如果大于父节点的优先级,则父节点的下标下移到child指定的下标
* 2.一直循环上述步骤,直到child为0或者遇到不大于父节点优先级时停止
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
if (isFull()) {
return false;
}
// child指针位置,注意添加后size还要++,这里合并写在一起了
int child = size++;
// 找到父节点下标
int parent = (child - 1) >>> 1;
// 如果child>0且父节点的优先级小于待插入元素节点的优先级
while (child > 0 && array[parent].priority() < element.priority()) {
// 父节点的值赋值给子节点
array[child] = array[parent];
// 变更子节点和父节点
child = parent;
parent = (child - 1) >>> 1;
}
// 循环结束,此时child指针指向的是待插入元素的下标
array[child] = element;
return true;
}
/
* 队头去除元素,并删除
* 步骤如下:
* 1.先把数组的第一个元素和最后一个元素交换
* 2.移动size,即size--,优先级最大的则被移出(即返回值)
* 3.开始调整堆
* 1)从第一个元素(父节点)开始比较它的左右子节点的优先级
* 2)如果父节点的优先级最大,则不用调整
* 3)否则从左右子节点中选出优先级最大的和父节点进行交换
* 4)直到到达数组尾部
*
* @return 队头元素
*/
@Override
public T poll() {
if (isEmpty()) {
return null;
}
// 交换数组第一个和最后一个,此时最后一个元素是优先级最大的元素
swap(0, size - 1);
// 减少元素数量
size--;
// 返回的优先级最大的元素
T element = (T) array[size];
// help GC
array[size] = null;
// 从根节点开始调整堆
heapAdjust(0);
return element;
}
/
* 调整大顶堆
*
* @param parent 父节点下标
*/
private void heapAdjust(int parent) {
// 左孩子
int leftChild = 2 * parent + 1;
// 右孩子
int rightChild = leftChild + 1;
// 最大优先级
int max = parent;
if (leftChild < size && array[leftChild].priority() > array[max].priority()) {
max = leftChild;
}
if (rightChild < size && array[rightChild].priority() > array[max].priority()) {
max = rightChild;
}
// 如果最大的不是父节点,则进行交换
if (max != parent) {
swap(max, parent);
// 再次递归调整剩下的堆
heapAdjust(max);
}
}
/
* 使用临时变量交换
*
* @param i 下标1
* @param j 下标2
*/
private void swap(int i, int j) {
Priority temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
// 数组中下标0存储的是优先级最大的
return (T) array[0];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = 0;
@Override
public boolean hasNext() {
return p < size;
}
@Override
public T next() {
T element = (T) array[p];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue.priority;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import java.util.Iterator;
/
* 使用无序数组实现优先级队列
*
* @author lzlg
* 2023/7/24 11:23
*/
@SuppressWarnings("unchecked")
public class DisorderPriorityQueue<T extends Priority> implements MyQueue<T> {
// 数组
private final Priority[] array;
// 元素数量
private int size;
public DisorderPriorityQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = new Priority[capacity];
size = 0;
}
/
* 队尾插入,由于是无序的,直接在数组尾部插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
if (isFull()) {
return false;
}
array[size++] = element;
return true;
}
/
* 队头去除元素,并删除
* 要先找到优先级最大的元素下标
* 然后删除此元素
*
* @return 队头元素
*/
@Override
public T poll() {
if (isEmpty()) {
return null;
}
// 找到优先级最大的元素下标
int maxPriorityIndex = maxPriorityIndex();
T element = (T) array[maxPriorityIndex];
// 删除此元素
remove(maxPriorityIndex);
return element;
}
/
* 删除指定下标的元素
*
* @param index 下标
*/
private void remove(int index) {
// 如果在数组的最后一个,则不用移动元素
if (index < size - 1) {
// 移动数组元素
System.arraycopy(array, index + 1, array, index, size - 1 - index);
}
size--;
// help GC
// 这里最后的元素置空就可以了
// 在删除过程中会移动元素将优先级最高的元素覆盖了
array[size] = null;
}
/
* 获取最大优先级的数组下标
*
* @return 数组下标
*/
private int maxPriorityIndex() {
int max = 0;
for (int i = 1; i < size; i++) {
// 如果有优先级比max大的,则赋值给max
if (array[i].priority() > array[max].priority()) {
max = i;
}
}
return max;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
// 找到优先级最大的元素下标
int maxPriorityIndex = maxPriorityIndex();
return (T) array[maxPriorityIndex];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = 0;
@Override
public boolean hasNext() {
return p < size;
}
@Override
public T next() {
T element = (T) array[p];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue.priority;
/
* 使用小顶堆实现合并多个升序的链表
*
* @author lzlg
* 2023/7/24 14:33
*/
public class MergeMultipleSortedLinkedList {
/
* 使用小顶堆实现合并多个升序的链表
*
* @param nodes 链表数组
* @return 新链表
*/
public static Node merge(Node[] nodes) {
// 使用小顶堆的优先级队列
SmallHeapPriorityQueue<Node> queue = new SmallHeapPriorityQueue<>(nodes.length);
// 将节点的第一个节点加入到队列中
for (Node node : nodes) {
if (node != null) {
queue.offer(node);
}
}
// 使用哨兵节点
Node sentinel = new Node(-1, null);
// 总指向新链表最后一个元素的指针
Node p = sentinel;
while (!queue.isEmpty()) {
// 把最小的取出,加入新链表的最后
Node min = queue.poll();
p.next = min;
// 指针p始终指向新链表最后一个元素
p = min;
// 添加旧链表的下一个元素到队列中
if (min.next != null) {
queue.offer(min.next);
}
}
return sentinel.next;
}
public static void main(String[] args) {
Node node1 = new Node(1, new Node(3, new Node(4, null)));
Node node2 = new Node(2, new Node(5, new Node(6, null)));
Node node3 = new Node(1, new Node(4, new Node(7, null)));
Node[] nodes = {node1, node2, node3};
Node node = merge(nodes);
printNode(node);
}
private static void printNode(Node node) {
Node p = node;
while (p != null) {
System.out.println(p);
p = p.next;
}
}
/
* 节点类
*/
private static class Node implements Priority {
private int value;
private Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
/
* 返回优先级数值
*
* @return 优先级
*/
@Override
public int priority() {
return value;
}
@Override
public String toString() {
return "Node[" + value + "]";
}
}
}
package com.lzlg.study.algorithm.new2023.queue.priority;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import java.util.Iterator;
/
* 使用有序数组实现优先级队列
*
* @author lzlg
* 2023/7/24 11:23
*/
@SuppressWarnings("unchecked")
public class OrderPriorityQueue<T extends Priority> implements MyQueue<T> {
// 数组
private final Priority[] array;
// 元素数量
private int size;
public OrderPriorityQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = new Priority[capacity];
size = 0;
}
/
* 队尾插入,因为是有序的,因此要找到插入的位置下标
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
if (isFull()) {
return false;
}
// 从后往前遍历
int i = size - 1;
// 找到小于等于待插入元素优先级的下标
while (i >= 0 && array[i].priority() > element.priority()) {
// 移动数组元素
array[i + 1] = array[i];
i--;
}
// 找到后,进行插入
array[i + 1] = element;
size++;
return true;
}
/
* 队头去除元素,并删除
* 因为是有序的,因此直接删除数组的最后一个即可
*
* @return 队头元素
*/
@Override
public T poll() {
if (isEmpty()) {
return null;
}
T element = (T) array[size - 1];
size--;
// help GC
array[size] = null;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
return (T) array[size - 1];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = 0;
@Override
public boolean hasNext() {
return p < size;
}
@Override
public T next() {
T element = (T) array[p];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue.priority;
/
* 优先级接口
*
* @author lzlg
* 2023/7/24 11:23
*/
public interface Priority {
/
* 返回优先级数值
*
* @return 优先级
*/
int priority();
}
package com.lzlg.study.algorithm.new2023.queue.priority;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import java.util.Iterator;
/
* 使用小顶堆实现优先级队列
* 小顶堆的特性: 父节点的值总比左右孩子的小
*
* @author lzlg
* 2023/7/24 11:23
*/
@SuppressWarnings("unchecked")
public class SmallHeapPriorityQueue<T extends Priority> implements MyQueue<T> {
// 数组
private final Priority[] array;
// 元素数量
private int size;
public SmallHeapPriorityQueue(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = new Priority[capacity];
size = 0;
}
/
* 队尾插入
* 一个child下标指向数组中下标为size的位置,然后开始调整堆
* 1.比较父节点的优先级,如果小于父节点的优先级,则父节点的下标下移到child指定的下标
* 2.一直循环上述步骤,直到child为0或者遇到不小于父节点优先级时停止
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
if (isFull()) {
return false;
}
// child指针位置,注意添加后size还要++,这里合并写在一起了
int child = size++;
// 找到父节点下标
int parent = (child - 1) >>> 1;
// 如果child>0且父节点的优先级大于待插入元素节点的优先级
while (child > 0 && array[parent].priority() > element.priority()) {
// 父节点的值赋值给子节点
array[child] = array[parent];
// 变更子节点和父节点
child = parent;
parent = (child - 1) >>> 1;
}
// 循环结束,此时child指针指向的是待插入元素的下标
array[child] = element;
return true;
}
/
* 队头去除元素,并删除
* 步骤如下:
* 1.先把数组的第一个元素和最后一个元素交换
* 2.移动size,即size--,优先级最小的则被移出(即返回值)
* 3.开始调整堆
* 1)从第一个元素(父节点)开始比较它的左右子节点的优先级
* 2)如果父节点的优先级最小,则不用调整
* 3)否则从左右子节点中选出优先级最小的和父节点进行交换
* 4)直到到达数组尾部
*
* @return 队头元素
*/
@Override
public T poll() {
if (isEmpty()) {
return null;
}
// 交换数组第一个和最后一个,此时最后一个元素是优先级最大的元素
swap(0, size - 1);
// 减少元素数量
size--;
// 返回的优先级最大的元素
T element = (T) array[size];
// help GC
array[size] = null;
// 从根节点开始调整堆
heapAdjust(0);
return element;
}
/
* 调整大顶堆
*
* @param parent 父节点下标
*/
private void heapAdjust(int parent) {
// 左孩子
int leftChild = 2 * parent + 1;
// 右孩子
int rightChild = leftChild + 1;
// 最小优先级
int min = parent;
if (leftChild < size && array[leftChild].priority() < array[min].priority()) {
min = leftChild;
}
if (rightChild < size && array[rightChild].priority() < array[min].priority()) {
min = rightChild;
}
// 如果最小的不是父节点,则进行交换
if (min != parent) {
swap(min, parent);
// 再次递归调整剩下的堆
heapAdjust(min);
}
}
/
* 使用临时变量交换
*
* @param i 下标1
* @param j 下标2
*/
private void swap(int i, int j) {
Priority temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
if (isEmpty()) {
return null;
}
// 数组中下标0存储的是优先级最大的
return (T) array[0];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = 0;
@Override
public boolean hasNext() {
return p < size;
}
@Override
public T next() {
T element = (T) array[p];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue.priority;
/
* 测试优先级队列
*
* @author lzlg
* 2023/7/24 11:53
*/
public class TestPriorityQueue {
public static void main(String[] args) {
BigHeapPriorityQueue<Entry> queue = new BigHeapPriorityQueue<>(4);
queue.offer(new Entry("work1", 5));
queue.offer(new Entry("work2", 2));
queue.offer(new Entry("work3", 8));
queue.offer(new Entry("work4", 1));
System.out.println("=================");
for (Entry entry : queue) {
System.out.println(entry);
}
System.out.println("=================");
System.out.println(queue.poll());
System.out.println("=================");
System.out.println(queue.peek());
}
/
* 实体类
*/
private static class Entry implements Priority {
private final String value;
private final int priority;
public Entry(String value, int priority) {
this.value = value;
this.priority = priority;
}
/
* 返回优先级数值
*
* @return 优先级
*/
@Override
public int priority() {
return priority;
}
@Override
public String toString() {
return value + ", 优先级: " + priority;
}
}
}
package com.lzlg.study.algorithm.new2023.queue;
import java.util.Iterator;
/
* 使用环形数组实现队列,环形数组是个逻辑结构
* 使用的是方式2: 使用头尾指针,使用一个表示数组实际元素数量的size
*
* @author lzlg
* 2023/7/22 11:02
*/
public class SecondArrayQueue<T> implements MyQueue<T> {
// 存储元素的数组
private final T[] array;
// 头指针下标
private int head;
// 尾指针下标
private int tail;
// 表示数组元素的实际数量
private int size;
@SuppressWarnings("unchecked")
public SecondArrayQueue(int capacity) {
// 创建数组,注意数组长度是容量,因为使用了size
array = (T[]) new Object[capacity];
head = 0;
tail = 0;
size = 0;
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// 如果队列已满,则不能添加
if (isFull()) {
return false;
}
// 使用尾指针下标存储元素
array[tail] = element;
// 移动尾指针,为防止数组越界,故%上数组长度
tail = (tail + 1) % array.length;
size++;
return true;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出头指针下标的元素
T element = array[head];
// 移动头指针,为防止数组越界,故%上数组长度
head = (head + 1) % array.length;
size--;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出头指针下标的元素
return array[head];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == array.length;
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
// 使用指针p辅助访问
int p = head;
// 使用计数器
int count = 0;
@Override
public boolean hasNext() {
// 计数器小于size时,则还能访问
return count < size;
}
@Override
public T next() {
T element = array[p];
p = (p + 1) % array.length;
// 访问一个,则计数器增加
count++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue;
/
* @author lzlg
* 2023/7/22 10:22
*/
public class TestMyQueue {
public static void main(String[] args) {
MyQueue<Integer> queue = new ThirdArrayQueue<>(2);
queue.offer(1);
System.out.println(queue.peek());
queue.offer(2);
queue.poll();
queue.offer(3);
System.out.println("=====删除队头元素====");
System.out.println(queue.peek());
System.out.println("=======队列元素======");
for (Integer ele : queue) {
System.out.println(ele);
}
}
/
* 测试链表实现的队列
*/
private static void testLinkedListQueue() {
MyQueue<Integer> queue = new MyLinkedListQueue<>(2);
queue.offer(1);
System.out.println(queue.peek());
queue.offer(2);
queue.poll();
queue.offer(3);
System.out.println("=====删除队头元素====");
System.out.println(queue.peek());
System.out.println("=======队列元素======");
for (Integer ele : queue) {
System.out.println(ele);
}
}
}```
```java
package com.lzlg.study.algorithm.new2023.queue;
import java.util.Iterator;
/
* 使用环形数组实现队列,环形数组是个逻辑结构
* 使用的是方式3: 使用头尾指针,但是头尾指针不再指向数组元素的下标,而是一直增长
* 这种方式有可能导致head和tail超出int的最大值范围,使用long类型的头尾指针比较好
*
* @author lzlg
* 2023/7/22 11:02
*/
public class ThirdArrayQueue<T> implements MyQueue<T> {
// 存储元素的数组
private final T[] array;
// 头指针
private int head;
// 尾指针
private int tail;
@SuppressWarnings("unchecked")
public ThirdArrayQueue(int capacity) {
// 创建数组,注意数组长度是容量
array = (T[]) new Object[capacity];
head = 0;
tail = 0;
}
/
* 队尾插入
*
* @param element 待插入的元素
* @return 是否插入成功
*/
@Override
public boolean offer(T element) {
// 如果队列已满,则不能添加
if (isFull()) {
return false;
}
// 使用(尾指针%数组长度)下标来存储元素
array[tail % array.length] = element;
// 保证尾指针增长
tail++;
return true;
}
/
* 队头去除元素,并删除
*
* @return 队头元素
*/
@Override
public T poll() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出(头指针%数组长度)下标的元素
T element = array[head % array.length];
// 保证头指针增长
head++;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peek() {
// 如果队列已空,则返回null
if (isEmpty()) {
return null;
}
// 取出(头指针%数组长度)下标的元素
return array[head % array.length];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
// 当头尾相等时,则队列为空
return head == tail;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
// 头尾的差值等于数组长度时,则队列已满
return (tail - head) == array.length;
}
/
* 迭代器实现
*
* @return 迭代器
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
// 使用指针p辅助访问
int p = head;
@Override
public boolean hasNext() {
// 当p等于尾指针下标时,则已经访问完
return p != tail;
}
@Override
public T next() {
T element = array[p % array.length];
p++;
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.queue;
import java.util.ArrayList;
import java.util.List;
/
* 队列使用: 二叉树的层序遍历
* 如果有如下二叉树
* 1
* /\
* 2 3
* /\ /\
* 4 5 6 7
* 则层序遍历的结果为1, 2, 3, 4, 5, 6, 7
*
* @author lzlg
* 2023/7/22 12:17
*/
public class TreeLevelForEachQuiz {
/
* 层序遍历二叉树
* 使用一个队列
* 1.开始时,将根节点加入队列
* 2.开始循环,取出队列的头部节点,访问此节点的元素
* 3.判断该节点如果有左右孩子,则分别加入队列中
* 4.直到队列为空,退出循环
*
* @param root 二叉树根节点
*/
public static void levelLoopTree(TreeNode root) {
// 创建队列
MyQueue<TreeNode> queue = new MyLinkedListQueue<>();
// 将根节点加入队列
queue.offer(root);
while (!queue.isEmpty()) {
// 取出节点
TreeNode node = queue.poll();
// 访问该节点
System.out.println(node);
// 如果有左右孩子节点,则分别加入队列中
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/
* 将二叉树的每层变成一个列表,并把这所有列表组合成一个列表返回
*
* @param root 二叉树根节点
* @return 层序列表
*/
public static List<List<Integer>> toLevelList(TreeNode root) {
// 返回结果
List<List<Integer>> result = new ArrayList<>();
// 当二叉树为空,则直接返回空list
if (root == null) {
return result;
}
// 创建队列
MyQueue<TreeNode> queue = new MyLinkedListQueue<>();
// 将根节点加入队列
queue.offer(root);
// 当前二叉树层的节点数量,初始为1,因为先遍历根节点,根节点这一层只有一个
int currentLevelNodeCount = 1;
while (!queue.isEmpty()) {
// 下个层序的节点数量
int nextLevelNodeCount = 0;
// 当前层序的列表
List<Integer> levelList = new ArrayList<>();
// 根据当前层的节点数量分别取出
for (int i = 0; i < currentLevelNodeCount; i++) {
// 取出节点
TreeNode node = queue.poll();
// 将此节点的值加入到当前层序的列表
levelList.add(node.value);
// 如果有左右孩子节点,则分别加入队列中
if (node.left != null) {
queue.offer(node.left);
// 下个层序的节点数量增加
nextLevelNodeCount++;
}
if (node.right != null) {
queue.offer(node.right);
// 下个层序的节点数量增加
nextLevelNodeCount++;
}
}
// 当前层序遍历完成,则添加到返回结果中
result.add(levelList);
// 切换当前层序的数量为下个层序的数量,进入下次循环
// 下次循环就是下个层次的遍历了
currentLevelNodeCount = nextLevelNodeCount;
}
// 返回最终结果
return result;
}
public static void main(String[] args) {
// 创建二叉树
TreeNode root = new TreeNode(
1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, new TreeNode(6), new TreeNode(7))
);
levelLoopTree(root);
System.out.println("=======层序遍历的列表=======");
System.out.println(toLevelList(root));
}
/
* 二叉树节点类
*/
private static class TreeNode {
// 节点值
int value;
// 节点左孩子
private TreeNode left;
// 节点右孩子
private TreeNode right;
public TreeNode(int value) {
this.value = value;
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
}
双端队列
package com.lzlg.study.algorithm.new2023.deque;
import java.util.Iterator;
/
* 使用数组实现双端队列
* 使用两个指针,头指针,尾指针
* 此方式会牺牲一个数组位置
* <p>
* 创建后情况:
* 指针 h
* t
* 下标: 0 1 2 3
* <p>
* 头部添加一个元素a:
* 指针 h
* t
* 下标: 0 1 2 3
* 元素: a
* <p>
* 尾部添加一个元素b:
* 指针 h
* t
* 下标: 0 1 2 3
* 元素: b a
*
* @author lzlg
* 2023/7/24 9:59
*/
public class FirstArrayDeque<T> implements MyDeque<T> {
// 头指针
private int head;
// 尾指针
private int tail;
// 存储元素的数组
private final T[] array;
@SuppressWarnings("unchecked")
public FirstArrayDeque(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
array = (T[]) new Object[capacity + 1];
head = 0;
tail = 0;
}
/
* 增加索引的方法
*
* @param index 当前索引
* @param length 数组长度
* @return 增加后的索引
*/
private int indexIncrease(int index, int length) {
// 如果索引+1大于等于数组长度,则返回下标为0的位置(数组头)
if (index + 1 >= length) {
return 0;
}
// 否则直接加1
return index + 1;
}
/
* 减少索引的方法
*
* @param index 当前索引
* @param length 数组长度
* @return 减少后的索引
*/
private int indexDecrease(int index, int length) {
// 如果索引-1小于0,则返回下标为数组长度-1的位置(数组尾)
if (index - 1 < 0) {
return length - 1;
}
return index - 1;
}
/
* 队头添加元素
* 先head减少,然后根据head指针下标添加到数组中
*
* @param element 元素
* @return 结果
*/
@Override
public boolean offerFirst(T element) {
if (isFull()) {
return false;
}
// head指针减少
head = indexDecrease(head, array.length);
array[head] = element;
return true;
}
/
* 队尾添加元素
* 把元素添加到tail指向的下标位置,然后tail增加
*
* @param element 元素
* @return 结果
*/
@Override
public boolean offerLast(T element) {
if (isFull()) {
return false;
}
// 添加元素
array[tail] = element;
// 增加tail下标
tail = indexIncrease(tail, array.length);
return true;
}
/
* 删除队头元素
* 先取出头部元素,然后增加head
*
* @return 队头元素
*/
@Override
public T pollFirst() {
if (isEmpty()) {
return null;
}
// 先取出头部元素
T element = array[head];
// help GC
array[head] = null;
head = indexIncrease(head, array.length);
return element;
}
/
* 删除队尾元素
* 先减少tail,然后取出元素
*
* @return 队头元素
*/
@Override
public T pollLast() {
if (isEmpty()) {
return null;
}
tail = indexDecrease(tail, array.length);
T element = array[tail];
// help GC
array[tail] = null;
return element;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peekFirst() {
if (isEmpty()) {
return null;
}
return array[head];
}
/
* 查看队尾元素
*
* @return 队头元素
*/
@Override
public T peekLast() {
if (isEmpty()) {
return null;
}
return array[indexDecrease(tail, array.length)];
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return head == tail;
}
/
* 判断队列是否已满
* 分为三种情况:
* 1.tail>head时,此时判断tail-head是否等于数组长度-1
* 2.tail<head时,此时判断head-tail是否等于1
* 3.tail=head时,队列为空
*
* @return 结果
*/
@Override
public boolean isFull() {
if (tail > head) {
return tail - head == array.length - 1;
}
if (tail < head) {
return head - tail == 1;
}
return false;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public T next() {
T element = array[p];
p = indexIncrease(p, array.length);
return element;
}
};
}
}
package com.lzlg.study.algorithm.new2023.deque;
import java.util.Iterator;
/
* 使用双向环形链表实现双端队列
* 使用哨兵节点作为头和尾节点
*
* @author lzlg
* 2023/7/24 10:23
*/
public class LinkedListDeque<T> implements MyDeque<T> {
// 哨兵节点
private final Node<T> sentinel;
// 队列容量
private int capacity;
// 元素数量
private int size;
public LinkedListDeque(int capacity) {
if (capacity < 1) {
throw new IllegalArgumentException("队列不能为空");
}
this.capacity = capacity;
size = 0;
// 初始化哨兵节点
sentinel = new Node<>(null, null, null);
// 头节点(还是哨兵节点)的是哨兵节点
sentinel.next = sentinel;
// 尾节点(还是哨兵节点)的是哨兵节点
sentinel.prev = sentinel;
}
/
* 队头添加元素
*
* @param element 元素
* @return 结果
*/
@Override
public boolean offerFirst(T element) {
if (isFull()) {
return false;
}
// 新节点的前一个节点是哨兵节点
Node<T> prev = sentinel;
// 新节点的后一个节点是哨兵节点的next
Node<T> next = sentinel.next;
// 创建新节点
Node<T> added = new Node<>(prev, element, next);
// 前节点的next是新节点
prev.next = added;
// 后节点的prev是新节点
next.prev = added;
size++;
return true;
}
/
* 队尾添加元素
*
* @param element 元素
* @return 结果
*/
@Override
public boolean offerLast(T element) {
if (isFull()) {
return false;
}
// 新节点的前一个节点是尾节点的prev
Node<T> prev = sentinel.prev;
// 新节点的后一个节点是尾节点
Node<T> next = sentinel;
// 创建新节点
Node<T> added = new Node<>(prev, element, next);
// 前节点的next是新节点
prev.next = added;
// 后节点的prev是新节点
next.prev = added;
size++;
return true;
}
/
* 删除队头元素
*
* @return 队头元素
*/
@Override
public T pollFirst() {
if (isEmpty()) {
return null;
}
// 待删除节点的前一个节点
Node<T> prev = sentinel;
// 待删除节点是哨兵节点的next
Node<T> removed = sentinel.next;
// 待删除记得的后一个节点
Node<T> next = removed.next;
// 删除待删除节点
prev.next = next;
next.prev = prev;
// helpGC
removed.prev = null;
removed.next = null;
size--;
return removed.value;
}
/
* 删除队尾元素
*
* @return 队头元素
*/
@Override
public T pollLast() {
if (isEmpty()) {
return null;
}
// 待删除节点的下一个节点
Node<T> next = sentinel;
// 待删除节点是尾节点的前一个节点
Node<T> removed = sentinel.prev;
// 待删除节点的上一个节点
Node<T> prev = removed.prev;
// 删除待删除节点
prev.next = next;
next.prev = prev;
// helpGC
removed.prev = null;
removed.next = null;
size--;
return removed.value;
}
/
* 查看队头元素
*
* @return 队头元素
*/
@Override
public T peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.next.value;
}
/
* 查看队尾元素
*
* @return 队头元素
*/
@Override
public T peekLast() {
if (isEmpty()) {
return null;
}
return sentinel.prev.value;
}
/
* 判断队列是否为空
*
* @return 结果
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/
* 判断队列是否已满
*
* @return 结果
*/
@Override
public boolean isFull() {
return size == capacity;
}
/
* Returns an iterator over elements of type {@code T}.
*
* @return an Iterator.
*/
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node<T> p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public T next() {
T element = p.value;
p = p.next;
return element;
}
};
}
/
* 节点类
*/
private static class Node<T> {
// 前节点指针
private Node<T> prev;
// 元素值
private T value;
// 后节点指针
private Node<T> next;
public Node(Node<T> prev, T value, Node<T> next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
}
package com.lzlg.study.algorithm.new2023.deque;
/
* 双端队列
* 能在两头进行添加删除操作的队列
*
* @author lzlg
* 2023/7/24 9:54
*/
public interface MyDeque<T> extends Iterable<T> {
/
* 队头添加元素
*
* @param element 元素
* @return 结果
*/
boolean offerFirst(T element);
/
* 队尾添加元素
*
* @param element 元素
* @return 结果
*/
boolean offerLast(T element);
/
* 删除队头元素
*
* @return 队头元素
*/
T pollFirst();
/
* 删除队尾元素
*
* @return 队头元素
*/
T pollLast();
/
* 查看队头元素
*
* @return 队头元素
*/
T peekFirst();
/
* 查看队尾元素
*
* @return 队头元素
*/
T peekLast();
/
* 判断队列是否为空
*
* @return 结果
*/
boolean isEmpty();
/
* 判断队列是否已满
*
* @return 结果
*/
boolean isFull();
}
package com.lzlg.study.algorithm.new2023.deque;
/
* @author lzlg
* 2023/7/24 10:19
*/
public class MyDequeTest {
public static void main(String[] args) {
MyDeque<Integer> deque = new LinkedListDeque<>(4);
deque.offerFirst(1);
deque.offerFirst(2);
deque.offerLast(3);
deque.offerLast(4);
for (Integer element : deque) {
System.out.println(element);
}
System.out.println("===============");
System.out.println(deque.peekFirst());
System.out.println("===============");
System.out.println(deque.peekLast());
System.out.println("===============");
System.out.println(deque.pollFirst());
System.out.println("===============");
System.out.println(deque.pollLast());
System.out.println("===============");
for (Integer element : deque) {
System.out.println(element);
}
System.out.println("===============");
System.out.println(deque.pollFirst());
System.out.println("===============");
System.out.println(deque.pollLast());
}
}
package com.lzlg.study.algorithm.new2023.deque.quiz;
import com.lzlg.study.algorithm.new2023.queue.MyLinkedListQueue;
import com.lzlg.study.algorithm.new2023.queue.MyQueue;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/
* 双端队列使用: 二叉树的z字层序遍历
* 如果有如下二叉树
* 1
* /\
* 2 3
* /\ /\
* 4 5 6 7
* 则z字层序遍历的结果为1, 3, 2, 4, 5, 6, 7
* 即奇数层从前往后,偶数层从后往前
*
* @author lzlg
* 2023/7/22 12:17
*/
public class TreeLevelZForEachQuiz {
/
* 层序遍历二叉树
* 使用一个队列
* 1.开始时,将根节点加入队列
* 2.开始循环,取出队列的头部节点,访问此节点的元素
* 3.判断该节点如果有左右孩子,则分别加入队列中
* 4.直到队列为空,退出循环
*
* @param root 二叉树根节点
*/
public static void levelLoopTree(TreeNode root) {
// 创建队列
MyQueue<TreeNode> queue = new MyLinkedListQueue<>();
// 将根节点加入队列
queue.offer(root);
while (!queue.isEmpty()) {
// 取出节点
TreeNode node = queue.poll();
// 访问该节点
System.out.println(node);
// 如果有左右孩子节点,则分别加入队列中
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/
* 将二叉树的每层变成一个列表,并把这所有列表组合成一个列表返回
*
* @param root 二叉树根节点
* @return 层序列表
*/
public static List<List<Integer>> toLevelList(TreeNode root) {
// 返回结果
List<List<Integer>> result = new ArrayList<>();
// 当二叉树为空,则直接返回空list
if (root == null) {
return result;
}
// 创建队列
MyQueue<TreeNode> queue = new MyLinkedListQueue<>();
// 将根节点加入队列
queue.offer(root);
// 当前二叉树层的节点数量,初始为1,因为先遍历根节点,根节点这一层只有一个
int currentLevelNodeCount = 1;
// 判断当前层数是否是奇数
boolean odd = true;
while (!queue.isEmpty()) {
// 下个层序的节点数量
int nextLevelNodeCount = 0;
// 当前层序的列表,这里使用实现双端队列接口的LinkedList
LinkedList<Integer> levelList = new LinkedList<>();
// 根据当前层的节点数量分别取出
for (int i = 0; i < currentLevelNodeCount; i++) {
// 取出节点
TreeNode node = queue.poll();
// 如果是奇数,将此节点的值加入到当前层序的列表的最后
if (odd) {
levelList.offerLast(node.value);
} else {// 如果是偶数,则添加到头部
levelList.offerFirst(node.value);
}
// 如果有左右孩子节点,则分别加入队列中
if (node.left != null) {
queue.offer(node.left);
// 下个层序的节点数量增加
nextLevelNodeCount++;
}
if (node.right != null) {
queue.offer(node.right);
// 下个层序的节点数量增加
nextLevelNodeCount++;
}
}
// 每次循环完成,奇数变偶数
odd = !odd;
// 当前层序遍历完成,则添加到返回结果中
result.add(levelList);
// 切换当前层序的数量为下个层序的数量,进入下次循环
// 下次循环就是下个层次的遍历了
currentLevelNodeCount = nextLevelNodeCount;
}
// 返回最终结果
return result;
}
public static void main(String[] args) {
// 创建二叉树
TreeNode root = new TreeNode(
1,
new TreeNode(2,
new TreeNode(4, new TreeNode(8), new TreeNode(9)),
new TreeNode(5, new TreeNode(10), new TreeNode(11))
),
new TreeNode(3, new TreeNode(6), new TreeNode(7))
);
levelLoopTree(root);
System.out.println("=======Z字层序遍历的列表=======");
System.out.println(toLevelList(root));
}
/
* 二叉树节点类
*/
private static class TreeNode {
// 节点值
int value;
// 节点左孩子
private TreeNode left;
// 节点右孩子
private TreeNode right;
public TreeNode(int value) {
this.value = value;
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
}
链表
package com.lzlg.study.algorithm.new2023.linkedlist;
import java.util.Iterator;
/
* 双向循环链表,带哨兵节点
*
* @author lzlg
* 2023/7/18 12:55
*/
public class DoubleCycleLinkedList implements Iterable<Integer> {
private final Node sentinel;
public DoubleCycleLinkedList() {
// 哨兵节点
this.sentinel = new Node(null, Integer.MAX_VALUE, null);
// 形成环
sentinel.prev = sentinel;
sentinel.next = sentinel;
}
/
* 头插法
*
* @param element 带插入的元素
*/
public void addFirst(int element) {
// 待插入节点的前一个节点是哨兵节点
Node prev = sentinel;
// 待插入节点的后一个节点是哨兵节点的下一个节点
Node next = sentinel.next;
// 插入新节点
Node added = new Node(prev, element, next);
// 前一个节点的下一个节点指向新插入的节点
prev.next = added;
// 后一个节点的上一个节点指向新插入的节点
next.prev = added;
}
/
* 删除第一个元素
*/
public void removeFirst() {
// 待删除的节点的哨兵节点的后节点
Node removed = sentinel.next;
if (removed == sentinel) {
throw new IllegalArgumentException("链表为空");
}
// 待删除节点的前一个节点是哨兵节点
Node prev = sentinel;
// 待删除节点的后一个节点
Node next = removed.next;
// 将前一个节点的后节点指向下一个节点
prev.next = next;
// 将下一个节点的前节点指向前一个节点
next.prev = prev;
// 将删除的节点的前后指针置空,方便GC
removed.prev = null;
removed.next = null;
}
/
* 尾插法
*
* @param element 带插入的元素
*/
public void addLast(int element) {
// 待插入节点的前一个节点是哨兵节点的上一个节点
Node prev = sentinel.prev;
// 待插入节点的后一个节点是哨兵节点
Node next = sentinel;
// 插入新节点
Node added = new Node(prev, element, next);
// 前一个节点的下一个节点指向新插入的节点
prev.next = added;
// 后一个节点的上一个节点指向新插入的节点
next.prev = added;
}
/
* 删除最后一个元素
*/
public void removeLast() {
// 待删除的节点的哨兵节点的前节点
Node removed = sentinel.prev;
if (removed == sentinel) {
throw new IllegalArgumentException("链表为空");
}
// 待删除节点的前一个节点
Node prev = removed.prev;
// 待删除节点的后一个节点是哨兵节点
Node next = sentinel;
// 将前一个节点的后节点指向下一个节点
prev.next = next;
// 将下一个节点的前节点指向前一个节点
next.prev = prev;
// 将删除的节点的前后指针置空,方便GC
removed.prev = null;
removed.next = null;
}
/
* 删除指定下标的元素
*
* @param index 指定下标
*/
public void remove(int index) {
// 首先找到待删除的节点
Node removed = findNode(index);
if (removed == null) {
throw new IllegalArgumentException("索引非法");
}
// 待删除节点的前后节点
Node prev = removed.prev;
Node next = removed.next;
// 切换指针
prev.next = next;
next.prev = prev;
// 将删除的节点的前后指针置空,方便GC
removed.prev = null;
removed.next = null;
}
/
* 根据索引找到指定的节点
*
* @param index 索引
* @return 节点
*/
private Node findNode(int index) {
int i = 0;
for (Node p = sentinel.next; p != sentinel; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
/
* 使用迭代器遍历
*/
@Override
public Iterator<Integer> iterator() {
return new NodeIterator();
}
/
* 迭代器
*/
private class NodeIterator implements Iterator<Integer> {
Node p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public Integer next() {
int element = p.value;
p = p.next;
return element;
}
}
static class Node {
// 前指针
Node prev;
// 节点的元素值
int value;
// 后指针
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
/
* 双向循环链表,带哨兵节点
*
* @author lzlg
* 2023/7/18 12:55
*/
public class DoubleCycleLinkedListTest {
public static void main(String[] args) {
DoubleCycleLinkedList list = new DoubleCycleLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.addFirst(4);
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list = new DoubleCycleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list.removeFirst();
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list.removeFirst();
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list.removeLast();
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list.removeLast();
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
list = new DoubleCycleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.remove(4);
System.out.println("============");
for (Integer element : list) {
System.out.println(element);
}
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
import java.util.Iterator;
import java.util.function.IntConsumer;
/
* 双向链表,带头尾哨兵
*
* @author lzlg
* 2023/7/18 12:05
*/
public class DoubleLinkedList implements Iterable<Integer> {
// 头指针-头哨兵
private final Node head;
// 尾指针-尾哨兵
private final Node tail;
public DoubleLinkedList() {
// 创建头尾指针
this.head = new Node(null, Integer.MAX_VALUE, null);
this.tail = new Node(null, Integer.MIN_VALUE, null);
// 将头指针的下个节点指向尾节点
head.next = tail;
// 将尾指针的上个节点指向头节点
tail.prev = head;
}
/
* 获取索引下标的节点的元素值
*
* @param index 索引下标
* @return 元素值
*/
public int get(int index) {
Node node = findNode(index);
if (node == null) {
throw new IllegalArgumentException("索引非法");
}
return node.value;
}
/
* 在指定下标位置插入元素
*
* @param index 指定下标
* @param element 待插入的元素
*/
public void insert(int index, int element) {
// 首先找到要插入的索引下标节点的前一个节点
Node prev = findNode(index - 1);
if (prev == null) {
throw new IllegalArgumentException("索引非法");
}
// 前一个节点的下个节点是待插入节点的下个节点
Node next = prev.next;
// 插入新节点,且设置新节点的前一个节点和后一个节点
Node insertNode = new Node(prev, element, next);
// 将前节点的下个节点指向插入的新节点
prev.next = insertNode;
// 将后节点的上个节点指向插入的新节点
tail.prev = insertNode;
}
/
* 找到指定下标的节点
*
* @param index 下标
* @return 指定下标的节点
*/
private Node findNode(int index) {
int i = -1;
for (Node p = head; p != tail; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
/
* 删除指定下标的元素
*
* @param index 指定下标
*/
public void remove(int index) {
// 找到待删除的节点
Node removed = findNode(index);
if (removed == null) {
throw new IllegalArgumentException("索引非法");
}
// 待删除节点的上一个节点
Node prev = removed.prev;
// 待删除节点的下一个节点
Node next = removed.next;
// 上一个节点的后节点指向待删除节点的下一个节点
prev.next = next;
// 下一个节点的前节点指向待删除节点的上一个节点
next.prev = prev;
// 将删除的节点的前后指针置空,方便GC
removed.prev = null;
removed.next = null;
}
/
* 头插法
*
* @param element 待插入的元素
*/
public void addFirst(int element) {
insert(0, element);
}
/
* 删除第一个元素
*/
public void removeFirst() {
remove(0);
}
/
* 尾插法
*
* @param element 待插入的元素
*/
public void addLast(int element) {
// 尾节点的上一个节点是最后一个节点
Node last = tail.prev;
// 插入新节点,新节点的上一个节点是上一个最后元素,新节点的下一个节点是尾节点
Node added = new Node(last, element, tail);
// 上一个最后元素的下一个节点是新插入的节点
last.next = added;
// 尾节点的前一个节点是新插入的节点
tail.prev = added;
}
/
* 删除最后一个元素
*/
public void removeLast() {
// 尾节点的上一个节点是最后一个节点
Node last = tail.prev;
// 最后一个节点不能是头哨兵节点
if (last == head) {
throw new IllegalArgumentException("链表为空");
}
// 最后一个节点的上个节点
Node prev = last.prev;
// 最后一个节点的上个节点的下个节点是尾节点
prev.next = tail;
// 尾节点的上一个节点是最后一个节点的上个节点
tail.prev = prev;
// 将最后一个节点的前后指针置空,方便GC
last.prev = null;
last.next = null;
}
/
* 使用while循环遍历链表
*/
public void loopWhile(IntConsumer consumer) {
Node p = head.next;
while (p != tail) {
consumer.accept(p.value);
p = p.next;
}
}
/
* 使用for循环遍历链表
*/
public void loopFor(IntConsumer consumer) {
for (Node p = head.next; p != tail; p = p.next) {
consumer.accept(p.value);
}
}
/
* 使用迭代器遍历链表
*/
@Override
public Iterator<Integer> iterator() {
return new NodeIterator();
}
/
* 迭代器
*/
private class NodeIterator implements Iterator<Integer> {
Node p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public Integer next() {
int element = p.value;
p = p.next;
return element;
}
}
/
* 节点
*/
static class Node {
// 前一个节点
Node prev;
// 节点值
int value;
// 后一个节点
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
/
* 双向链表
*
* @author lzlg
* 2023/7/18 12:05
*/
public class DoubleLinkedListTest {
public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
System.out.println("=================");
list.loopWhile(System.out::println);
System.out.println("=================");
list.loopFor(System.out::println);
System.out.println("=================");
for (Integer ele : list) {
System.out.println(ele);
}
System.out.println("=================");
System.out.println(list.get(4));
System.out.println("=================");
list.insert(5, 6);
list.loopWhile(System.out::println);
System.out.println("=================");
list.removeFirst();
list.loopWhile(System.out::println);
System.out.println("=================");
list.remove(0);
list.loopWhile(System.out::println);
System.out.println("=================");
list.removeLast();
list.loopWhile(System.out::println);
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
import java.util.Iterator;
import java.util.Optional;
import java.util.function.IntConsumer;
/
* 单向链表
*
* @author lzlg
* 2023/7/18 9:47
*/
public class SingleLinkedList implements Iterable<Integer> {
// 头节点-头指针
private Node head = null;
/
* 迭代器实现
*/
@Override
public Iterator<Integer> iterator() {
return new NodeIterator();
}
/
* 节点迭代器,如果为static class,则指针p访问不到外部类的head
*/
private class NodeIterator implements Iterator<Integer> {
// 使用指针p访问链表
Node p = head;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public Integer next() {
// 取出节点的值,并返回
int value = p.value;
// 将指针p指向下一个
p = p.next;
return value;
}
}
/
* 头插法
*
* @param element 要插入的元素值
*/
public void addFirst(int element) {
// 1.链表为空
// head = new Node(element, null);
// 2.链表非空(因为是头插法)
// head = new Node(element, head);
// 可将上诉两行代码合并
head = new Node(element, head);
}
/
* 使用while循环遍历链表
*/
public void loopWhile(IntConsumer consumer) {
// 使用指针
Node p = head;
// 条件是p指针不为空时,则依次取出节点的值
while (p != null) {
consumer.accept(p.value);
p = p.next;
}
}
/
* 使用for循环遍历链表
*/
public void loopFor(IntConsumer consumer) {
// 和上面的while循环实现进行对比
for (Node p = head; p != null; p = p.next) {
consumer.accept(p.value);
}
}
/
* 链表节点类
* 加static关键字, 因为Node不使用SingleLinkedList(外部类)的成员变量
*/
static class Node {
// 节点存储的值
int value;
// 指向下一个节点的指针
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/
* 尾插法
*
* @param element 要插入的元素值
*/
public void addLast(int element) {
// 首先要找到插入位置的前一个节点
Optional<Node> last = findLast();
// 如果找到前一个节点,则创建新节点,并将前一个节点的下一个节点指向新节点
if (last.isPresent()) {
last.get().next = new Node(element, null);
} else {
// 如果链表为空,则调用addFirst方法
addFirst(element);
}
}
/
* 找到尾部插入的前一个节点
*/
private Optional<Node> findLast() {
// 如果链表为空,则返回空
if (head == null) {
return Optional.empty();
}
Node p;
// 注意,这里的循环判断条件是p.next != null,因为要找到插入位置的前一个节点
for (p = head; p.next != null; p = p.next) ;
return Optional.of(p);
}
/
* 根据索引位置返回节点的值
*
* @param index 索引
* @return 节点的值
*/
public Optional<Integer> get(int index) {
if (index < 0) {
throw new IllegalArgumentException("索引值不能小于0");
}
// 首先根据索引找到节点
Optional<Node> node = findNode(index);
// 如果找到,则返回节点的值
return node.map(element -> element.value);
}
/
* 根据索引找到节点
*
* @param index 索引
* @return 索引对应的节点
*/
private Optional<Node> findNode(int index) {
int i = 0;
for (Node p = head; p != null; p = p.next, i++) {
if (i == index) {
return Optional.of(p);
}
}
return Optional.empty();
}
/
* 向指定索引位置插入元素值
*
* @param index 索引
* @param element 待插入的元素值
*/
public void insert(int index, int element) {
// 如果是index = 0,则是在链表头部进行插入
if (index == 0) {
addFirst(element);
return;
}
// 找到索引指定的节点的上一个节点
Optional<Node> prev = findNode(index - 1);
// 如果存在,则进行插入
if (prev.isPresent()) {
// 创建新节点,将新节点的下一个节点指向前一个节点的下一个节点
prev.get().next = new Node(element, prev.get().next);
} else {
throw new IllegalArgumentException("索引非法");
}
}
/
* 删除第一个节点
*/
public void removeFirst() {
// 如果链表为空,则直接返回
if (head == null) {
throw new IllegalArgumentException("链表为空");
}
// 保存原来的头节点指针
Node p = head;
// 将头指针指向头部的下一个节点
head = head.next;
// 将删除的节点的next指针置空,方便GC回收
p.next = null;
}
/
* 删除指定索引的节点
*
* @param index 指定的索引
*/
public void remove(int index) {
// 如果索引为0,则删除的是头节点,则直接调用removeFirst
if (index == 0) {
removeFirst();
return;
}
// 首先找到索引指向的节点的上一个节点
Optional<Node> prev = findNode(index - 1);
// 如果找到,则进行删除
if (prev.isPresent()) {
// 前一个节点的下一个节点是要删除的节点
Node removed = prev.get().next;
// 如果要删除的节点不存在,则抛出异常
if (removed == null) {
throw new IllegalArgumentException("索引非法");
}
// 将上一个节点的next指向要删除的节点的下个节点
prev.get().next = removed.next;
// 将删除的节点的指向下个节点next置空,方便GC
removed.next = null;
} else {
throw new IllegalArgumentException("索引非法");
}
}
/
* 递归循环
*/
public void recursionLoop(IntConsumer before, IntConsumer after) {
// 调用递归方法
recursion(head, before, after);
}
/
* 递归
*
* @param node 节点
*/
private void recursion(Node node, IntConsumer before, IntConsumer after) {
// 递归结束条件
if (node == null) {
return;
}
// 前置递归
before.accept(node.value);
recursion(node.next, before, after);
// 后置递归
after.accept(node.value);
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
/
* 单向链表测试
*
* @author lzlg
* 2023/7/18 9:47
*/
public class SingleLinkedListTest {
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
list.recursionLoop(
element -> System.out.println("before: " + element),
element -> System.out.println("after: " + element)
);
}
/
* 测试有哨兵的单链表
*/
private static void testSingleSentinelLinkedList() {
SingleSentinelLinkedList list = new SingleSentinelLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.addFirst(4);
list.addFirst(5);
System.out.println("=================");
list.loopWhile(System.out::println);
System.out.println("=================");
list.loopFor(System.out::println);
System.out.println("=================");
for (Integer ele : list) {
System.out.println(ele);
}
System.out.println("=================");
System.out.println(list.get(5));
System.out.println("=================");
list.insert(5, 6);
list.loopWhile(System.out::println);
System.out.println("=================");
list.removeFirst();
list.loopWhile(System.out::println);
System.out.println("=================");
list.remove(0);
list.loopWhile(System.out::println);
System.out.println("=================");
list.remove(3);
list.loopWhile(System.out::println);
}
/
* 测试单链表
*/
private static void testSingleLinkedList() {
SingleLinkedList list = new SingleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
System.out.println("=================");
list.loopWhile(System.out::println);
System.out.println("=================");
list.loopFor(System.out::println);
System.out.println("=================");
for (Integer ele : list) {
System.out.println(ele);
}
System.out.println("=================");
System.out.println(list.get(5));
System.out.println("=================");
list.insert(5, 6);
list.loopWhile(System.out::println);
System.out.println("=================");
list.removeFirst();
list.loopWhile(System.out::println);
System.out.println("=================");
list.remove(0);
list.loopWhile(System.out::println);
System.out.println("=================");
list.remove(3);
list.loopWhile(System.out::println);
}
}
package com.lzlg.study.algorithm.new2023.linkedlist;
import java.util.Iterator;
import java.util.Optional;
import java.util.function.IntConsumer;
/
* 单向链表带哨兵节点
*
* @author lzlg
* 2023/7/18 9:47
*/
public class SingleSentinelLinkedList implements Iterable<Integer> {
// 头节点-头指针-哨兵节点
private final Node head = new Node(Integer.MIN_VALUE, null);
/
* 迭代器实现
*/
@Override
public Iterator<Integer> iterator() {
return new NodeIterator();
}
/
* 节点迭代器,如果为static class,则指针p访问不到外部类的head
*/
private class NodeIterator implements Iterator<Integer> {
// 使用指针p访问链表
Node p = head.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public Integer next() {
// 取出节点的值,并返回
int value = p.value;
// 将指针p指向下一个
p = p.next;
return value;
}
}
/
* 头插法
*
* @param element 要插入的元素值
*/
public void addFirst(int element) {
insert(0, element);
}
/
* 使用while循环遍历链表
*/
public void loopWhile(IntConsumer consumer) {
// 使用指针
Node p = head.next;
// 条件是p指针不为空时,则依次取出节点的值
while (p != null) {
consumer.accept(p.value);
p = p.next;
}
}
/
* 使用for循环遍历链表
*/
public void loopFor(IntConsumer consumer) {
// 和上面的while循环实现进行对比
for (Node p = head.next; p != null; p = p.next) {
consumer.accept(p.value);
}
}
/
* 链表节点类
* 加static关键字, 因为Node不使用SingleLinkedList(外部类)的成员变量
*/
static class Node {
// 节点存储的值
int value;
// 指向下一个节点的指针
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
/
* 尾插法
*
* @param element 要插入的元素值
*/
public void addLast(int element) {
// 首先要找到插入位置的前一个节点
Optional<Node> last = findLast();
// 如果找到前一个节点,则创建新节点,并将前一个节点的下一个节点指向新节点
if (last.isPresent()) {
last.get().next = new Node(element, null);
} else {
// 如果链表为空,则调用addFirst方法
addFirst(element);
}
}
/
* 找到尾部插入的前一个节点
*/
private Optional<Node> findLast() {
Node p;
// 注意,这里的循环判断条件是p.next != null,因为要找到插入位置的前一个节点
for (p = head; p.next != null; p = p.next) ;
return Optional.of(p);
}
/
* 根据索引位置返回节点的值
*
* @param index 索引
* @return 节点的值
*/
public Optional<Integer> get(int index) {
if (index < 0) {
throw new IllegalArgumentException("索引值不能小于0");
}
// 首先根据索引找到节点
Optional<Node> node = findNode(index);
// 如果找到,则返回节点的值
return node.map(element -> element.value);
}
/
* 根据索引找到节点
*
* @param index 索引
* @return 索引对应的节点
*/
private Optional<Node> findNode(int index) {
int i = -1;
for (Node p = head; p != null; p = p.next, i++) {
if (i == index) {
return Optional.of(p);
}
}
return Optional.empty();
}
/
* 向指定索引位置插入元素值
*
* @param index 索引
* @param element 待插入的元素值
*/
public void insert(int index, int element) {
// 找到索引指定的节点的上一个节点
Optional<Node> prev = findNode(index - 1);
// 如果存在,则进行插入
if (prev.isPresent()) {
// 创建新节点,将新节点的下一个节点指向前一个节点的下一个节点
prev.get().next = new Node(element, prev.get().next);
} else {
throw new IllegalArgumentException("索引非法");
}
}
/
* 删除第一个节点
*/
public void removeFirst() {
remove(0);
}
/
* 删除指定索引的节点
*
* @param index 指定的索引
*/
public void remove(int index) {
// 首先找到索引指向的节点的上一个节点
Optional<Node> prev = findNode(index - 1);
// 如果找到,则进行删除
if (prev.isPresent()) {
// 前一个节点的下一个节点是要删除的节点
Node removed = prev.get().next;
// 如果要删除的节点不存在,则抛出异常
if (removed == null) {
throw new IllegalArgumentException("索引非法");
}
// 将上一个节点的next指向要删除的节点的下个节点
prev.get().next = removed.next;
// 将删除的节点的指向下个节点next置空,方便GC
removed.next = null;
} else {
throw new IllegalArgumentException("索引非法");
}
}
}
数据结构
算法
程序员内功
- 作者：lzlg520
- 发表时间：2023-09-13 21:45
- 版权声明：自由转载-非商用-非衍生-保持署名
- 公众号转载：请在文末添加作者公众号二维码
