[数据结构与算法]数据结构基础：使用数组和链表实现队列、循环队列

其他

如果大家想再次学习一下数据结构，推荐一个数据可视化的数据结构学习网站：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、队列概述

在开始具体的编码之前，我们先聊一下队列。

队列的特点是先进先出FIFO；队列中的数据的处理，就像在车站排队买票一样，先排队的先买到票。

队列常用于计算机操作系统中，它在多用户/多任务环境中尤为重要，因为多个用户或任务可能同时请求同一资源。例如：用户提交到打印机的打印任务由队列控制，保证打印机同一时间只会处理一个打印任务请求。

二、顺序队列和链表队列

我们程序里的数据存储方式有两种，分别是数组（顺序存储） 和链表（链式存储）。队列的实现也可以是数组或链表。

0、队列通用接口

出于通用性的考量，我们抽象一个Queue接口，其中包括入队、出队、获取队列size操作；并对入队数据进行泛型化处理。

package com.saint.base.datastructure.queue;

/**
 * 队列接口
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 20:04
 */
public interface Queue<E> {

    /**
     * 获取队列size
     */
    int getSize();

    /**
     * 入队操作
     */
    void enqueue(E e);

    /**
     * 出队操作
     */
    E dequeue();
}

1、使用数组实现队列

数组结构特点：

• 随机访问时间复杂度O(1) – 快速查询，随机插入时间复杂度O(n/2)
• 数据在内存中连续存储，空间预分配。

大家可以在如下网址进行入队和出队的演示，而我代码的版本在dequeue操作之后会对数据进行移动，使数据对齐到数据开头。网址中的版本减少了dequeue移动数据的操作，但带来了存储空间的浪费。

package com.saint.base.datastructure.queue;

/**
 * 基于数组实现的队列，泛型数据需要可比较
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 14:20
 */
public class ArrayQueue<E extends Comparable<E>> implements Queue<E> {

    /**
     * 存放数据的数组
     */
    Object[] items;

    /**
     * 元素个数
     */
    int size;

    /**
     * 无参构造方法  -- 其中调用有参构造方法
     */
    public ArrayQueue() {
        this(10);
    }

    /**
     * 有参构造方法
     *
     * @param capacity 初始容量
     */
    public ArrayQueue(int capacity) {
        items = new Object[capacity];
        this.size = 0;
    }


    @Override
    public void enqueue(E e) {
        // 判断是否需要扩容
        if (size == items.length) {
            resize(2 * items.length);
        }
        // 往数组尾部中添加数据
        items[size] = e;
        size++;
    }

    /**
     * 数组扩容/缩容操作
     *
     * @param newCapacity 新的数组容量
     */
    public void resize(int newCapacity) {
        Object[] newItems = new Object[newCapacity];
        // 数据迁移
        for (int i = 0; i < size; i++) {
            newItems[i] = items[i];
        }
        items = newItems;
    }

