【数据结构】队列与Queue接口

墨蓝 2023-09-27 13:26 152阅读 0赞

**目录**

一、队列

二、 Java里的Queue接口

1、概述

2、常用方法

1.入队

2.出队

3.获取队首元素

4、判空

三、单链表实现队列

1、准备字段

2、实现入队

3、实现出队

4、实现获取队首元素

5、实现判空

四、循环队列的实现

1、前言

2、字段准备

3、实现入队

4、实现出队

5、实现判空

6、实现获取队首元素

## 一、队列 ##

队列是一种操作受限的线性表，它与栈不同的是，栈是特点是先进后出而队列是先进先出，比如排队买早饭，先到先排到前面的人先买到先走。队列这一数据结构只允许在队首出数据，在队尾插入数据。

![17dbd8cffdd6413b9f4ac6fbd0d78c9a.png][]

## 二、 Java里的Queue接口 ##

### 1、概述 ###

在Java里Queue是一个接口，其内部方法主要有入队出队等，有很多实现他的类比如我们之前说到过的LinkedList，在Java里队列的使用可以分为阻塞队列（BlockingQueue）与非阻塞队列还有双端队列（Deque），一般多线程情况下我们常常使用阻塞队列实现生产者消费者模型

### 2、常用方法 ###

![862ffde4f5104999aa701bfb10c341ff.png][]

#### 1.入队 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>offer</td> 
   <td>入队失败返回false</td> 
  </tr> 
  <tr> 
   <td>add</td> 
   <td>入队失败抛出异常</td> 
  </tr> 
 </tbody> 
</table>

#### 2.出队 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>poll</td> 
   <td>队空出队返回空指针</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>队空出队抛出异常</td> 
  </tr> 
 </tbody> 
</table>

#### 3.获取队首元素 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>peek</td> 
   <td>队空时返回空指针</td> 
  </tr> 
  <tr> 
   <td>element</td> 
   <td>队空时抛出异常</td> 
  </tr> 
 </tbody> 
</table>

### 4、判空 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>isEmpty</td> 
   <td>判断队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

## 三、单链表实现队列 ##

### 1、准备字段 ###

单链表实现队列时，需要连个指针一个指向队首一个指向队尾

public class MyQueueByList {
        public Node first;    //队首指针
        public Node last;     //队尾指针
        
    }

### 2、实现入队 ###

入队操作就是插入到队尾，也就是单链表的尾插操作

![a7d2588fee9042959e097491147837bc.png][]

### 3、实现出队 ###

出队操作是将队首元素删除然后返回其值，类似于单链表删除头节点

![bb1f79f522734288ac5510fd8dcc302b.png][]

### 4、实现获取队首元素 ###

与出队操作不同的是该操作不用删除

![9746b6ad42dd4df483d76fcc484ab642.png][]

### 5、实现判空 ###

当队首节点为空时队列为空

![3dec3801f6134380a547431da175769b.png][]

## 四、循环队列的实现 ##

### 1、前言 ###

如果使用普通的数组去实现队列这一数据结构时，会有一个很严重的问题----内存浪费。如果我们使用普通数组实现时，初始长度为5，那么我们先入队5个元素，然后此时在入队时需要扩容，但是如果在满的情况下出队后再入队，此时由于要在队尾插入，还是需要去扩容，然后下标为0的空间则被浪费，循环往复内存浪费严重，如果我们能将数组“卷”起来变成一个“⚪”

![e8e768df2e7949af92797ce9c1ea1de2.png][]

此时如果有上述情况，在入队时直接插入进0下表依次类推。此处又存在一个问题，就是我们如何去区别队列到底是满了还是为空，空的时候队首下标与队尾下标相同，满时也一样，这一问题有多个解决办法，以下使用浪费一个空间的办法，就是在数组的最后一个位置不插入元素，此时如果队首与队尾下标相同时为空，如果队尾下标的下一个与队首下标相同则为满

### 2、字段准备 ###

基于上述情况，我们需要一个数组，一个指向队首的下标，一个指向队尾的下标

public class MyQueueByArray {
        private int[] elem;           //数组
        private int front;            //队首下标
        private int rear;             //队尾下标
    }

### 3、实现入队 ###

此时我们需要处理的点有：如果队列数组长度为5，当下标4的位置有数据而下标为0的位置没有元素，再插入时理应插入下标0位置，但是怎么让队尾下标变为0呢，有两种办法一种是，每次插入后判断一些队尾下标是不是4了，如果是4就在if语句里置为0；第二个办法是，每次入队操作后队尾下标自增改为 (队尾下标+1) % 数组的长度。下面出队操作也有以下情况。

/**
         * offer
         * @param data
         */
        public void offer(int data){
            if(isFull()){
                return;
            }
            
            elem[rear] = data;
            rear = (rear + 1) % elem.length;
        }
    
        /**
         * 判空
         * @return
         */
        public boolean isEmpty(){
            return front == rear;
        }
    
        /**
         * 判满
         * @return
         */
        private boolean isFull(){
            return (rear + 1) % elem.length == front;
        }

### 4、实现出队 ###

出队将队首元素记录并将队首下标自增删除，此处删除并不是将数据正在删除，而是改变队首下标让其被标志为一个空的位置

/**
         * poll
         * @return
         */
        public Integer poll(){
            //1.判空
            if(isEmpty()){
                return null;
            }
    
            //2.出队
            int frontValue = elem[front];
            front = (front + 1) % elem.length;
    
            //3.返回值
            return frontValue;
        }

### 5、实现判空 ###

由于我们使用了浪费一个空间的办法，因此空时队首下标与队尾下标相同

/**
         * 判空
         * @return
         */
        public boolean isEmpty(){
            return front == rear;
        }

### 6、实现获取队首元素 ###

根据队首下标获取队首元素

/**
         * peek
         * @return
         */
        public Integer peek(){
            //1.判空
            if(isEmpty()){
                return null;
            }
    
            //2.返回队首元素
            return elem[front];
        }

[17dbd8cffdd6413b9f4ac6fbd0d78c9a.png]: https://img-blog.csdnimg.cn/17dbd8cffdd6413b9f4ac6fbd0d78c9a.png
[862ffde4f5104999aa701bfb10c341ff.png]: https://img-blog.csdnimg.cn/862ffde4f5104999aa701bfb10c341ff.png
[a7d2588fee9042959e097491147837bc.png]: https://img-blog.csdnimg.cn/a7d2588fee9042959e097491147837bc.png
[bb1f79f522734288ac5510fd8dcc302b.png]: https://img-blog.csdnimg.cn/bb1f79f522734288ac5510fd8dcc302b.png
[9746b6ad42dd4df483d76fcc484ab642.png]: https://img-blog.csdnimg.cn/9746b6ad42dd4df483d76fcc484ab642.png
[3dec3801f6134380a547431da175769b.png]: https://img-blog.csdnimg.cn/3dec3801f6134380a547431da175769b.png
[e8e768df2e7949af92797ce9c1ea1de2.png]: https://img-blog.csdnimg.cn/e8e768df2e7949af92797ce9c1ea1de2.png