数据结构与算法 | 队列的实现及其应用

Posted on | In |
Words count in article: 1,720 | Reading time ≈ 8


Farming


前面，我们学习了 栈的实现及应用 ，本篇我们来学习一下最后一种线性表——队列。



队列是我们日常开发中经常会用到的一种数据结构，我们经常使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。例如，不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须100%处理成功、不知道谁依赖“我”的处理结果、不关心其他系统如何处理后续业务、不需要强一致性，只需保证最终一致性即可、想要保证数据处理的有序性等等，这些问题都考虑使用队列来解决。

## 队列

### 定义

队列与 栈 一样，都是操作受限的线性表数据结构。队列从一端插入数据，然后从另一端取出数据。插入数据的一端称为”队尾“，取出数据的一端称为”队头“，如图所示：


queue

特点

  • FIFO（First In First Out）：先进先出原则

分类

与 栈 一样，队列也分为顺序队列与链式队列，分别使用数组与链表来实现。

链式队列

链式队列实现比较简单，使用单链表即可实现，如果所示：


LinkedQueue


### 代码实现

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
package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 * 链表队列
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2019/03/27
 */
public class LinkedQueue<T> implements IQueue<T> {

    private int size = 0;
    private Node<T> head;
    private Node<T> tail;

    public LinkedQueue() {
    }

    /**
     * 添加元素到队列头部
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(value, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * 移除队列尾部元素
     *
     * @return
     */
    @Override
    public T poll() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node<T> tmpHead = head;
        head = head.next;
        tmpHead.next = null;
        size--;
        if (head == null) {
            tail = null;
        }
        return tmpHead.element;
    }

    /**
     * 查看队列尾部元素值
     *
     * @return
     */
    @Override
    public T peek() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return head.element;
    }

    /**
     * 清除队列元素
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * 队列大小
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private static class Node<T> {
        private T element;
        private Node<T> next;

        private Node(T element) {
            this.element = element;
        }

        private Node(T element, Node<T> next) {
            this.element = element;
            this.next = next;
        }
    }
}


> 源码

基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。



## 顺序队列

顺序队列采用数组实现，数组的实现有两种方式，一种是顺序式的，一种是循环数组实现。

### 顺序队列

当队列尾部没有剩余空间后，需要集中进行一次数据搬迁腾出空间，才能继续进行入队操作。如图所示：


ArrayQueue


### 循环队列

顺序队列会存在数据搬迁的问题，对入队操作有性能方面的影响。我们可以采用循环数组的方式来解决这一问题，如图所示：


ArrayQueue

当队尾无存储空间且队列未满时，我们可以将其存储到数组的前半部分剩余的空间去。

代码实现

循环队列的实现关键在于队列为空和为满时的状态判断：

  • 当队列为空时：rear == front
  • 当队列为满时：front == (rear + 1) % array.length，队满时，会浪费一个数组的存储空间。

代码如下：

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
package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 * 数组队列
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2019/02/04
 */
public class ArrayQueue<T> implements IQueue<T> {

    /**
     * default array size
     */
    private static final int DEFAULT_SIZE = 1024;
    /**
     * 元素数组
     */
    private T[] array;
    /**
     * 队头指针下标
     */
    private int front = 0;
    /**
     * 队尾指针下标
     */
    private int rear = 0;

    public ArrayQueue() {
        this(DEFAULT_SIZE);
    }

    public ArrayQueue(int capacity) {
        array = (T[]) new Object[capacity];
    }

    /**
     * 添加队尾元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        if (isFull()) {
            grow();
        }
        array[rear % array.length] = value;
        rear++;
        return true;
    }

    /**
     * grow queue size doubly
     */
    private void grow() {
        int growSize = array.length << 1;
        T[] tmpArray = (T[]) new Object[growSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear < front) {
            System.arraycopy(array, 0, tmpArray, array.length - adjRear, adjRear + 1);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = tmpArray;
        rear = (rear - front);
        front = 0;
    }

    /**
     * 移除队头元素
     *
     * @return
     */
    @Override
    public T poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        T element = array[front % array.length];
        array[front % array.length] = null;
        front++;
        if (isEmpty()) {
            // remove last element
            front = rear = 0;
        }

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && size() < shrinkSize) {
            shrink();
        }
        return element;
    }

    /**
     * 压缩
     */
    private void shrink() {
        int shrinkSize = array.length >> 1;
        T[] tmpArray = (T[]) new Object[shrinkSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear <= front) {
            System.arraycopy(array, 0, tmpArray, array.length - front, adjRear);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = null;
        array = tmpArray;
        rear = rear - front;
        front = 0;
    }

    /**
     * 查看队头元素
     *
     * @return
     */
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }
        return array[front % array.length];
    }

    /**
     * 清除队列元素
     */
    @Override
    public void clear() {
        array = null;
        front = rear = 0;
    }

    /**
     * 队列大小
     */
    @Override
    public int size() {
        return rear - front;
    }

    /**
     * 判断队列是否满
     *
     * @return
     */
    private boolean isFull() {
        return !isEmpty() && (front == (rear + 1) % array.length);
    }

    /**
     * 判断队是否为空
     *
     * @return
     */
    private boolean isEmpty() {
        return size() <= 0;
    }

}

源码

基于数组实现的有界队列（bounded queue），队列的大小有限，当请求数量超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

参考资料

请我喝半杯☕️