Java数据结构——队列

淡淡的烟草味﹌ 2022-09-17 04:27 297阅读 0赞

### 文章目录 ###

*   *  前言
     *  一、队列
     *   *  1.概念
         *  2.Java当中的队列
         *  3.实例化对象
         *  4.双端队列 (Deque)
         *  5.队列的常用方法
     *  二、Java实现简单队列
     *  三、循环队列
     *   *  设计循环队列
     *  循环队列的具体实现

## 前言 ##

最近博主在学习JavaWeb的过程中，讲到了具体线程的知识，在写生产与消费者模型的具体代码时，发现涉及到了循环队列的知识，于是打算再次复习一下循环队列的具体编写

我们先复习一下队列的相关知识

## 一、队列 ##

### 1.概念 ###

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

> 进行插入操作的一端称为队尾（rear）

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

### 2.Java当中的队列 ###

我们来看一下Java集合当中的有关队列的相关接口和类

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WiJ3e89S-1635256492714)(0ACD8A46870E4346B757757C5FB3E951)\]][img-WiJ3e89S-1635256492714_0ACD8A46870E4346B757757C5FB3E951]

我们可以看到 Queue 队列这个接口 底层可以是链表或者 顺序表来实现的 ，而在Java当中队列使用双端队列来进行维护的，同时 Deque 双端队列 也继承了Queue 这个接口

### 3.实例化对象 ###

我们要想实例化具体队列的对象，必须new 一个 LinkedList 这个类出来。

Queue<Integer> queue = new LinkedList<>();
            Deque<Integer> deque = new LinkedList<>();
            LinkedList<Integer> queue2 = new LinkedList<>();

### 4.双端队列 (Deque) ###

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

### 5.队列的常用方法 ###

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AG2rZ6b0-1635256492716)(D639AF97D9A244B39DCEAA42E13A6D95)\]][img-AG2rZ6b0-1635256492716_D639AF97D9A244B39DCEAA42E13A6D95]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fFyODzgy-1635256492718)(7AC9B01013EE4490AC427D0FC1042BB8)\]][img-fFyODzgy-1635256492718_7AC9B01013EE4490AC427D0FC1042BB8]

> Deque 我们一看就知道Deque双端队列的方法比 Queue的方法多，因为双端队列可以可以从队头出（pollFirst()）、队尾出（pollLast()）,还可以从队头入（offerFirst（））、队尾入（offerLast（））

大家光看可能不太熟悉，我带着大家一块写代码来使用队列的一些常见方法

**创建一个实例化对象**

Queue<Integer> queue = new LinkedList<>();

**入队操作**

Queue 这个接口中给我们提供了 offer() 这个方法来进行入队操作

给这个队列进行入队操作，添加一些元素（入队操作使用的是尾插法）

queue.offer(1);
            queue.offer(2);
            queue.offer(3);
            queue.offer(4);

我们在队列中添加了四个元素，如下图所示  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kegQIktP-1635256492719)(EB55EEB2860E46B5AA30D57F0E533DAD)\]][img-kegQIktP-1635256492719_EB55EEB2860E46B5AA30D57F0E533DAD]

现在队头元素是1，我们使用peek方法查看一下队首元素

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mqKV8AgP-1635256492720)(0D45467949BB4773BF065AA93C87838F)\]][img-mqKV8AgP-1635256492720_0D45467949BB4773BF065AA93C87838F]

**出队操作**

Queue 这个接口给我们提供了 poll()方法,返回队首元素并删除

也提供了 peek()方法，返回队首元素不删除

queue.poll();
       queue.poll();

我们将之前入队的元素进行出队两次，现在队首元素是3

查看一下

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nUet5tDL-1635256492721)(2B34B566402540759D3CDF062C587989)\]][img-nUet5tDL-1635256492721_2B34B566402540759D3CDF062C587989]

**判断是否为空**

Queue 提供了 isEmpty() 判断队列是否为空，返回值是 true 或 false

