前言：
队列是一种特殊的线性表，他的特殊性体现在只能在尾部进行插入，头部进行删除，所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的，而线性表又有顺序表和链表两种，所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用单链表来实现的队列–链队列。若是需要查看顺序队列实现请点这里： 顺序队列
一、实现过程
1.提供队列的接口：IQueue
该接口定义了队列中必须实现的方法，因此在队列实现时只需要继承该接口然后正确实现该接口中的方法即可。无论是顺序队列还是链队列。都可以通过实现该接口来实现，下面是该接口中具体定义的方法。
public interface IQueue { void clear(); boolean isEmpty(); int length(); Object peek();//查看队列头元素 void offer(Object object) throws Exception;//入队 Object poll();//出队 }
2.提供节点类：Node
因为链队列的底层是单链表，因此我们必须要为单链表提供节点类，节点类需要包含两部分：一部分是数据域用以存储数据；一部分是指针域用以存储指向下一节点的指针。同时需要提供相应的构造方法，代码如下：
public class Node { public Object object; public Node next; public Node(){ } public Node(Object object){ this.object = object; } public Node(Node next){ this.next = next; } public Node(Object object,Node next){ this.object = object; this.next = next; } @Override public String toString() { return "Node{" + "object=" + object + ", next=" + next + '}'; } }
3.提供链队列的实现：LinkedQueue
链队列因为数据流向都是单向的，因此使用单链表就可以实现。又根据队列的“先进先出”规则我们可以知道我们需要同时关注首结点和尾结点，因此需要声明尾结点，这样我们在尾部插入时就会很方便，若是不使用尾结点的话，每次队列的插入操作就需要遍历到链表的尾部进行插入，这样每次插入的时间复杂度都变成了O(n)，这是很耗费性能的。因此我们需要提供带有尾结点的单链表，同时提供首结点，用以标注链表的开始，注意这里是首结点不是头结点。首结点与头结点的区别是首结点存储数据，头结点是不存储数据的。提供了首结点和尾结点后我们还需要在构造器中对他们进行初始化。代码如下：
/** * 链式队列就相当于，既含有首结点，也含有尾结点的单链表 * @author pcc * @version 1.0.0 * @className LinkedQueue * @date 2021-04-29 09:55 */ public class LinkedQueue implements IQueue{ Node front;//首结点 Node rear;//尾结点 public LinkedQueue(){ front = rear = new Node(); } @Override public void clear() { front = null; rear = null; } }
4.提供清空（clear）、判空（isEmpty）、队列长度(length)等方法
这些方法的实现就比较简单，就一起简单说下就好。初始状态下front和rear节点相等且他们的数据域都是null，因此清空时我们就将队列还原成这个样子即可；判空也是判断首结点和尾结点是不是在初始装态，是的话自然就是空的了；队列长度的求取有两种方案，一种是维护一个计数器每次出队和入队时进行计算。另外一种就是遍历链表计算结点个数，笔者使用的是遍历链表，代码实现如下：
@Override public void clear() { front = rear = new Node(); } @Override public boolean isEmpty() { if(front == rear && front.object == null) return true; return false; } @Override public int length() { int length = 0; Node temp = front; if(front!=rear) while(temp!=null){ length++; temp = temp.next; } return length; }
5.提供入队方法：offer
队列的典型特征是“先进先出”，因此我们肯定是在一端进行插入一端进行删除。简单分析下数据的插入场景后可以发现，在第一个数据插入时front和rear应该还是相等的，只有一个元素时首结点也是尾结点；数据量大于1时则首结点和尾结点则不会有直接关系，此时的插入只需要在尾结点后继续拼接即可，代码如下：
@Override public void offer(Object object) throws Exception { Node temp = new Node(object,null); if(rear.object==null) rear = front = temp; else{ rear.next = temp;//尾部插入 rear = temp; } }
6.提供出队方法：poll
队列的典型特征是“先进先出”或者叫“后进后出”，插入时选择在尾部插入，那么我们显然就应该在头部进行删除（反过来其实一样：在链表的头部进行插入尾部进行删除）。头部进行删除我们应该考虑两种情况一种是只有一个元素时一种是多个元素时，一个元素时front和rear相等，此时出队后队列就空了。多个元素时只需要将首结点的下一个结点设置为首结点即可。代码实现如下：
@Override public Object poll() { if(front!=null){ Node frontTemp = front; if(front==rear){//只有一个元素时出队 front = rear = new Node(); }else{//其他场景出队 front = front.next; } return frontTemp.object; } return null; }
7.提供获取队列头部元素的方法：peek
该方法只是返回队列的头部元素，并不进行出队。该方法的实现就比较简单了，我们只需要确定首结点不是null即可，非null返回首结点的数据域，否则返回null。代码如下:
@Override public Object peek() { return front!=null?front.object:null; }
8.提供实现的完整代码
到这里链队列的方法就都实现了，各个方法实现起来其实都不难，难的是什么呢？好像没有难的，知道链队列的思想就可以轻松实现了。下面贴下链栈的完整代码：
/** * 链式队列就相当于，既含有首结点，也含有尾结点的单链表 * @author pcc * @version 1.0.0 * @className LinkedQueue * @date 2021-04-29 09:55 */ public class LinkedQueue implements IQueue{ Node front;//首结点 Node rear;//尾结点 public LinkedQueue(){ front = rear = new Node(); } @Override public void clear() { front = rear = new Node(); } @Override public boolean isEmpty() { if(front == rear && front.object == null) return true; return false; } @Override public int length() { int length = 0; Node temp = front; if(front!=rear) while(temp!=null){ length++; temp = temp.next; } return length; } @Override public Object peek() { return front!=null?front.object:null; } @Override public void offer(Object object) throws Exception { Node temp = new Node(object,null); if(rear.object==null) rear = front = temp; else{ rear.next = temp;//尾部插入 rear = temp; } } @Override public Object poll() { if(front!=null){ Node frontTemp = front; if(front==rear){//只有一个元素时出队 front = rear = new Node(); }else{//其他场景出队 front = front.next; } return frontTemp.object; } return null; } }
二、测试顺序队列的相应方法
1.测试入队和出队
链队列的实现已经完成了，下面需要测试下实现的方法是否正确，根据队列的“先进先出”特点，若是入队和出队的顺序保持一致，则说明方法的实现没有问题，测试结果如下，可以发现方法的入队和出队是一致的，也代表队列的入队和出队方法没有问题。
2.测试其他方法
上面的案例中已经测试了入队、出队、长度、非空等方法了，下面再配合清空方法测试下，如下图：
由上图可以看出：插入5个元素后队列长度是5、此时判空是false、然后清空操作再判空是true、然后获取首元素就是null；可以发现这些方法的操作和输出都没有问题。
三、总结
这篇文章总结了链队列的实现，代码是没有难度的，主要是掌握队列的思想。无论是使用单链表还是顺序表来实现队列，都只是队列的内部实现而已，平时的使用更关注的是队列的操作。队列是一种使用很广的数据结构，使用频率也很高，比如jvm中的finalize队列，线程池的等待队列，以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的，这篇文章只是以一个实现者的角度去写的，可能并不是适合很多人，但也希望可以帮到看到这篇文章的你。
