学校部门网站建设总结,怎么宣传自己的平台,seo人才网,短视频seo软件#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.接口定义4.链表实现5.数组实现 二.题目练习1.二叉树的锯齿形层序遍历-力扣 103 题2.设计双端队列-力扣 641 题 1.概述
双端队列、队列、栈对比
定义特点队列一端删除头另一端添加尾First In First Out栈一端删除和添加顶Last In First Out双端队列两端都可以删除、添加优先级队列优先级高者先出队延时队列根据延时时间确定优先级并发非阻塞队列队列空或满时不阻塞并发阻塞队列队列空时删除阻塞、队列满时添加阻塞
2.方法比较 注 1 Java 中 LinkedList 即为典型双端队列实现不过它同时实现了 Queue 接口也提供了栈的 push pop 等方法 注 2 不同语言操作双端队列的方法命名有所不同参见下表 操作JavaJavaScriptCleetCode 641尾部插入offerLastpushpush_backinsertLast头部插入offerFirstunshiftpush_frontinsertFront尾部移除pollLastpoppop_backdeleteLast头部移除pollFirstshiftpop_frontdeleteFront尾部获取peekLastat(-1)backgetRear头部获取peekFirstat(0)frontgetFront 吐槽一下 leetCode 命名比较 low 常见的单词还有 enqueue 入队、dequeue 出队 3.接口定义
public interface DequeE {boolean offerFirst(E e);boolean offerLast(E e);E pollFirst();E pollLast();E peekFirst();E peekLast();boolean isEmpty();boolean isFull();
}4.链表实现
/*** 基于环形链表的双端队列* param E 元素类型*/
public class LinkedListDequeE implements DequeE, IterableE {Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size;NodeE a sentinel;NodeE b sentinel.next;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size;NodeE a sentinel.prev;NodeE b sentinel;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}NodeE a sentinel;NodeE polled sentinel.next;NodeE b polled.next;a.next b;b.prev a;size--;return polled.value;}Overridepublic E pollLast() {if (isEmpty()) {return null;}NodeE polled sentinel.prev;NodeE a polled.prev;NodeE b sentinel;a.next b;b.prev a;size--;return polled.value;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {NodeE prev;E value;NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}NodeE sentinel new Node(null, null, null);int capacity;int size;public LinkedListDeque(int capacity) {sentinel.next sentinel;sentinel.prev sentinel;this.capacity capacity;}
}5.数组实现
/*** 基于循环数组实现, 特点* ul* litail 停下来的位置不存储, 会浪费一个位置/li* /ul* param E*/
public class ArrayDeque1E implements DequeE, IterableE {/*ht0 1 2 3b a*/Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head dec(head, array.length);array[head] e;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] e;tail inc(tail, array.length);return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e array[head];array[head] null;head inc(head, array.length);return e;}Overridepublic E pollLast() {if (isEmpty()) {return null;}tail dec(tail, array.length);E e array[tail];array[tail] null;return e;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {if (tail head) {return tail - head array.length - 1;} else if (tail head) {return head - tail 1;} else {return false;}}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E e array[p];p inc(p, array.length);return e;}};}E[] array;int head;int tail;SuppressWarnings(unchecked)public ArrayDeque1(int capacity) {array (E[]) new Object[capacity 1];}static int inc(int i, int length) {if (i 1 length) {return 0;}return i 1;}static int dec(int i, int length) {if (i - 1 0) {return length - 1;}return i - 1;}
}数组实现中如果存储的是基本类型那么无需考虑内存释放例如 但如果存储的是引用类型应当设置该位置的引用为 null以便内存及时释放 二.题目练习
1.二叉树的锯齿形层序遍历-力扣 103 题 给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 输入root [3,9,20,null,null,15,7]
输出[[3],[20,9],[15,7]]题解:
public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}LinkedListQueueTreeNode queue new LinkedListQueue();queue.offer(root);int c1 1; // 当前层节点数boolean odd true; // 奇数层while (!queue.isEmpty()) {LinkedListInteger level new LinkedList(); // 保存每一层结果int c2 0; // 下一层节点数for (int i 0; i c1; i) {TreeNode n queue.poll();if (odd) {level.offerLast(n.val);} else {level.offerFirst(n.val);}if (n.left ! null) {queue.offer(n.left);c2;}if (n.right ! null) {queue.offer(n.right);c2;}}odd !odd;result.add(level);c1 c2;}return result;
}2.设计双端队列-力扣 641 题
public class LinkedListDequeE implements DequeE, IterableE {Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}NodeE a sentinel;NodeE b sentinel.next;NodeE added new Node(a, e, b);a.next added;b.prev added;size;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}NodeE a sentinel.prev;NodeE b sentinel;NodeE added new Node(a, e, b);a.next added;b.prev added;size;return false;}// a bOverridepublic E pollFirst() {if (isEmpty()) {return null;}NodeE a sentinel;NodeE removed sentinel.next;NodeE b removed.next;a.next b;b.prev a;size--;return removed.value;}// a bOverridepublic E pollLast() {if (isEmpty()) {return null;}NodeE b sentinel;NodeE removed sentinel.prev;NodeE a removed.prev;a.next b;b.prev a;size--;return removed.value;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {NodeE prev;E value;NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}int capacity;int size;NodeE sentinel new Node(null, null, null);public LinkedListDeque(int capacity) {this.capacity capacity;sentinel.next sentinel;sentinel.prev sentinel;}
}觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
