专栏首页Java后端技术栈cwnait队列 | 如何使用数组和链表来实现“队列”

队列 | 如何使用数组和链表来实现“队列”

如何使用数组和链表来实现“队列”

与栈一样,队列(Queue)也是一种数据结构,它包含一系列元素。但是,队列访问元素的顺序不是后进先出(LIFO),而是先进先出(FIFO)。

实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。与实现栈的方法类似,队列的实现也有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

数组实现

分析

下图给出了一种最简单的实现方式,用front来记录队列首元素的位置,用rear来记录队列尾元素往后一个位置。

入队列的时候只需要将待入队列的元素放到数组下标为rear的位置,同时执行rear++,出队列的时候只需要执行front++即可。

代码实现

/**
 * 数组实现队列
 *
 * @author tian
 * @date 2020/4/26
 */
public class MyArrayQueueDemo {
    public static void main(String[] args) {
        MyQueueDemo<Integer> myQueueDemo = new MyQueueDemo<>();

        myQueueDemo.enQueue(1);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(2);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(3);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.enQueue(4);
        System.out.println("-----向队列中添加元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());

        System.out.println("---------------------------");
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
        myQueueDemo.deQueue();
        System.out.println("-----从队列中取出元素-----");
        System.out.println("队列头元素 = " + myQueueDemo.getFront());
        System.out.println("队列尾元素 = " + myQueueDemo.getBack());
        System.out.println("队列大小 = " + myQueueDemo.size());
    }
}

class MyQueueDemo<T> {
    private List<T> arrayList = new ArrayList<>();

    private int front;
    private int rear;

    public MyQueueDemo() {
        this.front = 0;
        this.rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public int size() {
        return rear - front;
    }

    //获取对手元素
    public T getFront() {
        if (isEmpty()) {
            return null;
        }
        return arrayList.get(front);
    }

    //获取队列尾部元素
    public T getBack() {
        if (isEmpty()) {
            return null;
        }
        return arrayList.get(rear - 1);
    }

    //删除队列中头部元素
    public void deQueue() {
        if (rear > front) {
            front++;
        } else {
            System.out.println("队列已经不存在元素了");
        }
    }

    //把新元素添加到队列中(队列尾部)
    public void enQueue(T item) {
        arrayList.add(item);
        rear++;
    }
}

运行结果

OK,自此,使用数组实现队列已经搞定。

问题

出队列后数组前半部分的空间不能够充分地利用,解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后,可以从数组首位置开始循环利用。

链表实现

分析

采用链表实现队列的方法与实现栈的方法类似,分别用两个指针指向队列的首元素与尾元素,如下图所示。用pHead来指向队列的首元素,用pEnd来指向队列的尾元素。

在上图中,刚开始队列中只有元素1、2和3,当新元素4要进队列的时候,只需要上图中(1)和(2)两步,就可以把新结点连接到链表的尾部,同时修改pEnd指针指向新增加的结点。出队列的时候只需要(3)这一步,改变pHead指针使其指向pHead→next,此外也需要考虑结点所占空间释放的问题。

代码实现

/**
 * @author tian
 * @date 2020/4/26
 */
class QueueNode<T> {
    T data;
    QueueNode<T> next;

}

class MyNodeQueue<T> {
    private QueueNode<T> head;
    private QueueNode<T> end;
   //初始化队列
    public MyNodeQueue() {
        end = head = null;
    }

    boolean isEmpty() {
        return head == null;
    }

    int size() {
        int size = 0;
        QueueNode<T> temp = head;
        while (temp != null) {
            temp = temp.next;
            size++;
        }
        return size;
    }
   //入队
    void enQueue(T t) {
        QueueNode<T> temp = new QueueNode<>();
        temp.data = t;
        temp.next = null;
        if (head == null) {
            head = end = temp;
        } else {
            end.next = temp;
            end = temp;
        }
    }
  //出队
    void deQueue() {
        if (head == null) {
            System.out.println("不存在元素,出队失败");
            return;
        }
        head = head.next;
        if (head == null) {
            end = null;
        }
    }
  //获取队首元素
   T getFront() {
        if (head == null) {
            System.out.println("队列中不存在元素,获取为空");
            return null;
        }
        return head.data;
    }
   //获取队尾元素    T getBack() {        if (end == null) {
            System.out.println("队列中不存在元素,获取失败");
            return null;
        }
        return end.data;
    }
}

public class MyNodeQueueDemo {
    public static void main(String[] args) {
        MyNodeQueue<Integer> queue = new MyNodeQueue<>();
        queue.enQueue(1);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(2);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(3);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.enQueue(4);
        System.out.println("向队列中添加元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());

        System.out.println("------------------");

        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
        queue.deQueue();
        System.out.println("从队列中取出元素");
        System.out.println("头 元素=" + queue.getFront());
        System.out.println("尾 元素=" + queue.getBack());
        System.out.println("大小=" + queue.size());
    }
}

运行结果

OK,使用链表实现队列到此就搞定。

总结

显然用链表来实现队列有更好的灵活性,与数组的实现方法相比,它多了用来存储结点关系的指针空间。此外,也可以用循环链表来实现队列,这样只需要一个指向链表最后一个元素的指针即可,因为通过指向链表尾元素可以非常容易地找到链表的首结点。

本文分享自微信公众号 - Java后端技术栈(t-j20120622),作者:田老师

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 栈 | 如何使用数组和链表实现“栈”

    实现一个栈的数据结构,使其具有以下方法:压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。下面是一个栈的入栈和出栈整个过程

    田维常
  • 快速掌握并发编程---ArrayBlockingQueue 底层原理和实战

    在JDK1.5的时候,在新增的Concurrent包中,BlockingQueue很好的解决了多线程中,如何高效安全“传输”数据的问题。通过这些高效并且线程安全...

    田维常
  • 【原创】Spring Boot 如何手写stater

    很多人可能会觉得这种starter方式很牛B,添加一个starter就搞定了很多事情。今天咱们也来搞一个自己的starter。

    田维常
  • java之集合那些事

    1、Hash Set和 TreeSet是Set的两个典型实现,到底如何选择 Hash Set和 Tree Set呢? HashSet的性能总是比 TreeSet...

    说故事的五公子
  • 测试性能(Java 8 的循环和Java 7 的循环耗时的对比测试)

    说高级的stream就是那个并行流。下面是那个并行流的简单实现。只要是继承Collection类的都可以这么用。

    一觉睡到小时候
  • 算法03 七大排序之:直接插入排序和希尔排序

    上一篇总结了直接选择排序和堆排序,这一篇要总结的是插入排序中的直接插入排序和希尔排序,我们主要从以下几点进行总结。 1、直接插入排序及算法实现 2、希尔排序及算...

    nnngu
  • Selenium Webdriver 3.X源码分析之ActionChains

    > Selenium Webdriver 3.X源码分析系列第5篇,该系列原则上会将整个源码分享一遍

    苦叶子
  • getBoundingClientRect方法获取元素在页面中的相对位置

    获取元素位置可以用 offset 或 getBoundingClientRect,使用 offset 因为兼容性不好,比较麻烦,offset获取位置会形成“回溯...

    用户6167509
  • java之==操作符和equals操作符

    说明:a1和b1指向的是同一个String,而a2和b2指向不同的String,所以a2.equals(b2)只比较值返回true,==比较引用返回false。

    绝命生
  • 遍历目录清理COS中大小为0的文件 for JAVA

    在上传到COS文件中,会存在一些0字节的文件,对于部分业务来说是无效的。需要做清理,否则看着碍眼也没用。

    腾讯云技术服务团队

扫码关注云+社区

领取腾讯云代金券