Java用链表实现队列

相关文章
Java用数组实现栈
Java用链表实现栈
Java用数组实现队列

队列是具有一定操作约束的线性表，对比堆栈的插入删除只在一端进行，队列是在一端插入（入队），在另一端删除（出队），也就是我们经常说的先进先出。

队列示意图

除了利用数组实现队列外，我们还可以通过一个单链表，来实现队列的链式存储。那么我们的队头变量front和队尾变量rear应该指向链表的哪一头呢。在单链表中链表的头可以方便的进行插入和删除的操作，而链表的尾由于找不到前一个结点的位置，因此只能做插入操作。队列遵循先进先出，也就是队头来进行删除操作，所以我们选择front指向链表的头，rear来指向链表的尾。

具体代码实现如下：

public class Node {
    private Object date; //每个结点的数据
    private Node next; //每个结点指向的下一个结点

    public Node() {
        this.date = null;
        this.next = null;
    }

    public Node(Object date) {
        this.date = date;
        this.next = null;
    }

    public Object getDate() {
        return date;
    }

    public Node getNext() {
        return next;
    }

    public void setDate(Object date) {
        this.date = date;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class MyLinkQueue {
    private Node front; //队头
    private Node rear; //队尾
    private int size; //记录队列数量

    //初始化
    public MyLinkQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    //入队
    public void AddQ(Object data) {
        Node node = new Node(data);//有新元素入栈，创建一个相应的结点对象，申请空间
        if(size == 0) { //如果是添加的第一个队列，将其设置为头结点
            front = node;
        }else { //否则将尾结点的下一个结点更新为新结点
            rear.setNext(node);
        }
        rear = node; //更新rear
        size += 1; //更新size
        System.out.println("入队元素为" + node.getDate());
    }

    public void DeleteQ() {
        if(size == 0) {
            System.out.println("这是一个空队列");
            rear = null; //更新rear
        }else {
            Object data = front.getDate();
            front = front.getNext(); //更新头结点
            System.out.println("出队元素为" + data);
            size -= 1; //更新size
        }
    }
}

public static void main(String[] args) {
        MyLinkQueue myQueue = new MyLinkQueue();
        myQueue.AddQ("第1个");
        myQueue.AddQ("第2个");
        myQueue.AddQ("第3个");
        myQueue.DeleteQ();
        myQueue.DeleteQ();
        myQueue.DeleteQ();
        myQueue.DeleteQ();
        myQueue.DeleteQ();
        myQueue.DeleteQ();
    }
/*
输出结果为：
入队元素为第1个
入队元素为第2个
入队元素为第3个
出队元素为第1个
出队元素为第2个
出队元素为第3个
这是一个空队列
这是一个空队列
这是一个空队列
*/