当前位置：首页 > news >正文

【数据结构】队列，你必须知道的内部原理！！！

news 来源：原创 2024/9/19 9:21:03

🌞🌞🌞生活本就沉闷，但跑起来就会有风 ~~~

前言：

🌟🌟Hello家人们，这期讲解数据结构队列的基础知识，希望你能帮到屏幕前的你。

📚️上期博客在这里：http://t.csdnimg.cn/WJjIy

📚️感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

📚️ 1.什么是对队列

🎥1.1队列概念：

🎥1.2入队列：

🎥1.3出队列：

📚️2.队列方法的底层模拟

🎥2.1引导：

🎥2.2初始化链表：

🎥2.3入队列：

🎥2.4出队列：

🎥2.5输出队列头元素：

🎥2.6队列长度，打印，非空判断：

📚️3.队列的应用

🎬️3.1队列的方法

🎬️3.2队列的使用代码：

📚️4.总结语

那么正片开始~~~🎬️🎬️🎬️

📚️ 1.什么是对队列

🎥1.1队列概念：

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

的性质

🎥1.2入队列：

进行插入操作的一端称为队尾（Tail/Rear）

🎥1.3出队列：

进行删除操作的一端称为队头（Head/front）

图片实例：

💡💡💡 总结来说，队列就是像我们平时排队一样，先到先得，第一个人站在队头，最后一

个人站在 队尾，这样是否更形象呢~~~

📚️2.队列方法的底层模拟

这部分是比较重要的一部分~~~

🎥2.1引导：

💬在上述描述中可以看到，队列用数组实现，但是当出队列时，可以看到前面的空间都浪费了，所以小编在这里将用链表进行队列的模拟。

图解如下：

💡💡可以看到，front索引前面的数据出队列后就为空了，导致前面的位置就直接浪费了。

🎥2.2初始化链表：

代码如下：

public class Queue {// 双向链表节点public static class ListNode{  //定义内部类表示节点ListNode next;      ListNode prev;int value;ListNode(int value){this.value = value;}}ListNode first; // 队头ListNode last; // 队尾int size = 0;  //有效数据

💬小编在这里创建了一个双向链表（双向链表博客在这里：http://t.csdnimg.cn/8vB1R）方便一系列操作，并且多初始化了一个变量表示有效数据。

🎥2.3入队列：

代码如下：

public void offer(int e){ListNode node=new ListNode(e);if(first==null){   //判断链表是否为空first= node;last=node;}else {            //正常插入node.prev=last;last.next=node;node.next=null;last=node;}size++;             //有效数据加一}

💬在链接节点时要进行链表是否为空的判断，如果为空，就将头结点和尾巴节点都给插入节点。反之，就直接进行正常的尾插法即可。

🎥2.4出队列：

代码如下：

 public int poll(){if(isEmpty()){     //判断是否为空System.out.println("队列为空，无法输出数据");return -1;}if(first==last){   //当只有一个节点时int ret=first.value;first=null;last=null;size--;return ret;}                  //正常进行链表的头节点删除int ret=first.value;first=first.next;first.prev=null;size--;            //有效数据减一return ret;}

💬这里还是一样的在出队列时，要判断链表是否为空，在进行头节点的删除。

注意：在判空的前提上还要分多个节点和一个节点的头节点的删除情况。

🎥2.5输出队列头元素：

代码如下：

public int peek(){if(isEmpty()){System.out.println("队列为空，没有数据");return -1;}return first.value;}

💬这里还是要先判断链表的状态，最后返回头节点的域值的数据即可，不用做其他操作，得到值就OK。

🎥2.6队列长度，打印，非空判断：

代码如下：

public int size() {   //获取队列的长度return size;}private boolean isEmpty(){  //判断队列是否为空if(first==null){return true;}return false;}public void display(){    //打印队列ListNode cur=first;while (cur!=null) {    //遍历链表System.out.print(cur.value + " ");cur = cur.next;}System.out.println();  //换行，方便测试}

💬这里就相比起来，就比前面的更简单，小编就不再过多赘述。

📚️3.队列的应用

🎬️3.1队列的方法

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

🎬️3.2队列的使用代码：

代码实例：

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);                   // 从队尾入队列System.out.println(q.size()); // 获取队列长度System.out.println(q.peek()); // 获取队头元素q.poll();                     System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){              System.out.println("队列空");}else{System.out.println(q.size());}}

💬这里就类似于方法的调用，这里小编就通过注解来解释咯~~~