一、实现过程

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队列，线程池的等待队列，以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的，这篇文章只是以一个实现者的角度去写的，可能并不是适合很多人，但也希望可以帮到看到这篇文章的你。

最后

以上就是搞怪八宝粥最近收集整理的关于java语言实现链队列一、实现过程二、测试顺序队列的相应方法三、总结的全部内容，更多相关java语言实现链队列一、实现过程二、测试顺序队列内容请搜索靠谱客的其他文章。