Java队列实现

全栈程序员站长

发布于 2022-09-14 11:42:50

5700

发布于 2022-09-14 11:42:50

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

一、队列简单介绍

队列是一种常用的数据结构之一，与之前的栈类似，不过队列是“先进先出”。队列有队头（front）和队尾（rear），数据从队尾进入队列，从队头出队列，队头（front）指向队列的第一个数据，队尾（rear）指向队列中的最后一个数据。

二、队列实现

队列有很多种，这里只是介绍最基本的实现，采用链式存储，也就是链式队列，与之前的链表存储形式一样，通过结点对象描述一个数据，结点对象包含具体数据和下一个结点的引用。

1、创建节点类

结点类就跟创建链表的结点类一样。

public class Node<T> {
    // 存储的数据
    private T data;
    // 下一个节点的引用
    private Node<T> next;

    public Node(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

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

}

2、创建队列类LinkQueue

在LinkQueue类中成员变量及方法如下：成员变量：front、rear、size 对应的行为方法有：入队、出队、获取队列元素个数、判断队列是否为空。

public class LinkQueue<T> { 
   

    // 队头
    private Node<T> front;
    // 队尾
    private Node<T> rear;
    // 元素个数
    private int size;

    /** * 创建队列 */
    public LinkQueue() {
        rear = front = null;
    }

    /** * 入队列 * * @param data */
    public void enQueue(T data) {
        Node<T> node = new Node<T>(data);
        if (isEmputy()) {
            front = rear = node;
        } else {
            rear.setNext(node);
            rear = node;
        }

        size++;
    }

    /** * 出队列 * * @return 返回数据 */
    public T deQueue() {
        if (isEmputy()) {
            throw new RuntimeException("队列为空");
        }

        Node<T> delete = front;
        front = delete.getNext();
        delete.setNext(null);; // help GC
        size--;

        if (size == 0) {
            // 删除掉最后一个元素时，front值已经为null，但rear还是指向该节点，需要将rear置为null
            // 最后一个结点front和rear两个引用都没指向它，帮助GC处理该节点对象
            rear = front;
        }

        return (T) delete.getData();
    }

    /** * 判断队列是否为空 * @return */
    public boolean isEmputy() {
        return (front == null && rear == null) ? true : false;
    }

    /** * 获取队列的元素个数 * @return */
    public int size() {
        return this.size;
    }

}

当创建队列时队列中没有数据，front和rear的值都为null。当插入第一个数据时，将front和rear都指向第一个结点对象

后续在插入数据时就利用rear进行数据的插入。

3、测试

测试代码及结果如下：

public static void main(String[] args) {
        LinkQueue<Integer> queue = new LinkQueue<Integer>();

        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);

        System.out.println("size：" + queue.size());

        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());

        System.out.println("删完重新添加==============");
        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        queue.enQueue(44);

        System.out.println("size：" + queue.size());

        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());
        System.out.println("出队列：" + queue.deQueue());
    }

size：4
出队列：1
出队列：2
出队列：3
出队列：4
删完重新添加==============
size：4
出队列：11
出队列：22
出队列：33
出队列：44

好了，java队列的简单实现就介绍到这里。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/159026.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年7月1，如有侵权请联系 cloudcommunity@tencent.com 删除

java

https

网络安全

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度