// 在进行两次出队操作，此时队列应该为空
             queue.poll();
             queue.poll();
            System.out.println(queue.isEmpty());

运行结果

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NKxDkiTo-1635256492722)(FFF6B1D87B74427AB4C5DAA153047BF0)\]][img-NKxDkiTo-1635256492722_FFF6B1D87B74427AB4C5DAA153047BF0]

## 二、Java实现简单队列 ##

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

在这里我们用 链表来实现 队列的内部常见方法

// 用单链表来实现简单的队列内部方法
    
    
    // 先建立一个Node类，队列中的每个元素都相当于一个节点
    class Node{
        
        public  int val;
        public Node next;
        // 写一个这个类的构造方法
    
        public Node(int val) {
        
            this.val = val;
        }
    }
    
    public class MyQueue {
        
        // 我们想呀，一个队列肯定是有队头，也肯定有一个队尾的
        // 所以定义 队头和队尾
        private Node first ;
        private Node last;
    
        // 入队
        // 入队这里要用到尾插法
        public void offer(int val){
        
    
            Node cur = new Node(val);
    
            // 第一次插入时，我们要把头尾指针指向这个节点
            if(this.first == null){
        
                this.first = cur;
                this.last = cur;
            }else{
        
                // 不是第一次插入，那么就用尾插法的思想进行插入元素
                this.last.next  =cur;
                this.last = cur;
    
            }
    
        }
    
    
        // 出队
        public int poll(){
        
            if(isEmpty()){
        
                throw new UnsupportedOperationException("队列为空");
            }
    
            int ret = this.first.val;
            this.first = this.first.next;
            return ret;
        }
    
    
        // 得到队头元素但不删除
        public int peek(){
        
            if(isEmpty()){
        
                throw new UnsupportedOperationException("队列为空");
            }
    
            int ret = this.first.val;
            return ret;
        }
    
    
        // 队列是否为空
        public boolean isEmpty(){
        
            if(this.first== null){
        
                return true;
            }
            return false;
        }
    
    }

## 三、循环队列 ##

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

环形队列通常使用数组实现

### 设计循环队列 ###

我们就借助一道题来开启今天的设计循环队列吧…

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5XYPhNPU-1635256492723)(88E33236BACE4AFFA7CC02C5822015A3)\]][img-5XYPhNPU-1635256492723_88E33236BACE4AFFA7CC02C5822015A3]

这道题让我们来设计一个循环队列，并且把相关方法给实现

我们先来简单了解一下循环队列的结构

循环队列的底层其实是一个数组，为什么是循环呢？

就是我们来看

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]

在这样的一个数组中，如果我们每一个格子都放满了，将队首元素出队，还想入一个元素，那么就从数组的0下标继续存储

这样的数组模型可能不太好理解，我们可以把这个数组看成环形的数组空间

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6YoRAOBA-1635256492724)(655D477BA5C64C938476CCC36FE5D5DD)\]][img-6YoRAOBA-1635256492724_655D477BA5C64C938476CCC36FE5D5DD]

> front 是队首元素的下标

> rear 是当前可存放元素的下标

当然我们能够想得到 入队出队的方式：

> 假如要入一个元素x,x 存放到 elem\[rear\],rear++;  
> 假如要出一个元素x，直接 front++;

我们在这个环形的空间内不断入队出队，可以实现循环的效果

了解了循环队列的结构，那么随之而来的问题就很多了

**第一个问题：front 和 rear 相遇之后到底是满还是空呢？**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]

上图有两种情况，

> 第一种：当队列存满之后，front和rear就会相遇  
> 第二种，当队列为空时，front 和rear 也会相遇

**第二个问题：rear 每次存放完成之后，能不能进行 rear= rear+1？**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vmx9BLMC-1635256492726)(8E2CE722FFDB4C5AAD28E7B6F5543390)\]][img-Vmx9BLMC-1635256492726_8E2CE722FFDB4C5AAD28E7B6F5543390]

在这种情况下，我们想想继续存入元素，那么 rear 如何从下标7 到下标1呢？

