哪些是 joomla做的网站,做网站运用的软件,商城网站建设框架,郑州炫彩网站建设#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 一.队列概述1.概述2.链表实现3.环形数组实现 二.队列刷题1.二叉树的层序遍历-力扣 102 题 一.队列概述
1.概述
计算机科学中queue 是以顺序的方式维护的一组数据集合在一端添加数据从另一端移除数据。习惯来说添加的一端称为尾移除的一端称为头就如同生活中的排队买商品
先定义一个简化的队列接口
public interface QueueE {/*** 向队列尾插入值* param value 待插入值* return 插入成功返回 true, 插入失败返回 false*/boolean offer(E value);/*** 从对列头获取值, 并移除* return 如果队列非空返回对头值, 否则返回 null*/E poll();/*** 从对列头获取值, 不移除* return 如果队列非空返回对头值, 否则返回 null*/E peek();/*** 检查队列是否为空* return 空返回 true, 否则返回 false*/boolean isEmpty();/*** 检查队列是否已满* return 满返回 true, 否则返回 false*/boolean isFull();
}2.链表实现
下面以单向环形带哨兵链表方式来实现队列 代码
public class LinkedListQueueEimplements QueueE, IterableE {private static class NodeE {E value;NodeE next;public Node(E value, NodeE next) {this.value value;this.next next;}}private NodeE head new Node(null, null);private NodeE tail head;private int size 0;private int capacity Integer.MAX_VALUE;{tail.next head;}public LinkedListQueue() {}public LinkedListQueue(int capacity) {this.capacity capacity;}Overridepublic boolean offer(E value) {if (isFull()) {return false;}NodeE added new Node(value, head);tail.next added;tail added;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}NodeE first head.next;head.next first.next;if (first tail) {tail head;}size--;return first.value;}Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p head.next;Overridepublic boolean hasNext() {return p ! head;}Overridepublic E next() {E value p.value;p p.next;return value;}};}
}3.环形数组实现
好处
对比普通数组起点和终点更为自由不用考虑数据移动“环”意味着不会存在【越界】问题数组性能更佳环形数组比较适合实现有界队列、RingBuffer 等 下标计算
例如数组长度是 5当前位置是 3 向前走 2 步此时下标为 ( 3 2 ) % 5 0 (3 2)\%5 0 (32)%50 ( c u r s t e p ) % l e n g t h (cur step) \% length (curstep)%length
cur 当前指针位置step 前进步数length 数组长度 注意 如果 step 1也就是一次走一步可以在 length 时重置为 0 即可 判断空 判断满 满之后的策略可以根据业务需求决定
例如我们要实现的环形队列满之后就拒绝入队
代码
public class ArrayQueueE implements QueueE, IterableE{private int head 0;private int tail 0;private final E[] array;private final int length;SuppressWarnings(all)public ArrayQueue(int capacity) {length capacity 1;array (E[]) new Object[length];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] value;tail (tail 1) % length;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head];head (head 1) % length;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}Overridepublic boolean isEmpty() {return tail head;}Overridepublic boolean isFull() {return (tail 1) % length head;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p];p (p 1) % array.length;return value;}};}
}判断空、满方法 2
引入 size
public class ArrayQueue2E implements QueueE, IterableE {private int head 0;private int tail 0;private final E[] array;private final int capacity;private int size 0;SuppressWarnings(all)public ArrayQueue2(int capacity) {this.capacity capacity;array (E[]) new Object[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail] value;tail (tail 1) % capacity;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head];head (head 1) % capacity;size--;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p];p (p 1) % capacity;return value;}};}
}判断空、满方法 3 head 和 tail 不断递增用到索引时再用它们进行计算两个问题 如何保证 head 和 tail 自增超过正整数最大值的正确性 如何让取模运算性能更高 答案让 capacity 为 2 的幂
public class ArrayQueue3E implements QueueE, IterableE {private int head 0;private int tail 0;private final E[] array;private final int capacity;SuppressWarnings(all)public ArrayQueue3(int capacity) {if ((capacity capacity - 1) ! 0) {throw new IllegalArgumentException(capacity 必须为 2 的幂);}this.capacity capacity;array (E[]) new Object[this.capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}array[tail capacity - 1] value;tail;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E value array[head capacity - 1];head;return value;}Overridepublic E peek() {if (isEmpty()) {return null;}return array[head capacity - 1];}Overridepublic boolean isEmpty() {return tail - head 0;}Overridepublic boolean isFull() {return tail - head capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E value array[p capacity - 1];p;return value;}};}
}二.队列刷题
1.二叉树的层序遍历-力扣 102 题 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]private static ListListInteger getLists(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}LinkedListQueueTreeNode queue new LinkedListQueue();queue.offer(root);int c1 1;while (!queue.isEmpty()) {ListInteger level new ArrayList(); // 保存每一层结果int c2 0;for (int i 0; i c1; i) {TreeNode n queue.poll();level.add(n.val);if (n.left ! null) {queue.offer(n.left);c2;}if (n.right ! null) {queue.offer(n.right);c2;}}result.add(level);c1 c2;}return result;
}觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
