目录

一、队列

二、 Java里的Queue接口

1、概述

2、常用方法

1.入队

2.出队

3.获取队首元素

4、判空

三、单链表实现队列

1、准备字段

2、实现入队

3、实现出队

4、实现获取队首元素

5、实现判空

四、循环队列的实现

1、前言

2、字段准备

3、实现入队

4、实现出队

5、实现判空

6、实现获取队首元素

一、队列

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

二、 Java里的Queue接口

1、概述

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

2、常用方法

1.入队

2.出队

3.获取队首元素

4、判空

三、单链表实现队列

1、准备字段

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

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

2、实现入队

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

3、实现出队

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

4、实现获取队首元素

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

5、实现判空

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

四、循环队列的实现

1、前言

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

此时如果有上述情况，在入队时直接插入进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];
    }