数据结构：图文详解队列 | 循环队列的各种操作（出队，入队，获取队列元素，判断队列状态）

叁歲伎倆 2024-02-05 16:14 61阅读 0赞

![98f9e83e268945ff96b2134c64a5e01e.gif][]

--------------------

**目录**

队列的概念

队列的数据结构

队列的实现

入队

出队

获取队头元素

获取队列长度

循环队列的概念

循环队列的数据结构

循环队列的实现

判断队列是否为空

判断队列是否已满

入队

出队

得到队头元素

得到队尾元素

--------------------

## 队列的概念 ##

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

**图示如下：**

![4374cbac41a142379bfba3d36c017924.png][]

队列的特点是按照元素加入的先后顺序进行操作，先加入队列的元素会先被取出，后加入的元素会后被取出。这种特性常常被用于模拟实际生活中的排队场景，例如银行柜台排队、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;//记录尾部节点
    }

--------------------

## 队列的实现 ##

### 入队 ###

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

![b57d06000f4d4c448a7d09f1fc3f4808.png][]

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

![1aba831b1bf64f848c3dd9c1dde038dc.png][]

//入队
        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;
            }
        }

### 出队 ###

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

![95e908048e2d46be90ad77a22e6222bb.png][]

出队实际上是对于队头节点的删除，所以当队内没有节点的时候我们就不能进行这样的操作，我们直接抛出一个异常，在可以抛出的情况下，我们定义一个 **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;
        }

--------------------

## 循环队列的概念 ##

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

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

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

**图示如下：**

![2e0d369be6484793b7d737f0fcbf2f46.png][]

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

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

--------------------

## 循环队列的数据结构 ##

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

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

--------------------

## 循环队列的实现 ##

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

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

### 判断队列是否为空 ###

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

![3d8c6ba00e9944ef8735c3ab55de227a.png][]

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

### 判断队列是否已满 ###

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

![d2d70ec4b1c4459ba0faeab61d18fe7d.png][]

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

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

### 入队 ###

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

![45cd14731e164dfb87cc59865c6fffdc.png][]

### 出队 ###

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

![fc3f2ec48c6b4fefbf37a08e17854d7b.png][]

//出队
        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;
        }

--------------------

![b4e223eb39274c4790c1accda528968f.png][] **本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！**![dee54f8cb32a413fb28d115ba29feb97.png][]**如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！**![08cf81c9e3f84f6fb5e5805897ac6d8e.png][]**有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见**![08cf81c9e3f84f6fb5e5805897ac6d8e.png][]

[98f9e83e268945ff96b2134c64a5e01e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/4bc099914e17443f8e06f282b69a3eba.png
[4374cbac41a142379bfba3d36c017924.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b0f139d285d94ee59862c019d51b9259.png
[b57d06000f4d4c448a7d09f1fc3f4808.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/2df05e1b9f464e9ea35bf278fe4f9eb0.png
[1aba831b1bf64f848c3dd9c1dde038dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/884dcb04ec804fa9802dbd8e5dd64e6c.png
[95e908048e2d46be90ad77a22e6222bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/a2a9634af12242ee861e69c17c083af8.png
[2e0d369be6484793b7d737f0fcbf2f46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/128f08d21cbe4eef9f16afc58772e621.png
[3d8c6ba00e9944ef8735c3ab55de227a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/639c633ae7774a74abedd75ba96eebd8.png
[d2d70ec4b1c4459ba0faeab61d18fe7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/3306eadd482d4916a84690c5f89b5f3f.png
[45cd14731e164dfb87cc59865c6fffdc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/0b2bc7afe3d1422eb8eb83ec210b35d2.png
[fc3f2ec48c6b4fefbf37a08e17854d7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/cc5a52c64025473294745ee163330317.png
[b4e223eb39274c4790c1accda528968f.png]: https://img-blog.csdnimg.cn/b4e223eb39274c4790c1accda528968f.png
[dee54f8cb32a413fb28d115ba29feb97.png]: https://img-blog.csdnimg.cn/dee54f8cb32a413fb28d115ba29feb97.png
[08cf81c9e3f84f6fb5e5805897ac6d8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/34fd6a46d93e4957a1488b2d3f365f8d.png