数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态)

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第1张

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第2张


目录

队列的概念

队列的数据结构

队列的实现

入队

出队

获取队头元素

获取队列长度

循环队列的概念

循环队列的数据结构

循环队列的实现

判断队列是否为空

判断队列是否已满

入队

出队

得到队头元素

得到队尾元素


队列的概念

队列(Queue)是一种数据结构,是一种先进先出(First-In-First-Out,FIFO)的线性数据结构。它只允许在列表的一端进行插入 *** 作(入队),在另一端进行删除 *** 作(出队),即队头进行删除 *** 作,队尾进行插入 *** 作。队列常用的 *** 作有入队(Enqueue)、出队(Dequeue)、获取队头元素(Front/Peek)、获取队列长度(Size/Length)等。

图示如下:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第3张

队列的特点是按照元素加入的先后顺序进行 *** 作,先加入队列的元素会先被取出,后加入的元素会后被取出。这种特性常常被用于模拟实际生活中的排队场景,例如银行柜台排队、CPU任务调度等。


队列的数据结构

队列可以用数组或链表来实现。数组实现的队列需要预先分配一定的空间,但是在 *** 作中效率较高;链表实现的队列没有固定的空间限制,但是在 *** 作中可能需要更多的时间和空间。

这里笔者以链表进行演示:

