Java数据结构----------------队列（性质，功能，图解代码）

系统管理员 2023-10-02 13:03 18阅读 0赞

![b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png][]

**目录**

1.什么是队列？

2.队列的基本功能和结构

3.队列的基本功能图解实现

1.判断队列是否为空

2.返回队列中元素的个数

3.清空队列

4.入队

5.出队

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

## 1.什么是队列？ ##

某一天你没有吃早餐就去上课，饿的无精打采，于是中午一放学你就兴冲冲的冲去饭堂，但没想到一群上体育课的已经早已将窗口排的慢慢的，这时你想直接去窗口打饭，你刚走过去，前排的几位同学立马叫住了你：“喂，插队啊？”，他们长得高大威猛，于是你老实的从最后一位同学开始排队，慢慢的前面都打完了才到你。其实这时你就完成了一个从入队到出队的流程

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16][]

**像这种只能在一端进入，从另外一端出，先进先出的数据结构，我们就叫做队列。**这类似我们排队的情况，如果你插队是违反了规则，只能老实从后端进入，等前面的元素都走了才到你，最直观的就是我们日常生活中的排队情况。

## **2.队列的基本功能和结构** ##

解析：队列像栈一样，同样可以通过顺序表和链表来实现，当然使用链表更加方便我们进行操作，顺序表实现队列会大量的移动元素，就像我们排队要所有人慢慢往前走，非常不方便。首先有个内部类Node表示结点，成员属性有头结点以及尾结点，还有int类型变量N统计存储的元素个数。

ps：再次强调，头结点不存储元素，尾结点是可以存储的。构造方法中初始化时不能写this.Node=null这种，这样代表压根没有头结点，但是刚开始是确实没有尾结点，因为队列还是空的

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td> <pre>public boolean isEmpty()</pre> </td> 
   <td> <pre>判断队列是否为空</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public int size()</pre> </td> 
   <td> <pre>返回队列中元素的个数</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void clean()</pre> </td> 
   <td> <pre>清空队列</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void enqueue(T t) </pre> </td> 
   <td> <pre>入队</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T dequeue()</pre> </td> 
   <td> <pre>出队</pre> </td> 
  </tr> 
 </tbody> 
</table>

## 3.队列的基本功能图解实现 ##

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

//判断队列是否为空
        public boolean isEmpty() {
            return N == 0;
        }

解析：因为有N统计队列中的元素个数，所以直接返回N是否等于0即可。

### 2.返回队列中元素的个数 ###

//返回队列中元素的个数
        public int size() {
            return N;
        }

解析：同理于上面，返回N的值即可

### 3.清空队列 ###

public void clean(){
            N=0;
            head.next=null;
        }

解析：因为是单链表实现队列，访问队列中的任何元素，我们都只能通过头结点向后遍历，如果头结点的next指向为空，那我们什么也遍历不到，也就意味着队列为空了，此时别忘记将N置为0。

### 4.入队 ###

//入队
        public void enqueue(T t) {
            Node newNode = new Node(t, null);
            if (N == 0) {
                head.next = newNode;
                last = newNode;
            }else {
                last.next = newNode;
                last = newNode;
            }
            N++;
        }

解析：入队入队，顾名思义就排队嘛，那排队你只能排到最后，那我们肯定要先找到最后一个同学，同理我们要先找到最后一个结点。但是如果队列此时没有同学呢？说明你直接就成为了头结点的next，同时也是尾结点，这就是代码中我们先要判断N是否为0的情况。如果队列不为空，那我们就需要在最后一个结点补上新结点，同时让新节点成为尾结点，最后无论哪种情况都需要让N++。

### 5.出队 ###

//出队
        public T dequeue() {
            //如果队列为空
            if (isEmpty()) return null;
            //
            Node a = head.next;
            head.next = a.next;
            N--;
            return a.item;
        }

解析：出队就像你排队打饭打好了，就该端着饭盘走了，让你后面的同学也好上来打饭。同理我们需要判断队列是否为空，如果为空说明没有元素给我们出，那么就得返回null。如果有元素，操作就类似删除结点，删掉头结点的next，也就是即将队头元素，让队头元素的下一元素成为新的队头元素。

**ps:其实从栈看到队列，发现出栈入栈出队入队的功能都是在链表的增删功能上实现的，甚至后面更复杂的数据结构如二叉树等，也同样如此，所以学好基础的数据结构是重中之重，这里可以看看我前面的文章**

**附上全文代码可直接复制**

public class Queue<T> implements Iterable {
        //记录头结点
        private Node head;
        //记录元素个数
        private int N;
        //记录尾结点
        private Node last;
    
        private class Node {
            public T item;
            public Node next;
    
            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }
    
        public Queue() {
            this.head = new Node(null, null);
            this.last = null;
            this.N = 0;
        }
    
        //判断队列是否为空
        public boolean isEmpty() {
            return N == 0;
        }
    
        //返回队列中元素的个数
        public int size() {
            return N;
        }
    
        //清空队列
            public void clean(){
            N=0;
            head.next=null;
        }
    
        //入队
        public void enqueue(T t) {
            Node newNode = new Node(t, null);
            if (N == 0) {
                head.next = newNode;
                last = newNode;
            }else {
                last.next = newNode;
                last = newNode;
            }
            N++;
        }
    
        //出队
        public T dequeue() {
            //如果队列为空
            if (isEmpty()) return null;
            //
            Node a = head.next;
            head.next = a.next;
            N--;
            return a.item;
        }
    
        //为了折纸问题（树）实现的方法
        public Node dequeue2() {
            //如果队列为空
            if (isEmpty()) return null;
            //
            Node a = head.next;
            head.next = a.next;
            N--;
            return a;
        }
    }

1.**[Java----图解顺序表，手撕代码][Java----]**

2.[Java----单链表（图文详解）][Java---- 1]

3.[Java----双向链表（图文详解）][Java---- 2]

4.[Java----栈（图文实现，手撕代码）][Java---- 3]

![f704dcb374c688a57eae9f5dd97c3655.png][]

有问题可问，有错误请指正，多谢！

[b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png]: https://img-blog.csdnimg.cn/img_convert/b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/61df8871c55946928b36eebe3471c911.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[Java----]: https://blog.csdn.net/m0_57487901/article/details/120853794?spm=1001.2014.3001.5501
[Java---- 1]: https://blog.csdn.net/m0_57487901/article/details/120871022?spm=1001.2014.3001.5501
[Java---- 2]: https://blog.csdn.net/m0_57487901/article/details/120892159?spm=1001.2014.3001.5501
[Java---- 3]: https://blog.csdn.net/m0_57487901/article/details/120979515?spm=1001.2014.3001.5501
[f704dcb374c688a57eae9f5dd97c3655.png]: https://img-blog.csdnimg.cn/img_convert/f704dcb374c688a57eae9f5dd97c3655.png