尧图网站建设 
你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、口诀二、用法2.1 定义语法2.2 有哪些功能三、手搓队列第一套单向链表实现队列 MyQueue无傀儡头节点LinkedNode 节点类单向链表节点MyQueue 成员变量offer (int val) 入队方法【尾插向队尾添加元素】poll () 出队方法【头删删除并返回队首元素】peek () 获取队首元素【只查看不删除元素】main 测试方法执行流程模拟第二套循环数组实现队列 MyArrayQueue成员变量逐行讲解构造方法 MyArrayQueue ()offer (int val) 入队方法poll () 出队方法peek () 查看队首元素main 方法执行模拟一、口诀队列遵循先进先出FIFO队尾用来入队新增元素队首用来出队删除元素新增、删除操作分开在两端执行。offer完成尾插入队poll头删出队取出队首元素peek仅读取队首不会改动队列内容。链表实现队列维护 head 队首指针、tail 队尾指针数组实现采用循环数组依靠取模运算形成环形复用出队后闲置的数组空间。二、用法2.1 定义语法ArrayDeque推荐无界数组队列性能优于 LinkedListimport java.util.Queue; import java.util.ArrayDeque; public class Test { public static void main(String[] args) { // 定义队列存放Integer类型 QueueInteger queue new ArrayDeque(); } }LinkedList实现了 Queue 接口链表队列import java.util.Queue; import java.util.ArrayDeque; public class Test { public static void main(String[] args) { // 定义队列存放Integer类型 QueueInteger queue new ArrayDeque(); } }2.2 有哪些功能Java 原生Queue接口三个核心基础方法本次不拓展 Dequeoffer(E e)入队在队列尾部添加元素poll()出队删除并返回队首元素队列为空时返回nullpeek()获取队首元素只查看、不删除队列为空时返回null核心区分栈是同一端进出队列一头进、另一头出。三、手搓队列第一套单向链表实现队列 MyQueue无傀儡头节点package queue; class LinkedNode { public int val; public LinkedNode next; public LinkedNode(int val) { this.val val; this.next null; } } // 不引入傀儡节点 public class MyQueue { private LinkedNode head null; // 为了尾插方便引入尾结点 private LinkedNode tail null; // 入队列实现尾插 public void offer(int val) { LinkedNode newNode new LinkedNode(val); if (head null) { head newNode; tail newNode; return; } // 把新节点添加到 tail 的末尾 tail.next newNode; tail tail.next; } // 出队列实现头删 public Integer poll() { if (head null) { return null; } int ret head.val; head head.next; return ret; } // 取队首元素 public Integer peek() { if (head null) { return null; } return head.val; } public static void main(String[] args) { MyQueue queue new MyQueue(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } }LinkedNode 节点类单向链表节点class LinkedNode { public int val; public LinkedNode next; public LinkedNode(int val) { this.val val; this.next null; } }public int val存储队列中保存的数据使用public方便外部类直接访问省去 get/set 方法。public LinkedNode next引用变量保存下一个节点的内存地址。单向链表只能顺着 next 向后查找节点无法反向查找。构造方法LinkedNode(int val)创建节点时必须传入存储的值。this.val val将传入数值赋值给当前节点this.next null新创建的节点暂时没有连接任何其他节点后继引用初始为空。MyQueue 成员变量private LinkedNode head null;private LinkedNode tail null;private封装特性外部代码不能直接修改头、尾指针只能通过提供的方法操作队列。head指向队首节点。队列为空时 head null队列存在元素时head 就是链表第一个节点。tail指向队尾节点。重点普通单向链表如果没有 tail 指针每次尾部插入元素都要从 head 从头遍历到最后一个节点时间复杂度 O (n)保存 tail 指针后尾插直接操作 tail时间复杂度 O (1)大幅提升效率。空队列初始状态head nulltail null。offer (int val) 入队方法【尾插向队尾添加元素】public void offer(int val) { LinkedNode newNode new LinkedNode(val); if (head null) { head newNode; tail newNode; return; } tail.next newNode; tail tail.next; }LinkedNode newNode new LinkedNode(val);根据传入的值新建一个链表节点。if (head null)判断队列是否为空。队列为空此时链表只有这唯一一个节点队首和队尾是同一个节点所以head newNode; tail newNode;执行 return 结束方法。队列不为空的执行逻辑tail.next newNode;当前 tail 是最后一个节点让尾节点的 next 指向新节点完成节点连接tail tail.next;移动 tail 指针让 tail 指向新的末尾节点。原生代码存在 BUG当队列中最后一个元素被 poll 删除后head会被赋值为 null但是tail仍然保留旧节点引用。旧节点无法被垃圾回收造成内存引用残留。修复方案在 poll 方法中添加判断head head.next;if(head null){ tail null;}poll () 出队方法【头删删除并返回队首元素】public Integer poll() { if (head null) { return null; } int ret head.val; head head.next; return ret; }if (head null)队列为空没有元素可以取出返回 nullint ret head.val;提前保存队首节点的值。head 指针马上要向后移动如果不提前保存数据会丢失head head.next;head 指针向后移动指向第二个节点原先的队首节点没有任何引用指向它等待 JVM 垃圾回收return ret;返回取出的队首数值。peek () 获取队首元素【只查看不删除元素】public Integer peek() { if (head null) { return null; } return head.val; }判断队列非空直接读取 head 节点存储的值。核心区别peek 不会移动 head、tail 指针链表结构完全不发生变化仅仅读取数据。main 测试方法执行流程模拟MyQueue queue new MyQueue(); // headnulltailnull queue.offer(1); // 队空head节点1tail节点1 queue.offer(2); // tail.next节点2tail指向节点2 queue.offer(3); // tail.next节点3tail指向节点3 queue.offer(4); // tail.next节点4tail指向节点4// 当前链表结构1 → 2 → 3 → 4head指向1tail指向4System.out.println(queue.poll()); //取出1head指向2输出1System.out.println(queue.poll()); //取出2head指向3输出2System.out.println(queue.poll()); //取出3head指向4输出3System.out.println(queue.poll()); //取出4headnull输出4System.out.println(queue.poll()); //head为null返回null第二套循环数组实现队列 MyArrayQueue普通数组实现队列存在缺陷元素出队后数组前面的空间永久浪费。循环队列利用下标取模运算让下标到达数组末尾后折返到下标 0复用前面空闲空间。本实现核心特点使用size变量记录有效元素数量区分空队列、满队列不需要空出一个数组位置。package queue; public class MyArrayQueue { private int[] array; private int head; private int tail; private int size; public MyArrayQueue() { array new int[1000]; head 0; tail 0; size 0; } public void offer(int val) { if (size array.length) { return; } array[tail] val; tail (tail 1) % array.length; size; } public Integer poll() { if (size 0) { return null; } int ret array[head]; head; if (head array.length) { head 0; } size--; return ret; } public Integer peek() { if (size 0) { return null; } return array[head]; } public static void main(String[] args) { MyArrayQueue queue new MyArrayQueue(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } }成员变量逐行讲解private int[] array; private int head; private int tail; private int size;int[] array底层存储队列数据的数组占用连续内存head队首元素所在数组下标head 位置一定存在有效数据tail下一个待插入元素的下标位置tail 指向的位置目前是空没有数据重点极易混淆size队列当前有效元素个数。size 0→ 队列为空size array.length→ 队列已满构造方法 MyArrayQueue ()public MyArrayQueue() { array new int[1000]; head 0; tail 0; size 0;}array new int[1000]创建长度固定为 1000 的数组容量写死拓展方向可以实现动态扩容head 0; tail 0初始下标全部从 0 开始size 0初始化队列没有任何元素。offer (int val) 入队方法public void offer(int val) { if (size array.length) { return; } array[tail] val; tail (tail 1) % array.length; size; }if (size array.length)有效元素数量等于数组最大容量队列已满无法继续添加元素直接结束方法array[tail] val把待存入的值放到 tail 下标位置tail (tail 1) % array.length;取模实现循环假设数组长度 1000当tail 999数组最后一个下标tail110001000 % 1000 0tail 自动回到下标 0注释中 if 判断写法和取模效果完全一致取模写法更加简洁通用size成功新增元素有效元素数量 1。poll () 出队方法public Integer poll() { if (size 0) { return null; } int ret array[head]; head; if (head array.length) { head 0; } size--; return ret; }if (size 0)没有有效元素队空返回 nullint ret array[head];取出 head 下标对应的队首数据提前保存head队首下标向后移动一位if (head array.length) head 0;head 超出数组下标范围时重置为 0实现循环size--删除一个元素有效元素数量减一return ret返回取出的数据。peek () 查看队首元素public Integer peek() { if (size 0) { return null; } return array[head]; }size 为 0 代表队空返回 null否则直接读取 array [head]。head、tail、size 全部不会修改仅查询数据。main 方法执行模拟MyArrayQueue queue new MyArrayQueue(); // head0 tail0 size0 queue.offer(1); // array[0]1 tail1 size1 queue.offer(2); // array[1]2 tail2 size2 queue.offer(3); // array[2]3 tail3 size3 queue.offer(4); // array[3]4 tail4 size4System.out.println(queue.poll()); //取array[0]1 head1 size3 →输出1System.out.println(queue.poll()); //取array[1]2 head2 size2 →输出2System.out.println(queue.poll()); //取array[2]3 head3 size1 →输出3System.out.println(queue.poll()); //取array[3]4 head4 size0 →输出4System.out.println(queue.poll()); //size0 返回null今天的数据结构讲解就到这了我们下期再见诸位共勉 队列 FIFO 原理 手撕两种队列实现（链表 + 循环数组）—数据结构陆
你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、口诀二、用法2.1 定义语法2.2 有哪些功能三、手搓队列第一套单向链表实现队列 MyQueue无傀儡头节点LinkedNode 节点类单向链表节点MyQueue 成员变量offer (int val) 入队方法【尾插向队尾添加元素】poll () 出队方法【头删删除并返回队首元素】peek () 获取队首元素【只查看不删除元素】main 测试方法执行流程模拟第二套循环数组实现队列 MyArrayQueue成员变量逐行讲解构造方法 MyArrayQueue ()offer (int val) 入队方法poll () 出队方法peek () 查看队首元素main 方法执行模拟一、口诀队列遵循先进先出FIFO队尾用来入队新增元素队首用来出队删除元素新增、删除操作分开在两端执行。offer完成尾插入队poll头删出队取出队首元素peek仅读取队首不会改动队列内容。链表实现队列维护 head 队首指针、tail 队尾指针数组实现采用循环数组依靠取模运算形成环形复用出队后闲置的数组空间。二、用法2.1 定义语法ArrayDeque推荐无界数组队列性能优于 LinkedListimport java.util.Queue; import java.util.ArrayDeque; public class Test { public static void main(String[] args) { // 定义队列存放Integer类型 QueueInteger queue new ArrayDeque(); } }LinkedList实现了 Queue 接口链表队列import java.util.Queue; import java.util.ArrayDeque; public class Test { public static void main(String[] args) { // 定义队列存放Integer类型 QueueInteger queue new ArrayDeque(); } }2.2 有哪些功能Java 原生Queue接口三个核心基础方法本次不拓展 Dequeoffer(E e)入队在队列尾部添加元素poll()出队删除并返回队首元素队列为空时返回nullpeek()获取队首元素只查看、不删除队列为空时返回null核心区分栈是同一端进出队列一头进、另一头出。三、手搓队列第一套单向链表实现队列 MyQueue无傀儡头节点package queue; class LinkedNode { public int val; public LinkedNode next; public LinkedNode(int val) { this.val val; this.next null; } } // 不引入傀儡节点 public class MyQueue { private LinkedNode head null; // 为了尾插方便引入尾结点 private LinkedNode tail null; // 入队列实现尾插 public void offer(int val) { LinkedNode newNode new LinkedNode(val); if (head null) { head newNode; tail newNode; return; } // 把新节点添加到 tail 的末尾 tail.next newNode; tail tail.next; } // 出队列实现头删 public Integer poll() { if (head null) { return null; } int ret head.val; head head.next; return ret; } // 取队首元素 public Integer peek() { if (head null) { return null; } return head.val; } public static void main(String[] args) { MyQueue queue new MyQueue(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } }LinkedNode 节点类单向链表节点class LinkedNode { public int val; public LinkedNode next; public LinkedNode(int val) { this.val val; this.next null; } }public int val存储队列中保存的数据使用public方便外部类直接访问省去 get/set 方法。public LinkedNode next引用变量保存下一个节点的内存地址。单向链表只能顺着 next 向后查找节点无法反向查找。构造方法LinkedNode(int val)创建节点时必须传入存储的值。this.val val将传入数值赋值给当前节点this.next null新创建的节点暂时没有连接任何其他节点后继引用初始为空。MyQueue 成员变量private LinkedNode head null;private LinkedNode tail null;private封装特性外部代码不能直接修改头、尾指针只能通过提供的方法操作队列。head指向队首节点。队列为空时 head null队列存在元素时head 就是链表第一个节点。tail指向队尾节点。重点普通单向链表如果没有 tail 指针每次尾部插入元素都要从 head 从头遍历到最后一个节点时间复杂度 O (n)保存 tail 指针后尾插直接操作 tail时间复杂度 O (1)大幅提升效率。空队列初始状态head nulltail null。offer (int val) 入队方法【尾插向队尾添加元素】public void offer(int val) { LinkedNode newNode new LinkedNode(val); if (head null) { head newNode; tail newNode; return; } tail.next newNode; tail tail.next; }LinkedNode newNode new LinkedNode(val);根据传入的值新建一个链表节点。if (head null)判断队列是否为空。队列为空此时链表只有这唯一一个节点队首和队尾是同一个节点所以head newNode; tail newNode;执行 return 结束方法。队列不为空的执行逻辑tail.next newNode;当前 tail 是最后一个节点让尾节点的 next 指向新节点完成节点连接tail tail.next;移动 tail 指针让 tail 指向新的末尾节点。原生代码存在 BUG当队列中最后一个元素被 poll 删除后head会被赋值为 null但是tail仍然保留旧节点引用。旧节点无法被垃圾回收造成内存引用残留。修复方案在 poll 方法中添加判断head head.next;if(head null){ tail null;}poll () 出队方法【头删删除并返回队首元素】public Integer poll() { if (head null) { return null; } int ret head.val; head head.next; return ret; }if (head null)队列为空没有元素可以取出返回 nullint ret head.val;提前保存队首节点的值。head 指针马上要向后移动如果不提前保存数据会丢失head head.next;head 指针向后移动指向第二个节点原先的队首节点没有任何引用指向它等待 JVM 垃圾回收return ret;返回取出的队首数值。peek () 获取队首元素【只查看不删除元素】public Integer peek() { if (head null) { return null; } return head.val; }判断队列非空直接读取 head 节点存储的值。核心区别peek 不会移动 head、tail 指针链表结构完全不发生变化仅仅读取数据。main 测试方法执行流程模拟MyQueue queue new MyQueue(); // headnulltailnull queue.offer(1); // 队空head节点1tail节点1 queue.offer(2); // tail.next节点2tail指向节点2 queue.offer(3); // tail.next节点3tail指向节点3 queue.offer(4); // tail.next节点4tail指向节点4// 当前链表结构1 → 2 → 3 → 4head指向1tail指向4System.out.println(queue.poll()); //取出1head指向2输出1System.out.println(queue.poll()); //取出2head指向3输出2System.out.println(queue.poll()); //取出3head指向4输出3System.out.println(queue.poll()); //取出4headnull输出4System.out.println(queue.poll()); //head为null返回null第二套循环数组实现队列 MyArrayQueue普通数组实现队列存在缺陷元素出队后数组前面的空间永久浪费。循环队列利用下标取模运算让下标到达数组末尾后折返到下标 0复用前面空闲空间。本实现核心特点使用size变量记录有效元素数量区分空队列、满队列不需要空出一个数组位置。package queue; public class MyArrayQueue { private int[] array; private int head; private int tail; private int size; public MyArrayQueue() { array new int[1000]; head 0; tail 0; size 0; } public void offer(int val) { if (size array.length) { return; } array[tail] val; tail (tail 1) % array.length; size; } public Integer poll() { if (size 0) { return null; } int ret array[head]; head; if (head array.length) { head 0; } size--; return ret; } public Integer peek() { if (size 0) { return null; } return array[head]; } public static void main(String[] args) { MyArrayQueue queue new MyArrayQueue(); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); } }成员变量逐行讲解private int[] array; private int head; private int tail; private int size;int[] array底层存储队列数据的数组占用连续内存head队首元素所在数组下标head 位置一定存在有效数据tail下一个待插入元素的下标位置tail 指向的位置目前是空没有数据重点极易混淆size队列当前有效元素个数。size 0→ 队列为空size array.length→ 队列已满构造方法 MyArrayQueue ()public MyArrayQueue() { array new int[1000]; head 0; tail 0; size 0;}array new int[1000]创建长度固定为 1000 的数组容量写死拓展方向可以实现动态扩容head 0; tail 0初始下标全部从 0 开始size 0初始化队列没有任何元素。offer (int val) 入队方法public void offer(int val) { if (size array.length) { return; } array[tail] val; tail (tail 1) % array.length; size; }if (size array.length)有效元素数量等于数组最大容量队列已满无法继续添加元素直接结束方法array[tail] val把待存入的值放到 tail 下标位置tail (tail 1) % array.length;取模实现循环假设数组长度 1000当tail 999数组最后一个下标tail110001000 % 1000 0tail 自动回到下标 0注释中 if 判断写法和取模效果完全一致取模写法更加简洁通用size成功新增元素有效元素数量 1。poll () 出队方法public Integer poll() { if (size 0) { return null; } int ret array[head]; head; if (head array.length) { head 0; } size--; return ret; }if (size 0)没有有效元素队空返回 nullint ret array[head];取出 head 下标对应的队首数据提前保存head队首下标向后移动一位if (head array.length) head 0;head 超出数组下标范围时重置为 0实现循环size--删除一个元素有效元素数量减一return ret返回取出的数据。peek () 查看队首元素public Integer peek() { if (size 0) { return null; } return array[head]; }size 为 0 代表队空返回 null否则直接读取 array [head]。head、tail、size 全部不会修改仅查询数据。main 方法执行模拟MyArrayQueue queue new MyArrayQueue(); // head0 tail0 size0 queue.offer(1); // array[0]1 tail1 size1 queue.offer(2); // array[1]2 tail2 size2 queue.offer(3); // array[2]3 tail3 size3 queue.offer(4); // array[3]4 tail4 size4System.out.println(queue.poll()); //取array[0]1 head1 size3 →输出1System.out.println(queue.poll()); //取array[1]2 head2 size2 →输出2System.out.println(queue.poll()); //取array[2]3 head3 size1 →输出3System.out.println(queue.poll()); //取array[3]4 head4 size0 →输出4System.out.println(queue.poll()); //size0 返回null今天的数据结构讲解就到这了我们下期再见诸位共勉