public class MyQueue { static class ListNode { int val;//存放数据 ListNode pre;//前驱指针 ListNode next;//后驱指针 public ListNode(int val) { this.val = val; } } private ListNode head;//记录头节点 private ListNode last;//记录尾部节点 }


队列的实现

入队

因为我们使用的是链表来模拟实现,所以对于入队的 *** 作就相当于使用尾插法(头插法),入队图示:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第4张

当队列为空的时候需要进行特殊处理,不然会造成空指针异常,队列为空的时候让我们的头指针和尾指针都指向这个节点就可以,如果队列不为空就正常的使用尾插法,尾插法图示:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第5张

//入队 public void enqueue(int val) { ListNode newNode = new ListNode(val); if (head == null) { head = newNode; last = newNode; }else { newNode.pre = last; last.next = newNode; last = newNode; } }

出队

队列是个单向的数据结构,对于入队我们使用了尾插法,那么出队就需要使用删除头节点的方法,出队的图示如下:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第6张

出队实际上是对于队头节点的删除,所以当队内没有节点的时候我们就不能进行这样的 *** 作,我们直接抛出一个异常,在可以抛出的情况下,我们定义一个 val变量 来存放我们要删除的值,以便返回。当队列只有一个元素的时候要进行特殊处理,不然后面的程序会报空指针异常,这种情况下,我们需要先拿到头节点的值,然后将头节点置空,最后返回这个值;其余情况我们就正常进行删除 *** 作,先拿到头节点的值然后让头节点后移,再让改变现在头节点的前驱指针,让我们要删除的数据无法被访问,最后返回这个值

//出队 public int dequeue() { if (head == null) { throw new ExceptionOfEmpty("队列为空,无法 *** 作"); } int val = -1; //当队列只有一个元素的时候要进行特殊处理,不然后面的程序会报空指针异常 if (head.next == null) { val = head.val; head = null; last = null; return val; } //对于其他正常位置元素的处理 val = head.val; head = head.next; head.pre = null; return val; }

获取队头元素

获取队头元素则十分的简单,使用个临时变量拿到头节点的值然后返回就可以了

//拿出队列的首个元素进行查看 public int peek() { if (head == null) { throw new ExceptionOfEmpty("队列为空,无法 *** 作"); } int val = head.val; return val; }

获取队列长度

获取队列的长度也非常的简单,使用一个新的节点挨个变量,然后累加计数器最后返回就可以

//获取队列长度 public int size() { int count = 0; ListNode cur = head; while (cur != null) { cur = cur.next; count++; } return count; }


循环队列的概念

循环队列是一种特殊的队列数据结构,它允许队列的头尾相接,形成一个环。循环队列解决了普通队列的一些缺点,如空间浪费和在元素出队后无法再次入队的问题。

循环队列通常使用数组来实现,其内部有两个指针frontrear,分别指向队列的第一个元素和最后一个元素的下一个位置。初始化时,frontrear都指向数组的第一个位置。

当往循环队列中插入元素时,将元素放入rear指向的位置,并将rear指针向后移动一位。如果rear指针到达数组的尾部,则将其指向数组的起始位置。当从循环队列中删除元素时,将front指针向后移动一位,表示该元素已出队列。如果front指针到达数组的尾部,则将其指向数组的起始位置。

图示如下:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第7张

使用循环队列可以实现高效的元素入队和出队 *** 作,因为循环队列的空间利用率较高。当队列满时,rear指针和front指针会指向同一个位置,此时队列被认为是满的。而在普通队列中,即使队列中还有空闲位置,当rear指针到达数组的尾部时,无法再向队列中插入元素。

循环队列通过循环利用数组空间,解决了普通队列的空间浪费和无法再次入队的问题,提高了队列的空间利用率和性能。


循环队列的数据结构

对于循环队列,我们可以使用数组来模拟实现,分别有俩个指针指向整个数组的首部和尾部

public class MyCircularQueue { public int[] elem;//存放数据 public int front;//指向队头 public int rear;//指向队尾 MyCircularQueue(int k) { elem = new int[k]; } }


循环队列的实现

对于循环队列的实现,其实难点就在于判断队列的状态,分得清队列已满和队列为空的情况就可以,其余的 *** 作实际上都是非常简单的数组的添加和删除元素

另外很重要的一点就是,循环队列需要体现出循环的概念,所以不管是队头指针还是队尾指针,我们在 *** 作的时候都需要除以这个数组的模

判断队列是否为空

队列为空是怎么样的状态?为空,也就是说队列内什么都没有,队列的开始就是队列的结束,也就是队头指针和队尾指针指向同一个地方,如图所示:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第8张

//判空 front和rear相遇 public boolean isEmpty() { return front == rear; }

判断队列是否已满

队列已满是怎么样的状态?队列已满就是说队列每一个位置都有元素存放,这个情况下,如果队尾指针再往后走一步,就相当于回到了第二轮的起点,如图所示:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第9张

那么也就是说,当队尾指针再往后走一步的值除以整个队列的大小,就等于头指针的大小 

//判空 front和rear相遇 public boolean isFull() { return (rear + 1) % elem.length == front; }

入队

入队的时候,我们先要判断队列是否已满,满了就返回false表示入队失败;没有满的话就进行入队,也就是从数组的最后位置放个元素,然后再更改队尾指针指向,图示如下:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第10张

出队

出队的实现实际上就是对数组的第一个元素进行删除 *** 作,如图所示:

数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第11张

//出队 public boolean deQueue() { if (isEmpty()) { return false; } front = (front + 1) % elem.length; return true; }

得到队头元素

这样的 *** 作其实就是出队 *** 作的简化,拿到值返回即可,这里就不再赘述

//得到队头元素 public int Front() { if (isEmpty()) { return -1; } return elem[front]; }

得到队尾元素

这里有一点需要注意,当我们的队列只有一个元素的时候,是需要进行特殊处理的,不然就会出现数组越界的异常,毕竟数组不存在下标为-1的元素

//得到队尾元素 public int Rear() { if (isEmpty()) { return -1; } int index = (rear == 0) ? elem.length - 1 : rear - 1; return index; }




 数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第12张 本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第13张如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第14张有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见数据结构:图文详解 队列 | 循环队列 的各种 *** 作(出队,入队,获取队列元素,判断队列状态),第14张

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/13518107.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-12-27
下一篇 2023-12-31

发表评论

登录后才能评论

评论列表(0条)

保存