数据结构—队列(Queue)的原理以及Java实现案例 1

发表于

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」。

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。本文详细介绍了队列的特性，并且使用Java语言分别实现了基于顺序结构和链式结构的队列。

1 队列的概述

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,……,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。

在这里插入图片描述

因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。

关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

2 队列的顺序存储结构实现

2.1 队列的顺序存储结构概述

和栈不同的是，队列的入队和出队操作在不同端。采用数组来实现时，如果和实现栈的思想一样，如果队头在数组元素最大索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为Ｏ(1)；但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)。如果队头在数组元素的起始索引处，那么出队列到时变快了，但是入队列的时间复杂度却又变成O(n)了。

因此，这里要灵活处理对头或者队尾，不再是固定在数组起始索引或者最大索引处，应该是可变的，此时需要添加外部指针用来保存“队头”和“队尾”。操作数据的时候只需要操作队头和队尾就行了，这样入队和出队的时间复杂度都是O(1)。

按照上面的做法，队头和队尾是不用固定了，入队和出队操作确实很方便。但是可能造成索引溢出以及内存浪费，如下图：

在这里插入图片描述

可能会出现图上的情况，队头被移动到数组的中间，而队尾由于添加元素，移动到数组尾部，此时如果再次入队，由于数组索引溢出将会抛出ArrayIndexOutOfBoundsException，但是数组的前半部分空间却还没有使用，此时又造成了空间浪费。

上面这种溢出，称为“假溢出”。假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列解决了假溢出的问题，同时入队和出队时间都是O(1)。此时需要考虑的就只是数组的容量有限的问题了。

2.2 数组循环队列的简单实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
java复制代码/**
 * 数组实现的循环队列,为了方便,这里底层数组设计为不可扩展
 */
public class MyArrayLoopQueue<E> {

    /**
     * 采用数组实现链式存储
     */
    private final Object[] elements;

    /**
     * 容量
     */
    private final int capacity;

    /**
     * 队头元素索引
     */
    private int first;

    /**
     * 队尾元素索引
     */
    private int end;

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

    /**
     * 构造器初始化数组
     *
     * @param capacity 容量
     */
    public MyArrayLoopQueue(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }


    /**
     * 入队,元素添加在队尾
     *
     * @param element 添加的元素
     * @return 添加成功返回true，添加失败返回false
     */
    public boolean add(E element) {
        //如果队列容量已满.添加失败返回false
        if (size == capacity) {
            return false;
        }
        if (size == 0) {
            /*如果是第一次放元素,则队头和队尾都指向索引0处的元素*/
            elements[end] = element;
        } else if (end + 1 == capacity) {
            /*如果end + 1等于capacity说明队尾空间满了，转向队头,队尾队尾索引置0，循环*/
            end = 0;
            elements[end] = element;
        } else {
            /*否则,队尾索引正常自增*/
            elements[++end] = element;
        }
        //size自增1
        size++;
        return true;
    }

    /**
     * 出队,删除队头元素
     *
     * @return 被移除的元素, 或者null
     */
    public E remove() {
        //队列是否已空
        if (size == 0) {
            // 返回null
            return null;
        }
        Object o = elements[first];
        //移除队头元素
        elements[first] = null;
        //如果队头索引+1之后等于capacity，重置队头索引，循环
        if (++first == capacity) {
            first = 0;
        }
        //如果出队列后队列为空,那么重置队头和队尾索引
        if (--size == 0) {
            first = 0;
            end = 0;
        }
        return (E) o;
    }

    /**
     * 返回队列元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }


    /**
     * 清空队列
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
        first = 0;
        end = 0;
    }


    /**
     * 重写了toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size == 0) {
            stringBuilder.append("[ ]");
            return stringBuilder.toString();
        }
        stringBuilder.append("[ ");
        if (first < end) {
            for (int i = first; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        } else if (size == 1) {
            stringBuilder.append(elements[first]);
        } else {
            for (int i = first; i < capacity; i++) {
                stringBuilder.append(elements[i]);
                stringBuilder.append(", ");
            }
            for (int i = 0; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }


    /**
     * 增强toString方法,用于测试
     *
     * @return
     */
    public String toStringPlus() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size == 0) {
            stringBuilder.append("[ ]");
            stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
            return stringBuilder.toString();
        }
        stringBuilder.append("[ ");
        if (first < end) {
            for (int i = first; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        } else if (size == 1) {
            stringBuilder.append(elements[first]);
        } else {
            for (int i = first; i < capacity; i++) {
                stringBuilder.append(elements[i]);
                stringBuilder.append(", ");
            }
            for (int i = 0; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        }
        stringBuilder.append(" ]");
        stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
        return stringBuilder.toString();
    }
}