**第三个问题： 每次出队操作时，能不能进行 front = front+1？**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RCr0arp6-1635256492727)(C14596C984094C628F4089E4DFA771B7)\]][img-RCr0arp6-1635256492727_C14596C984094C628F4089E4DFA771B7]

这种情况下，我们还想继续出队，可以 front = front+1 吗？

我们接下来逐一解决这些问题

首先第一个问题，

> rear 是代表当前可以存放数组元素的下标

因为 front 、rear 相遇无法判断满还是空，所以我们干脆浪费一个数据元素的空间，最后一个空间不放元素，帮我们来判断是空还是满

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]

我们现在想把 89 放到这个队列当中，但是每次放入元素时都要判断队列是否已经满了，那么此时我们看一下 rear下标的下一个 是不是 front，如果是的话就说明满了。

**所以解决第一个问题是怎样解决的呢？**

每次在放元素的时候都去判断当前rear 的下一个是不是 front，如果是就满了！！

**第二、三问题怎么解决呢？**

数组下标循环的小技巧

数组下标index 是 0、1、2、3、4、5、6、7

我们通过简单的运算就可以得到循环的下标

> (index+1)% length

我们来试一试

> 当 index = 7 ，( index+1 )% length = 0

成功的实现了数组下标的循环操作

解决了这三个问题，我们来实现循环队列的具体方法

## 循环队列的具体实现 ##

class MyCircularQueue {
        
            private int front;
            private int rear;
            private int[] elem;
    
    
            public MyCircularQueue(int k) {
        
             // 构造方法
                this.front = 0;
                this.rear = 0; // 队首队尾下标都初始化为0
                this.elem = new int[k]; // new 一个 k大小的数组
            }
    
            // 入队操作
            public boolean enQueue(int value) {
        
    
                // 如果队列已经满了，那么入队失败
                if(isFull()) return false;
    
                // 往rear 下标存放元素，之后rear向后走一格
                   this.elem[this.rear] = value;
                   this.rear = (this.rear+1)%this.elem.length;
                   return true;
    
            }
    
            public boolean deQueue() {
        
            //出队操作
                if(isEmpty()){
        
                    // 如果队列为空，那么出队失败
                    return false;
                }
                this.front = (this.front+1)%this.elem.length;
                return true;
            }
    
            public int Front() {
        
                //        得到队首元素
                if(isEmpty()){
        
                    // 如果队列为空，那么返回-1
                    return -1;
                }
                return this.elem[this.front];
            }
    
            public int Rear() {
        
    //        得到队尾元素
                if(isEmpty()){
        
                    // 如果队列为空，那么返回-1
                   return -1;
                }
                // 如果队列不为空，那么返回rear的前一格元素，注意rear==0的情况
                //rear == 0 的这种情况，前一个是数组的最后一个下标
                int index = (this.rear ==0)? this.elem.length-1: this.rear-1;
                return this.elem[index];
            }
    
            public boolean isEmpty() {
        
                // 只要 rear 和 front 相遇时那么说明队列为空
              if(this.rear==this.front){
        
                  return true;
              }
              return false;
            }
    
            public boolean isFull() {
        
    
                // 如果front的前一格是rear 的话，那么就说明队列是满的
    
                // 注意千万不要直接 front-1==rear,如果front ==0 ，那么就无法判断了
                // 一定要考虑 front == 0 的这种情况，前一个是数组的最后一个下标
    
              int index = (this.front ==0)? this.elem.length-1: this.front-1;
              if(index == rear){
        
                  return true;
              }
              return false;
            }
    }

我们将这个代码进行OJ测试，

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CpyLZPPL-1635256492729)(BABD30D144B7411CB2DE09B0CA90F439)\]][img-CpyLZPPL-1635256492729_BABD30D144B7411CB2DE09B0CA90F439]

