Java版-数据结构-队列（数组队列）

原创
顾立剑
数据结构, 队列
0 ℃

前言

看过笔者前两篇介绍的Java版数据结构数组和栈的盆友，都给予了笔者一致的好评，在这里笔者感谢大家的认可！！！

由于本章介绍的数据结构是队列，在队列的实现上会基于前面写的动态数组来实现，而队列又和栈不论是从特点上和操作上都有类似之处，所以在这里对这两种数据结构不了解的朋友，可以去看一下笔者前两篇文章介绍的数据结构数组和栈，这里笔者把链接贴出来（看过的盆友可以跳过此步骤…）

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的操作方式和栈类似，唯一的区别在于队列只允许新数据在后端（rear）进行添加。

特点

  • 队列是一种线性结构
  • 只能从一端（队尾）添加元素，从另一端（队首）取出元素
  • 先进先出，First In First Out（FIFO）

之前在介绍栈的时候，通过示意图来帮助大家了解什么是栈；这里，我仍采用示意图形式向大家演示队列常用的两个操作：入队操作和出队操作。

队列入队操作

image-20190314004824471

这里我们可以形象地想成我们到银行办理业务排队的场景，现在A、B、C三个元素分别到银行柜台排成一条队办理业务（我们都是文明的孩纸，总不能插队O(∩_∩)O哈！），依次排队的元素是：A、B、C。

队列出队操作

image-20190314004945601

当元素A办理完业务时，当前是元素A先离开队列，然后是元素B，最后是元素C

我们时刻要牢记队列，入队是从队尾一端进行入队，出队是从队首一端进行出队，是一种：先进先出的数据结构。

本文会介绍队列的两张实现方式，一种是数组队列，另外一种是循环队列，考虑篇幅长度原因，本篇我们暂时只介绍数组队列，循环队列放在下一篇介绍。

数组队列（底层基于数组实现）

底层原理分析

现在我们声明一个数组的长度（capacity=3），元素个数为（size=0）的int类型数组的空队列，在这里，假设对队列的队首为数组的左侧，队尾为数组的右侧，示意图如下:

image-20190314023306672

现在如果我们有四个元素：A、B、C、D要入队

元素A入队

image-20190314025039492

元素A已经入队了，现在开始元素B入队

image-20190314025109889

元素A和元素B已经入队了，现在开始元素C入队

image-20190314055125456

元素A、B和C已经分别入队了，现在如果我们要开始元素D入队，根据我们之前定义的动态数组的特性，如果元素D进行入队操作，会发现此时我们的数组已经满了，这时候数组会自动地扩容（扩容的原理：新建一个容量是原数组容量两倍的数组，把原数组中的元素依次拷贝到新的数组中，最后引用指向新的数组）的原来的两倍（具体扩容多少，盆友可以自行设置）示意图如下：

image-20190314055438791

到这里我们已经完成了元素:A、B、C、D的入队操作了，现在我们来看一下，它们的出队操作，根据队列的特性，队列是一种先进先出的数据结构，之前入队操作顺序依次是：A->B->C->D，那么出队操作顺序仍然是：A->B->C->D

现在我们来看一下元素A和元素B出队后的示意图：

image-20190314060105701

元素C和D的出队原理和元素A出队的原理一样，直至全部出队完成，变成空队列

在元素出队的过程中，相应地也会进行缩容操作，之前笔者这边定义，当数组中元素的个数（size）等于数组容量（capacity）的一半时，数组会进行缩容操作，这也正是动态数组的特点。

了解了数组队列的底层原理之后，接下来我们用代码来实现一下（建议盆友，在看之前，自己可以尝试写一下，然后在看，这样印象可能会比较深刻O(∩_∩)O哈！）

队列基本操作
  • 向队列中添加元素（入队）
1
void enqueue(E e);
  • 从队列中取出元素（出队）
1
E dequeue();
  • 获取队首元素
1
E getFront();
  • 获取队列中元素个数
1
int getSize();
  • 判断队列是否为空
1
boolean isEmpty();
代码实现