2.2.1 测试

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
java复制代码MyArrayLoopQueue<Object> objectMyArrayLoopQueue = new 
MyArrayLoopQueue<>(4);
System.out.println("入队========>");
objectMyArrayLoopQueue.add(11);
objectMyArrayLoopQueue.add(22);
objectMyArrayLoopQueue.add(33);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队========>");
objectMyArrayLoopQueue.add(44);
objectMyArrayLoopQueue.add(55);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队========>");
objectMyArrayLoopQueue.add(null);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队失败========>");
boolean add = objectMyArrayLoopQueue.add(77);
System.out.println(add);
System.out.println(objectMyArrayLoopQueue.toStringPlus());


System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());

3 队列的链式存储结构及实现

3.1 队列的链式存储结构概述

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

可以看出来，使用链式结构实现队列相比顺序结构的实现更加简单。

3.2 队列的链式存储结构简单实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
java复制代码/**
 * 队列的链式储存结构的简单单链表实现
 */
public class MySingleLinkedQueue<E> {

    /**
     * 空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。
     */
    public MySingleLinkedQueue() {
    }

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

    /**
     * 指向队头结点的引用
     */
    private Node<E> first;


    /**
     * 指向队尾结点的引用
     */
    private Node<E> end;

    /**
     * 单链表内部的节点
     */
    private static class Node<E> {
        //下一个结点的引用
        Node<E> next;
        //结点数据
        E data;

        //节点构造器
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    /**
     * 入队，添加元素到单链表尾部
     *
     * @param e 要添加的元素
     */
    public void add(E e) {
        //创建新节点
        Node<E> newNode = new Node<>(e, null);
        if (end != null) {
            /*如果尾结点不为空*/
            end.next = newNode;
            //改变队尾节点引用
            end = newNode;
        } else {
            end = newNode;
            first = newNode;
        }
        ++size;
    }

    /**
     * 出队，删除单链表头部元素
     *
     * @return 被删除的元素
     */
    public E remove() {
        //如果头结点为空,抛出异常
        if (first == null) {
            throw new NoSuchElementException("队列已经为空");
        }
        E e = first.data;
        //改变队头节点引用
        first = first.next;
        //如果元素为0,则将队尾节点引用置空
        if (--size == 0) {
            end = null;
        }
        return e;
    }

    /**
     * 获取元素数量
     */
    public int size() {
        return size;
    }


    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size > 0) {
            Node<E> f = first;
            stringBuilder.append("[ ");
            for (int i = 0; i < size; i++) {
                stringBuilder.append(f.data);
                if (i != size - 1) {
                    stringBuilder.append(" , ");
                }
                f = f.next;
            }
            stringBuilder.append(" ]");
            return stringBuilder.toString();
        }
        return "[]";
    }
}

3.2.1 测试

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
java复制代码MySingleLinkedQueue<Object> objectMySingleLinkedQueue = new 
MySingleLinkedQueue<>();
System.out.println("入队========>");
objectMySingleLinkedQueue.add(11);
objectMySingleLinkedQueue.add(22);
objectMySingleLinkedQueue.add(33);
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("入队========>");
objectMySingleLinkedQueue.add(44);
objectMySingleLinkedQueue.add(55);
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("入队========>");
objectMySingleLinkedQueue.add(null);
System.out.println(objectMySingleLinkedQueue.toString());


System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队异常========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());

4 总结

本文介绍了队列的基本概念，并且提供了简单的实现，队列属于一种特殊的线性表。“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛，实际上我们能够直接接触到的队列的应用是要高于栈的应用的，比如各种并发队列，消息队列。另外在广度优先搜索算法中，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

另外，关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

相关文章：

  1. 《大话数据结构》
  2. 《算法图解》
  3. 《我的第一本算法书》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%