Java-自定义队列

队列的概述

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

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

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

队列接口

packagecom.lineardatastructure.queue;/**
 * @author huanmin
 * @param <T>
 *//**
 * 自定义队列接口定义
 **/publicinterfaceQueue<T>{/**
     * 向队列中添加元素
     *
     * @param e
     */voidpush(T e);/**
     * 从队列中删除元素
     */Tpop();/**
     * 获取队列顶元素
     *
     * @return
     */Tpeek();/**
     * 获取队列中元素个数
     *
     * @return
     */intgetSize();/**
     * 判断队列中是否为空
     *
     * @return
     */booleanisEmpty();/**
     * 判断队列是否满
     * @return
     */booleanisFull();/**
     * 销毁队列
     */voidqueueDestroy();}

队列数组储结构

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

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

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

packagecom.lineardatastructure.queue;/**
 * @author huanmin
 * @param <T>
 */publicclassArrayQueue<T>implementsQueue<T>{privateObject[] arrayQueue;//队列数组privateint end=0;//队尾下标privateint begin=0;//队列开头privatefinalint CLEARTRASH=1000;//垃圾个数privateint length;publicArrayQueue(int size){
        arrayQueue=newObject[size];}publicArrayQueue(){
        arrayQueue=newObject[30];}@Overridepublicsynchronizedvoidpush(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=newObject[this.length];//java最快数组copy方式System.arraycopy(this.arrayQueue,0, target,0,this.arrayQueue.length);this.arrayQueue= target;//将原数组替换this.arrayQueue[this.end++]= e;}}@OverridepublicsynchronizedTpop(){if(this.isEmpty()){System.out.println("队列为空,请先向队列中添加元素");returnnull;}else{T t=(T)this.arrayQueue[this.begin];if(this.begin== CLEARTRASH){//队列向前移动,清理垃圾int i=this.CLEARTRASH+1;int i1=this.end-i;Object[] target=newObject[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;}}@OverridepublicsynchronizedTpeek(){return(T)this.arrayQueue[this.begin];}@OverridepublicsynchronizedintgetSize(){returnthis.end;}@OverridepublicsynchronizedbooleanisEmpty(){if(this.arrayQueue==null){returntrue;}returnthis.arrayQueue[this.begin]==null;}@OverridepublicsynchronizedbooleanisFull(){returnthis.arrayQueue.length==this.end;}@OverridepublicsynchronizedvoidqueueDestroy(){this.arrayQueue=null;this.end=0;}}

队列链表储结构

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

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

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

插入

取值

packagecom.lineardatastructure.queue;/**
 * @author huanmin
 * @param <T>
 */publicclassLinkedQueue<T>implementsQueue<T>{/**
     * 指向队头结点的引用
     */privateNode<T> first;/**
     * 指向队尾结点的引用
     */privateNode<T> end;/**
     * 元素个数
     */privateint size;privatestaticclassNode<T>{//下一个结点的引用Node<T> next;//结点数据T data;//节点构造器publicNode(T data,Node<T> next){this.data= data;this.next= next;}}@Overridepublicvoidpush(T e){//创建新节点Node<T> newNode=newNode<>(e,null);if(this.end==null){this.end= newNode;this.first= newNode;this.size++;return;}//改变头节点,和尾节点 ,A-b-c-dthis.end.next=newNode;// 这个动作其实是添加this.first的下一个节点 ,1,2,3,4this.end=newNode;//存放最后节点元素this.size++;}@OverridepublicTpop(){if(this.isEmpty()){returnnull;}T e=this.first.data;//改变队头节点引用,将下一个节点引用替换当前引用this.first=this.first.next;//如果元素为0,则将队尾节点引用置空if(--this.size==0){this.end=null;}return e;}@OverridepublicTpeek(){returnthis.first.data;}@OverridepublicintgetSize(){returnthis.size;}@OverridepublicbooleanisEmpty(){returnthis.first==null;}@OverridepublicbooleanisFull(){returnfalse;}@OverridepublicvoidqueueDestroy(){this.first=null;this.end=null;this.size=0;}}