一、队列结构（本文侧重于源码实现，基础理论不多赘述）

　　和栈一样，队列（queue)也是表，然而使用队列是在一端插入数据，在另一端删除数据。这里插入就是入队（enqueue),删除就是（dequeue).

       队列的核心思想是：“先进先出”

　　队列的实现方式有很多中，常见的有

　　（1）数组方式

　　（2）单链表方式

　　（3）双链表方式

　　（4）其他

二、数组方式实现队列结构（详细注释说明）

 　　我学习的时候，发现网上有很多数组实现队列，用得最多的是循环结构的方式，提供一下：（数组循环结构实现队列结构）

我这里并没有使用这种方式，下面的案例使用的是，在队列内部维护了2个数组，一个是执行数组（固定长度-不可扩展容量），一个等待数组（初始长度+System复制扩展容量），这个队列是永远支持入队操作的，当执行队列未满的时候，优先入队执行队列，当执行队列满了的时候，

会将数据继续入队到等待队列中。当执行队列出队数据的时候，也会检查等待队列中是否有数据，有的话会调取等待的数据到执行队列中。

提供一下类的结构图：

 源码如下：

MyQueueDefin3.java

1 package com.xfwl.algorithmAnalysis.heap;  2 import java.util.Arrays;  3 /**  4  * 自定义栈结构（基于数组的形式）  5  * 队列的核心思想：先进先出  6  * @function  日常学习测试  7  * @author 小风微凉  8  * @time  2018-5-20 上午8:41:27  9  */ 10 public class MyQueueDefin3
     
       { 11     /** 12      * 定义一个默认扩展容量：100 13      * 特别说明： 14      *           这个案例就不做数组容量扩展了，默认设置一个定量的数组。如果入队列达到上限则需要等待！ 15      * 所以又需要创建一个等待数组（这个可以扩容） 16      *          17      */ 18     private static final int DEFAULT_CAPACITY=10; 19     private static final int DEFAULT_WAIT_CAPACITY=10; 20     /** 21      * 数组队列容器：（执行队列-不支持扩展） 22      */ 23     private T[] arrQueue; 24     /** 25      * 等待队列数组（等待队列-支持扩展） 26      */ 27     private T[] waitQueue; 28     /** 29      * 计数器(执行队列中的数据条数) 30      */ 31     private int nodeCount=0; 32     /** 33      * 计数器(等待队列中的数据条数) 34      */ 35     private int nodeWaitCount=0; 36     /** 37      * 栈构造器 38      */ 39     public MyQueueDefin3(){ 40         //重置队列结构 41         this.arrQueue=(T[]) new Object[this.DEFAULT_CAPACITY]; 42         this.waitQueue=(T[]) new Object[this.DEFAULT_WAIT_CAPACITY]; 43         this.nodeCount=0; 44         this.nodeWaitCount=0; 45     } 46     /** 47      * 扩展数组容器(仅供waitQueue使用) 48      * @param newCapacity 新容量大小 49      * 说明：这里参考ArrayList源码中的一套扩展规则">>" 50      */ 51     public void ensureCapacity(int newCapacity){ 52         //大小范围检查 53         if(newCapacity<=this.size()){
   //不超过了当前容器的容量大小 54             return;//则不需要扩展容器容量 55         } 56         //数组初始值判断  57         if(this.waitQueue==null){ 58             waitQueue=(T[]) new Object[newCapacity]; 59             return;//第一次初始化进来 60         } 61         //需要扩展容器容量 62         T[] newItems=(T[]) Arrays.copyOf(this.waitQueue, newCapacity,this.waitQueue.getClass()); 63         this.waitQueue=newItems; 64     } 65     /** 66      * 执行队列容量 67      * @return 68      */ 69     public int size(){ 70         return this.nodeCount; 71     } 72     /** 73      * 等待队列容量 74      * @return 75      */ 76     public int waitSize(){ 77         return this.nodeWaitCount; 78     }     79     /** 80      * 数据入队列  81      * @param data  数据 82      * @return 83      */ 84     public boolean enqueue(T data){ 85         boolean bool=false; 86         try{ 87             //判断当前执行队列是否达到上限 88             if(this.size()==this.DEFAULT_CAPACITY){
   //执行队列已经上限，数据压入等待队列中 89                 //判断等待队列是否达到上限，是否需要扩容 90                 if(this.nodeWaitCount==this.waitQueue.length){
   //等待队列达到上限，需要扩容 91                     int newCapacity=this.waitSize()+this.waitSize()>>1;//扩展量：取当前容量的一半，且向下取整 92                     ensureCapacity(newCapacity);                     93                 }                 94                 //数据压入等待队列 95                 this.waitQueue[this.nodeWaitCount]=data; 96                 this.nodeWaitCount++;                 97                 bool=false;  98                 System.out.println("执行队列已满容量："+DEFAULT_CAPACITY+"，数据进入等待队列！等待队列容量："+this.waitSize()); 99             }else{
   //执行队列未满，可继续压入                100                 this.arrQueue[this.nodeCount]=data;101                 this.nodeCount++;102                 bool=true; 103                 System.out.println("数据进入执行队列！当前容量："+this.size()+",剩余容量："+(this.DEFAULT_CAPACITY-this.size()));104             }105         }catch(Exception e){106             e.printStackTrace();107             throw e;108         }109         return bool;    110     }111     /**112      * 数据出队列113      * @return114      */115     public T dequeue(){116         T data=null;117         if(this.size()==0){118             System.out.println("执行队列中无数据，请先插入数据！");119             return data;120         }        121         if(this.size()==this.DEFAULT_CAPACITY){
   //执行队列已经上限，出队的同时，调取等待队列的第一条数据到执行队列中122             //出执行队列123             data=this.arrQueue[0];124             //数组数据前移一位125             System.arraycopy(this.arrQueue, 1, this.arrQueue, 0, this.size()-1);126             this.arrQueue[this.size()-1]=null;127             this.nodeCount--;128             System.out.println("执行队列【已满】，出队数据："+data+",当前容量："+this.nodeCount+"，剩余熔炼"+(this.DEFAULT_CAPACITY-this.nodeCount));129             //调取判断130             if(this.waitSize()>0){131                 //调取等待队列的第一条数据到执行队列的最后一条132                 T tmpData=this.waitQueue[0];133                 this.arrQueue[this.DEFAULT_CAPACITY-1]=tmpData;134                 //等待队列数据变化：要移除的位置之后的数据前移一位135                 System.arraycopy(this.waitQueue, 1, this.waitQueue, 0, this.waitSize()-1);136                 //末尾的数据需要置空137                 this.waitQueue[this.waitSize()-1]=null;138                 //计数-1139                 this.nodeWaitCount--;140                 this.nodeCount++;141                 System.out.println("tips:等待队列调取一位数据补充执行队列，调取数据："+tmpData+"，当前执行队列当前容量："+this.nodeCount+"，剩余熔炼"+(this.DEFAULT_CAPACITY-this.nodeCount));142             }else{143                 System.out.println("tips:等待队列中无数据，当前执行队列当前容量："+this.nodeCount+"，剩余熔炼"+(this.DEFAULT_CAPACITY-this.nodeCount));144             }            145         }else{
   //仅仅执行队列中数据出列146             //出执行队列147             data=this.arrQueue[0];148             //数组数据前移一位149             System.arraycopy(this.arrQueue, 1, this.arrQueue, 0, this.size()-1);150             this.arrQueue[this.size()-1]=null;151             this.nodeCount--;152             System.out.println("执行队列【不满】，出队数据："+data+",当前容量："+this.nodeCount+"，剩余熔炼"+(this.DEFAULT_CAPACITY-this.nodeCount));153         }154         return data;        155     }    156     /**157      * 打印队列数据158      */159     public void printList(){160         System.out.println("----1·【执行队列】开始打印---------------------");161         for(int i=0;i
     

 测试类：Test3.java

1 package com.xfwl.algorithmAnalysis.heap; 2  3 public class Test3 { 4     public static void main(String[] args) { 5         //创建一个队列对象 6         MyQueueDefin3

 运行结果：

----1·【执行队列】开始打印---------------------队列为空，无数据返回！----1·【执行队列】结束打印-------------------------2·【等待队列】开始打印---------------------队列为空，无数据返回！----2·【等待队列】结束打印---------------------数据进入执行队列！当前容量：1,剩余容量：9数据进入执行队列！当前容量：2,剩余容量：8数据进入执行队列！当前容量：3,剩余容量：7数据进入执行队列！当前容量：4,剩余容量：6数据进入执行队列！当前容量：5,剩余容量：5数据进入执行队列！当前容量：6,剩余容量：4数据进入执行队列！当前容量：7,剩余容量：3数据进入执行队列！当前容量：8,剩余容量：2数据进入执行队列！当前容量：9,剩余容量：1数据进入执行队列！当前容量：10,剩余容量：0----1·【执行队列】开始打印---------------------数据-1数据-2数据-3数据-4数据-5数据-6数据-7数据-8数据-9数据-10----1·【执行队列】结束打印-------------------------2·【等待队列】开始打印---------------------队列为空，无数据返回！----2·【等待队列】结束打印---------------------执行队列已满容量：10，数据进入等待队列！等待队列容量：1执行队列已满容量：10，数据进入等待队列！等待队列容量：2执行队列已满容量：10，数据进入等待队列！等待队列容量：3----1·【执行队列】开始打印---------------------数据-1数据-2数据-3数据-4数据-5数据-6数据-7数据-8数据-9数据-10----1·【执行队列】结束打印-------------------------2·【等待队列】开始打印---------------------数据-11数据-12数据-13----2·【等待队列】结束打印---------------------执行队列【已满】，出队数据：数据-1,当前容量：9，剩余熔炼1tips:等待队列调取一位数据补充执行队列，调取数据：数据-11，当前执行队列当前容量：10，剩余熔炼0----1·【执行队列】开始打印---------------------数据-2数据-3数据-4数据-5数据-6数据-7数据-8数据-9数据-10数据-11----1·【执行队列】结束打印-------------------------2·【等待队列】开始打印---------------------数据-12数据-13----2·【等待队列】结束打印---------------------

 三、单链表方式实现队列结构

类结构图：

 MyQueueDefin.java类

1 package com.xfwl.algorithmAnalysis.heap;  2 /**  3  * 自定义栈结构（基于单链表的形式）  4  * 队列的核心思想：先进先出  5  * @function  日常学习测试  6  * @author 小风微凉  7  * @time  2018-5-20 上午8:41:27  8  */  9 public class MyQueueDefin
     
       { 10     /** 11      * 头结点 12      */ 13     private Node
      
        front;     14     /** 15      * 计数器 16      */ 17     private int nodeCount=0; 18     /** 19      * 队列构造器 20      */ 21     public MyQueueDefin(){ 22         //重置队列结构 23         front=new Node(null,null); 24         nodeCount=0; 25     } 26     /** 27      * 队列容量 28      * @return 29      */ 30     public int size(){ 31         return this.nodeCount; 32     } 33     /** 34      * 拿到最后一个结点（最新的入队列数据结点） 35      * @return 36      */ 37     private Node
       
         findLastNode(){ 38         Node
        
          tmp=this.front; 39         while(tmp.next!=null){ 40             tmp=tmp.next; 41         } 42         return tmp; 43     } 44     /** 45      * 数据入队列  46      * @param data  数据 47      * @return 48      */ 49     public boolean enqueue(T data){ 50         boolean bool=false; 51         try{ 52             //创建新鲜结点 53             Node
         
           newNode=new Node<>(data,null); 54             //拿到队列尾部结点 55             this.findLastNode().next=newNode; 56             //计数器+1 57             this.nodeCount++; 58             bool=true;  59         }catch(Exception e){ 60             e.printStackTrace(); 61             throw e; 62         } 63         return bool;     64     } 65     /** 66      * 数据出队列 67      * @return 68      */ 69     public T dequeue(){ 70         if(this.size()==0){ 71             System.out.println("空队列，请先插入数据！"); 72             return null; 73         } 74         T data=this.findNode(0).data; 75         this.front.next=this.findNode(0).next; 76         this.nodeCount--;         77         return data;         78     } 79     /** 80      * 根据索引值找到结点 81      * @param index 位置索引值 82      * @return 83      */ 84     private Node
          
            findNode(int index){ 85 if(index<0 || index>(this.size()-1)){ 86 throw new IllegalArgumentException("参数不合法，请重新输入！"); 87 } 88 //第一个数据结点 89 Node tmp=this.front.next; 90 for (int i = 0; i < this.size(); i++) { 91 if(index==i){ 92 break; 93 } 94 tmp=tmp.next; 95 } 96 return tmp; 97 } 98 /** 99 * 打印队列数据100 */101 public void printList(){102 System.out.println("-----------开始打印----------------");103 for(int i=0;i
           
            {115 /**116 * 结点数据域117 */118 private T data;119 /**120 * 结点指针域121 */122 private Node
            
              next;123 /**124 * 结点构造函数125 */126 public Node(T data,Node
             
               node){127 this.data=data;128 this.next=node;129 }130 }131 }
             
            
           
          
         
        
       
      
     

  测试类：Test.java

1 package com.xfwl.algorithmAnalysis.heap; 2 /** 3  * 测试类 4  * @function   5  * @author 小风微凉 6  * @time  2018-5-20 上午9:01:13 7  */ 8 public class Test { 9     public static void main(String[] args) {10         //创建队列对象11         MyQueueDefin

  运行结果：

-----------开始打印----------------队列为空，无数据！-----------结束打印---------------------------开始打印----------------当1个数据当2个数据当3个数据当4个数据当5个数据-----------结束打印---------------------------开始打印----------------当2个数据当3个数据当4个数据当5个数据-----------结束打印---------------------------开始打印----------------当2个数据当3个数据当4个数据当5个数据当6个数据-----------结束打印----------------

 四、双链表方式实现队列结构 

类结构图

MyQueueDefin2.java 

1 package com.xfwl.algorithmAnalysis.heap;  2   3 /**  4  * 自定义栈结构（基于双链表的形式）  5  * 队列的核心思想：先进先出  6  * @function  日常学习测试  7  * @author 小风微凉  8  * @time  2018-5-20 上午8:41:27  9  */ 10 public class MyQueueDefin2
     
       { 11     /** 12      * 头结点 13      */ 14     private Node
      
        front;     15     /** 16      * 尾结点 17      */ 18     private Node
       
         back;     19     /** 20      * 计数器 21      */ 22     private int nodeCount=0; 23     /** 24      * 队列构造器 25      */ 26     public MyQueueDefin2(){ 27         //重置队列结构 28         this.front=new Node(null,null,null); 29         this.back=new Node(null,null,null); 30         this.front.next=this.back; 31         this.back.prev=this.front; 32         nodeCount=0; 33     } 34     /** 35      * 队列容量 36      * @return 37      */ 38     public int size(){ 39         return this.nodeCount; 40     } 41     /** 42      * 拿到最后一个结点（最新的入队列数据结点） 43      * @return 44      */ 45     private Node
        
          findLastNode(){ 46         if(this.size()==0){ 47             return this.front; 48         } 49         return this.back.prev; 50     } 51     /** 52      * 数据入队列  53      * @param data  数据 54      * @return 55      */ 56     public boolean enqueue(T data){ 57         boolean bool=false; 58         try{ 59             //创建新鲜结点 60             Node
         
           newNode=new Node<>(data,null,null); 61             //拿到队列尾部结点 62             Node lastNode=this.findLastNode(); 63             lastNode.next=newNode; 64             newNode.prev=lastNode; 65             newNode.next=this.back; 66             this.back.prev=newNode; 67             //计数器+1 68             this.nodeCount++; 69             bool=true;  70         }catch(Exception e){ 71             e.printStackTrace(); 72             throw e; 73         } 74         return bool;     75     } 76     /** 77      * 数据出队列 78      * @return 79      */ 80     public T dequeue(){ 81         if(this.size()==0){ 82             System.out.println("空队列，请先插入数据！"); 83             return null; 84         } 85         Node
          
            deNode=this.findNode(0); 86 T data=deNode.data; 87 this.front.next=deNode.next; 88 deNode.next.prev=this.front; 89 this.nodeCount--; 90 return data; 91 } 92 /** 93 * 根据索引值找到结点 94 * @param index 位置索引值 95 * @return 96 */ 97 private Node
           
             findNode(int index){ 98 if(index<0 || index>(this.size()-1)){ 99 throw new IllegalArgumentException("参数不合法，请重新输入！");100 }101 //第一个数据结点102 Node tmp=this.front.next;103 for (int i = 0; i < this.size(); i++) {104 if(index==i){105 break;106 }107 tmp=tmp.next;108 }109 return tmp;110 }111 /**112 * 打印队列数据113 */114 public void printList(){115 System.out.println("-----------开始打印----------------");116 for(int i=0;i
            
             {128 /**129 * 结点数据域130 */131 private T data;132 /**133 * 结点前驱指针域134 */135 private Node
             
               prev;136 /**137 * 结点后驱指针域138 */139 private Node
              
                next;140 /**141 * 结点构造函数142 */143 public Node(T data,Node
               
                 prev,Node
                
                  next){144 this.data=data;145 this.prev=prev;146 this.next=next;147 }148 }149 }
                
               
              
             
            
           
          
         
        
       
      
     

  测试类：Test2.java 

1 package com.xfwl.algorithmAnalysis.heap; 2 /** 3  * 测试类 4  * @function   5  * @author 小风微凉 6  * @time  2018-5-20 上午9:01:13 7  */ 8 public class Test2 { 9     public static void main(String[] args) {10         //创建队列对象11         MyQueueDefin2

  运行结果：

-----------开始打印----------------队列为空，无数据！-----------结束打印---------------------------开始打印----------------当1个数据当2个数据当3个数据当4个数据当5个数据-----------结束打印---------------------------开始打印----------------当2个数据当3个数据当4个数据当5个数据-----------结束打印---------------------------开始打印----------------当2个数据当3个数据当4个数据当5个数据当6个数据-----------结束打印----------------