队列的概述

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,…,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。

因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。

队列接口

package com.lineardatastructure.queue;
/** * @author huanmin * @param <T> */
/** * 自定义队列接口定义 **/
public interface Queue<T> {

    /** * 向队列中添加元素 * * @param e */
    void push(T e);

    /** * 从队列中删除元素 */
    T pop();

    /** * 获取队列顶元素 * * @return */
    T peek();

    /** * 获取队列中元素个数 * * @return */
    int getSize();

    /** * 判断队列中是否为空 * * @return */
    boolean isEmpty();

    /** * 判断队列是否满 * @return */
    boolean isFull();

    /** * 销毁队列 */
    void queueDestroy();
}

队列数组储结构

队列的入队和出队操作在不同端。采用数组来实现时，如果队头在数组元素最小索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为Ｏ(1), 但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)(但是也是有优化办法看下图)。

当浪费到指定数量内存后我们进行迁移数据

当队列满了,我们就进行扩容

package com.lineardatastructure.queue;
/** * @author huanmin * @param <T> */
public class ArrayQueue<T> implements Queue<T> {

    private Object[] arrayQueue;//队列数组
    private int end = 0;//队尾下标
    private int begin=0;//队列开头
    private final int CLEARTRASH = 1000; //垃圾个数
    private  int length;

    public ArrayQueue(int size) {
        arrayQueue = new Object[size];
    }

    public ArrayQueue() {
        arrayQueue = new Object[30];
    }

    @Override
    public synchronized void push(T e) {
        if (!this.isFull()) {
            this.arrayQueue[this.end++] = e;
        } else {
            //队列满了进行扩容
            this.length = this.arrayQueue.length + (int) (this.arrayQueue.length * 0.75 + 1);
            Object[] target = new Object[this.length];
            //java最快数组copy方式
            System.arraycopy(this.arrayQueue, 0, target, 0, this.arrayQueue.length);
            this.arrayQueue = target;//将原数组替换

            this.arrayQueue[this.end++] = e;
        }

    }

    @Override
    public synchronized T pop() {
        if (this.isEmpty()) {
            System.out.println("队列为空,请先向队列中添加元素");
            return null;
        } else {
            T t = (T) this.arrayQueue[this.begin];
            if (this.begin == CLEARTRASH) {
                //队列向前移动,清理垃圾
                int i = this.CLEARTRASH + 1;
                int i1 =this.end-i ;
                Object[] target = new Object[this.length];
                System.arraycopy(this.arrayQueue, i, target, 0, i1);
                this.arrayQueue = target;
                this.begin = -1;
                this.end=this.end-i;
            }
            this.begin++;

            return t;
        }

    }

    @Override
    public synchronized T peek() {
        return (T) this.arrayQueue[this.begin];
    }

    @Override
    public synchronized int getSize() {
        return this.end;
    }

    @Override
    public synchronized boolean isEmpty() {
        if (this.arrayQueue == null) {
            return true;
        }
        return this.arrayQueue[this.begin] == null;
    }

    @Override
    public synchronized boolean isFull() {
        return this.arrayQueue.length == this.end;
    }

    @Override
    public synchronized void queueDestroy() {
        this.arrayQueue = null;
        this.end = 0;
    }
}

队列链表储结构

队列的入队和出队操作在不同端。采用链表来实现时，队列头和队列尾部, 时间复杂度都是Ｏ(1) 使用链式结构实现队列相比顺序结构的实现更加简单。

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点

空队列时，头指针front和尾指针rear都指向头结点。

插入

取值

package com.lineardatastructure.queue;

/** * @author huanmin * @param <T> */
public class LinkedQueue<T> implements  Queue<T>{
    /** * 指向队头结点的引用 */
    private Node<T> first;

    /** * 指向队尾结点的引用 */
    private Node<T> end;
    /** * 元素个数 */
    private int size;
    private static class Node<T> {
        //下一个结点的引用
        Node<T> next;
        //结点数据
        T data;

        //节点构造器
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    @Override
    public void push(T e) {
        //创建新节点
        Node<T> newNode = new Node<>(e, null);
        if (this.end == null) {
            this.end = newNode;
            this.first = newNode;
            this.size++;
            return;

        }
        //改变头节点,和尾节点 ,A-b-c-d
        this.end.next=newNode;// 这个动作其实是添加this.first的下一个节点 ,1,2,3,4
        this.end=newNode;    //存放最后节点元素
        this.size++;

    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
           return  null;
        }
        T e = this.first.data;
        //改变队头节点引用,将下一个节点引用替换当前引用
        this.first = this.first.next;
        //如果元素为0,则将队尾节点引用置空
        if (--this.size == 0) {
            this.end = null;
        }
        return e;

    }

    @Override
    public T peek() {
        return this.first.data;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.first == null;
    }

    @Override
    public boolean isFull() {
        return false;
    }

    @Override
    public void queueDestroy() {
        this.first=null;
        this.end=null;
        this.size=0;
    }
}

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^_^