我们发现并没有通过测试，我们通过输出来看一下原因：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0Hu8HDFI-1635256492729)(5E45F5F867084B0D9D32C06491B68F21)\]][img-0Hu8HDFI-1635256492729_5E45F5F867084B0D9D32C06491B68F21]

为什么会出现这样的结果呢？

在构造函数时传入的参数是3，预期结果是能够入三个元素才满，但是我们定义的循环队列必然会浪费一个空间，所以只能存两个元素，插入第三个元素的时候就失败了。

这个问题很好解决，我们在构造函数这里定义数组的空间大上一格,new int\[k+1\]，这样这个队列中就可以插入k 个元素

public MyCircularQueue(int k) {
        
             // 构造方法
                this.front = 0;
                this.rear = 0; // 队首队尾下标都初始化为0
                this.elem = new int[k+1]; // new 一个 k+1大小的数组
            }

再来提交OJ测试

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T7FsChju-1635256492730)(874F0D4DCB244FA2AAAA4F7EA2A09A0B)\]][img-T7FsChju-1635256492730_874F0D4DCB244FA2AAAA4F7EA2A09A0B]

通过测试！！

好了，这一节我们主要复习了队列的相关知识，了解了循环队列如何具体实现，如果感兴趣的同学可以自己实现一下双端队列的具体代码，希望大家多多练习！！

**谢谢欣赏！**

[img-WiJ3e89S-1635256492714_0ACD8A46870E4346B757757C5FB3E951]: /images/20220828/ac1123aa17444db08bb36ddd93b6ed73.png
[img-AG2rZ6b0-1635256492716_D639AF97D9A244B39DCEAA42E13A6D95]: /images/20220828/c357ced3048e47269a79c1f7a2bb5d98.png
[img-fFyODzgy-1635256492718_7AC9B01013EE4490AC427D0FC1042BB8]: /images/20220828/301141795eed4d698993725d43a85539.png
[img-kegQIktP-1635256492719_EB55EEB2860E46B5AA30D57F0E533DAD]: /images/20220828/8b80c743761349f0a8cefc7dd0b60c87.png
[img-mqKV8AgP-1635256492720_0D45467949BB4773BF065AA93C87838F]: /images/20220828/a81144f685f04e11bbee5583bcda38e2.png
[img-nUet5tDL-1635256492721_2B34B566402540759D3CDF062C587989]: /images/20220828/6f40bc198d38482781c7ba8ebbdd7372.png
[img-NKxDkiTo-1635256492722_FFF6B1D87B74427AB4C5DAA153047BF0]: /images/20220828/efc2ca0321de488086a1ec48599799c0.png
[img-5XYPhNPU-1635256492723_88E33236BACE4AFFA7CC02C5822015A3]: /images/20220828/05fc6c67f7964210b4e2ac769a2db5ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fb514e6577674f90948895a9cc664ba4.png
[img-6YoRAOBA-1635256492724_655D477BA5C64C938476CCC36FE5D5DD]: /images/20220828/4afbf72dd99f4e6aa28da3603c5ad02a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/43b6d3290e0143c4bbca364bf6cf4735.png
[img-Vmx9BLMC-1635256492726_8E2CE722FFDB4C5AAD28E7B6F5543390]: /images/20220828/32e3e580763d4a148fa47e41a1237f39.png
[img-RCr0arp6-1635256492727_C14596C984094C628F4089E4DFA771B7]: /images/20220828/d7701ae32591493c82afca4353d61f90.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/63afea39009c4c59ba4705ddd93d32dc.png
[img-CpyLZPPL-1635256492729_BABD30D144B7411CB2DE09B0CA90F439]: /images/20220828/ec8d145298174242bdfa9ba235a23720.png
[img-0Hu8HDFI-1635256492729_5E45F5F867084B0D9D32C06491B68F21]: /images/20220828/3fe2229979fa4f408ef652da5efb91c1.png
[img-T7FsChju-1635256492730_874F0D4DCB244FA2AAAA4F7EA2A09A0B]: /images/20220828/2e118e45b4ee44dbba7d8e38fa581987.png