接口定义 ：Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public interface Queue<E> {
    /**
     * 入队
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出队
     *
     * @return
     */
    E dequeue();

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}

DynamicArrayQueue 类实现接口 Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class DynamicArrayQueue<E> implements Queue<E> {

    /**
     * 用数组存放队列中元素的个数
     */
    private DynamicArray<E> dynamicArray;

    /**
     * 指定容量，初始化队列
     *
     * @param capacity
     */
    public DynamicArrayQueue(int capacity) {
        dynamicArray = new DynamicArray<>(capacity);
    }

    /**
     * 默认容量，初始化队列
     */
    public DynamicArrayQueue() {
        dynamicArray = new DynamicArray<>();
    }


    @Override
    public void enqueue(E e) {
        dynamicArray.addLast(e);
    }

    @Override
    public E dequeue() {
        return dynamicArray.removeFirst();
    }

    @Override
    public E getFront() {
        return dynamicArray.getFirst();
    }

    @Override
    public int getSize() {
        return dynamicArray.getSize();
    }

    @Override
    public boolean isEmpty() {
        return dynamicArray.isEmpty();
    }

    @Override
    public String toString() {
        return "DynamicArrayQueue{" +
                "【队首】dynamicArray=" + dynamicArray + "}【队尾】";
    }
}

测试类： DynamicArrayQueueTest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class DynamicArrayQueueTest {
    @Test
    public void testArrayQueue() {
        // 指定容量（capacity=6）初始化队列
        DynamicArrayQueue<String> dynamicArrayQueue = new DynamicArrayQueue(3);
        System.out.println("初始队列：" + dynamicArrayQueue);

        // 准备入队元素
        List<String> enQueueElements = Arrays.asList("A", "B", "C");

        // 元素入队
        enQueueElements.forEach(x -> dynamicArrayQueue.enqueue(x));
        System.out.println("元素A、B、C入队：" + dynamicArrayQueue);

        // 此时如果又有一个元素D入队，会发生扩容操作 （size == capacity）进行扩容
        dynamicArrayQueue.enqueue("D");
        System.out.println("元素D入队，发生扩容：" + dynamicArrayQueue);


        // 元素A出队，会发生缩容操作（size == capacity / 2）进行缩容
        dynamicArrayQueue.dequeue();
        System.out.println("元素A出队，发生缩容：" + dynamicArrayQueue);

        // 元素B出队
        dynamicArrayQueue.dequeue();
        System.out.println("元素B出队：" + dynamicArrayQueue);

    }
}

运行结果

1
2
3
4
5
6
7
8
9
初始队列：DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[null, null, null], size=0,capacity=3}}【队尾】

元素A、B、C入队：DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[A, B, C], size=3,capacity=3}}【队尾】

元素D入队，发生扩容：DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[A, B, C, D, null, null], size=4,capacity=6}}【队尾】

元素A出队，发生缩容：DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[B, C, D], size=3,capacity=3}}【队尾】

元素B出队：DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[C, D, null], size=2,capacity=3}}【队尾】

细心的盆友，会发现，因为队列的底层是数组来实现的，队列的出队操作实际上就是：删除数组中的第一个元素，后面的所有元素都要往前面挪一位；其实这样性能是比较低下的，时间复杂度是O(n)级别的。

我们想如果元素进行出队操作后，能否不挪动后面的元素，还能维持队列的特性，这样问题不就解决了吗？盆友可以自行思考一下。

完整版代码GitHub仓库地址：Java版数据结构-队列（数组队列） 欢迎大家【关注】和【Star】

本篇完成的数组队列是基于之前【Java版-数据结构-数组】动态数组来实现的，下一篇笔者会给大家介绍用循环队列来解决数组队列带来的性能问题。接下来，笔者还会一一的实现其它常见的数组结构。

  • 静态数组
  • 动态数组
  • 栈
  • 数组队列
  • 循环队列
  • 链表
  • 循环链表
  • 二分搜索树
  • 优先队列
  • 堆
  • 线段树
  • 字典树
  • AVL
  • 红黑树
  • 哈希表
  • ….
数据结构, 队列