    @Override
    public E dequeue() {
        if (getCapacity() < 1) {
            throw new RuntimeException("Queue is empty");
        }

        E e = (E) items[0];
        // 删除数组头部数据， 时间复杂度O(n)
        for (int i = 0; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        items[size - 1] = null;
        size--;
        // 缩容操作
        if (size == getCapacity() / 4 && getCapacity() > 1) {
            resize(getCapacity() / 2);
        }

        return e;
    }

    /**
     * 获取元素个数
     *
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 获取数组当前容量
     *
     * @return
     */
    public int getCapacity() {
        return items.length;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("ArrayQueue: size =%d, capacity = %d.\n", size, getCapacity()));
        res.append("[");
        for (int i = 0; i < size; i++) {
            res.append(items[i]);
            if (i != size - 1) {
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

2、使用数组实现循环队列

特点：

• 使用数组实现的普通队列，每次出队之后都要调整数组中的数据位置。而循环队列减少了这个O(n)时间复杂的操作。
• 所以循环队列出队的效率比一般的队列要高很多。

package com.saint.base.datastructure.queue;

/**
 * 基于数组实现的循环队列
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 14:19
 */
public class ArrayLoopQueue<E extends Comparable<E>> implements Queue<E> {

    /**
     * 存放队列数据的地方
     */
    Object[] items;

    /**
     * 队列元素个数
     */
    int size;

    /**
     * 队首指针
     */
    int takeIndex;

    /**
     * 队尾指针
     */
    int putIndex;

    public ArrayLoopQueue() {
        this(10);
    }

    public ArrayLoopQueue(int capacity) {
        items = new Object[capacity];
        size = 0;
        putIndex = 0;
        takeIndex = 0;
    }


    @Override
    public void enqueue(E e) {
        // 判断是否需要扩容 ，队尾指针 + 1 和 数组容量取模
        if ((putIndex + 1) % items.length == takeIndex) {
            resize(2 * items.length);
        }
        items[putIndex] = e;
        putIndex++;
        size++;
    }

    @Override
    public E dequeue() {
        if (takeIndex == putIndex) {
            throw new RuntimeException("Queue is empty");
        }

        E e = (E) items[takeIndex];
        items[takeIndex] = null;
        takeIndex = (takeIndex + 1) % items.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 > 0) {
            resize(getCapacity() / 2);
        }
        return e;
    }

    /**
     * 数组扩容/缩容操作
     *
     * @param newCapacity 新的数组容量
     */
    public void resize(int newCapacity) {
        Object[] newItems = new Object[newCapacity];
        // 数据迁移
        for (int i = 0; i < size; i++) {
            // 这里取数据的时候要从takeIndex开始取
            newItems[i] = items[(i + takeIndex) % items.length];
        }
        items = newItems;
        // 数据迁移完，要对takeIndex和putIndex进行重置
        takeIndex = 0;
        putIndex = size;
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 获取数组当前容量
     *
     * @return
     */
    public int getCapacity() {
        return items.length;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("ArrayLoopQueue: size =%d, capacity = %d, takeIndex = %d, putIndex = %d.\n", size,
                getCapacity(), takeIndex, putIndex));
        res.append("head [");
        for (int i = takeIndex; i != putIndex; i = (i + 1) % items.length) {
            res.append(items[i]);
            if ((i + 1) % items.length != putIndex) {
                res.append(" ,");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

3、使用链表实现队列

链表特点：

• 随机访问时间复杂度O(n) – 丧失随机访问的能力、随机插入时间复杂度O(1)。
• 不需要空间预分配，但会额外占用内存空间，用于存储next指针。

Node节点类：

package com.saint.base.datastructure;

/**
 * 链表节点类
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 21:21
 */
public class Node<E> {

    /**
     * 存放数据
     */
    public E value;

    /**
     * 指向下一个node节点
     */
    public Node next;

    /**
     * 构造器
     *
     * @param e
     * @param next
     */
    public Node(E e, Node next) {
        this.value = e;
        this.next = next;
    }

    /**
     * 带一个参数的构造器
     *
     * @param e
     */
    public Node(E e) {
        this(e, null);
    }

    /**
     * 默认构造器
     */
    public Node() {
        this(null, null);
    }

    @Override
    public String toString() {
        return value.toString();
    }
}

package com.saint.base.datastructure.queue;

import com.saint.base.datastructure.Node;

/**
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 14:19
 */
public class LinkedQueue<E extends Comparable<E>> implements Queue<E> {

    /**
     * 链表头部
     */
    Node<E> head;

    /**
     * 链表尾部
     */
    Node<E> tail;

    /**
     * 数据元素个数
     */
    int size;

    public LinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(E e) {
        // 如果链表为空，则创建一个新节点
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            // 新建一个Node节点，并将链表尾节点的next指向新建的Node节点。
            tail.next = new Node(e);
            // tail指针后移
            tail = tail.next;
        }
        size++;

    }

    @Override
    public E dequeue() {
        if (head == null) {
            throw new RuntimeException("Queue is empty!");
        }

        Node<E> cur = head;
        head = head.next;
        cur.next = null;
        if (head == null) {
            tail = null;
        }
        size--;
        return cur.value;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("LinkedQueue: front ");
        Node cur = head;
        while (cur != null) {
            res.append(cur.value + "--> ");
            cur = cur.next;
        }
        res.append(" NULL tail");
        return res.toString();
    }
}

4、测试类

package com.saint.base.datastructure.queue;

/**
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-04 20:27
 */
public class QueueTest {
    public static void main(String[] args) {
        System.out.println("------------------ArrayQueue-----------------------");
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 0) {
                queue.dequeue();
                System.out.println("出队 ： " + queue);
            }
        }
        System.out.println("-----------------------------------------");

        System.out.println("------------------ArrayLoopQueue-----------------------");
        ArrayLoopQueue<Integer> loopQueue = new ArrayLoopQueue<>();
        for (int i = 0; i < 10; i++) {
            loopQueue.enqueue(i);
            System.out.println(loopQueue);
            if (i % 3 == 0) {
                loopQueue.dequeue();
                System.out.println("出队 ： " + loopQueue);
            }
        }
        System.out.println("-----------------------------------------");

        System.out.println("------------------ArrayLoopQueue-----------------------");
        LinkedQueue<Integer> linkedQueue = new LinkedQueue<>();
        for (int i = 0; i < 10; i++) {
            linkedQueue.enqueue(i);
            System.out.println(linkedQueue);
            if (i % 3 == 0) {
                linkedQueue.dequeue();
                System.out.println("出队 ： " + linkedQueue);
            }
        }

    }
}

控制台输出：

------------------ArrayQueue-----------------------
ArrayQueue: size =1, capacity = 10.
[0] tail
出队 ： ArrayQueue: size =0, capacity = 10.
[] tail
ArrayQueue: size =1, capacity = 10.
[1] tail
ArrayQueue: size =2, capacity = 10.
[1,2] tail
ArrayQueue: size =3, capacity = 10.
[1,2,3] tail
出队 ： ArrayQueue: size =2, capacity = 5.
[2,3] tail
ArrayQueue: size =3, capacity = 5.
[2,3,4] tail
ArrayQueue: size =4, capacity = 5.
[2,3,4,5] tail
ArrayQueue: size =5, capacity = 5.
[2,3,4,5,6] tail
出队 ： ArrayQueue: size =4, capacity = 5.
[3,4,5,6] tail
ArrayQueue: size =5, capacity = 5.
[3,4,5,6,7] tail
ArrayQueue: size =6, capacity = 10.
[3,4,5,6,7,8] tail
ArrayQueue: size =7, capacity = 10.
[3,4,5,6,7,8,9] tail
出队 ： ArrayQueue: size =6, capacity = 10.
[4,5,6,7,8,9] tail
-----------------------------------------
------------------ArrayLoopQueue-----------------------
ArrayLoopQueue: size =1, capacity = 10, takeIndex = 0, putIndex = 1.
head [0] tail
出队 ： ArrayLoopQueue: size =0, capacity = 10, takeIndex = 1, putIndex = 1.
head [] tail
ArrayLoopQueue: size =1, capacity = 10, takeIndex = 1, putIndex = 2.
head [1] tail
ArrayLoopQueue: size =2, capacity = 10, takeIndex = 1, putIndex = 3.
head [1 ,2] tail
ArrayLoopQueue: size =3, capacity = 10, takeIndex = 1, putIndex = 4.
head [1 ,2 ,3] tail
出队 ： ArrayLoopQueue: size =2, capacity = 5, takeIndex = 0, putIndex = 2.
head [2 ,3] tail
ArrayLoopQueue: size =3, capacity = 5, takeIndex = 0, putIndex = 3.
head [2 ,3 ,4] tail
ArrayLoopQueue: size =4, capacity = 5, takeIndex = 0, putIndex = 4.
head [2 ,3 ,4 ,5] tail
ArrayLoopQueue: size =5, capacity = 10, takeIndex = 0, putIndex = 5.
head [2 ,3 ,4 ,5 ,6] tail
出队 ： ArrayLoopQueue: size =4, capacity = 10, takeIndex = 1, putIndex = 5.
head [3 ,4 ,5 ,6] tail
ArrayLoopQueue: size =5, capacity = 10, takeIndex = 1, putIndex = 6.
head [3 ,4 ,5 ,6 ,7] tail
ArrayLoopQueue: size =6, capacity = 10, takeIndex = 1, putIndex = 7.
head [3 ,4 ,5 ,6 ,7 ,8] tail
ArrayLoopQueue: size =7, capacity = 10, takeIndex = 1, putIndex = 8.
head [3 ,4 ,5 ,6 ,7 ,8 ,9] tail
出队 ： ArrayLoopQueue: size =6, capacity = 10, takeIndex = 2, putIndex = 8.
head [4 ,5 ,6 ,7 ,8 ,9] tail
-----------------------------------------
------------------ArrayLoopQueue-----------------------
LinkedQueue: front 0-->  NULL tail
出队 ： LinkedQueue: front  NULL tail
LinkedQueue: front 1-->  NULL tail
LinkedQueue: front 1--> 2-->  NULL tail
LinkedQueue: front 1--> 2--> 3-->  NULL tail
出队 ： LinkedQueue: front 2--> 3-->  NULL tail
LinkedQueue: front 2--> 3--> 4-->  NULL tail
LinkedQueue: front 2--> 3--> 4--> 5-->  NULL tail
LinkedQueue: front 2--> 3--> 4--> 5--> 6-->  NULL tail
出队 ： LinkedQueue: front 3--> 4--> 5--> 6-->  NULL tail
LinkedQueue: front 3--> 4--> 5--> 6--> 7-->  NULL tail
LinkedQueue: front 3--> 4--> 5--> 6--> 7--> 8-->  NULL tail
LinkedQueue: front 3--> 4--> 5--> 6--> 7--> 8--> 9-->  NULL tail
出队 ： LinkedQueue: front 4--> 5--> 6--> 7--> 8--> 9-->  NULL tail

三、数组和链表的区别

• 数组最好用于索引有语意的情况。 最大的优点是支持快速查询。
• 链表不适合用于索引有语意的情况。 最大的优点是动态。