Java集合(二) Queue和Deque

队列和双端队列

第一节 简介

队列(queue):就是一个先进先出的集合,不支持从中间插入元素。

双端队列(Deque):就是有两个端头的队列,可以有效的从头部尾部增删元素,由 ArrayDequeLinkedList 实现。


第二节 Queue

Queue 接口如下,声明了一个队列所需的几个基本方法。

1
2
3
4
5
6
7
8
9
10
public interface Queue<E> extends Collection<E> {
boolean add(E e);//若队列不满,将给定的元素添加到队列的尾部,若队列已满,就抛出异常IllegalStateException
boolean offer(E e);//若队列不满,将给定的元素添加到队列的尾部,若队列已满,就返回false

E remove();//若队列不空,删除并返回队列头部的元素,若队列为空,就抛出异常NoSuchElementException
E poll();//若队列不空,删除并返回队列头部的元素,若队列为空,就返回false

E element();//若队列不空,返回队列头部的元素,若队列为空,就抛出异常NoSuchElementException
E peek();//若队列不空,返回队列头部的元素,若队列为空,就返回false
}

队列的实现有两种方式:

  1. 循环数组
  2. 链表

java.util 包中的抽象类 AbstractQueue ,实现了Queue,提供了接口方法的部分默认实现。

1
2
3
4
public abstract class AbstractQueue<E> extends AbstractCollection<E>
implements Queue<E> {
//省略
}

第三节 Deque

双向队列 Deque 接口如下:

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
public interface Deque<E> extends Queue<E> {
void addFirst(E e);//将给定的元素添加到队列头部或尾部,若队列已满,就抛出异常IllegalStateException
void addLast(E e);

boolean offerFirst(E e);//将给定的元素添加到队列头部或尾部,若队列已满,就返回false
boolean offerLast(E e);

E removeFirst();//若队列不空,删除并返回队列头部或尾部的元素,若队列为空,就抛出异常NoSuchElementException
E removeLast();

E pollFirst();//若队列不空,删除并返回队列头部或尾部的元素,若队列为空,就返回false
E pollLast();

E getFirst();//若队列不空,返回队列头部或尾部的元素,若队列为空,就抛出异常NoSuchElementException
E getLast();

E peekFirst();//若队列不空,返回队列头部或尾部的元素,若队列为空,就返回false
E peekLast();

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
boolean addAll(Collection<? extends E> c);

// *** Stack methods ***
void push(E e);
E pop();

// *** Collection methods ***
boolean remove(Object o);
boolean contains(Object o);
int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();

}

Deque 包含了 Queue 的方法,并定义了头尾相关方法、栈方法、集合方法等。


第四节 ArrayDeque

ArrayDeque 实现了双向队列 Deque ,底层通过数组实现。

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
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable{
transient Object[] elements;//Object数组存放元素
transient int head;//头部
transient int tail;//尾部
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大size

public ArrayDeque() {//默认初始容量16
elements = new Object[16];
}

public ArrayDeque(int numElements) {//给定初始容量
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}

public ArrayDeque(Collection<? extends E> c) {//创建并添加集合的所有元素
this(c.size());
addAll(c);
}

private void grow(int needed) {//自增长
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}

// 向队首添加元素
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}

// 向队尾添加元素
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
// 更新首尾游标,并当游标重合时扩容
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}

// 添加元素,等价于队尾添加
public boolean add(E e) {
addLast(e);
return true;
}
...

}

第五节 优先级队列

优先级队列可以按任意的顺序插入元素,但总是按照排序的顺序进行检索。即无论何时调用 remove() ,总会获取优先级队列的最小元素,但优先级队列并没有对所有的元素进行排序算法,而是通过堆(heap)的数据结构来存储元素,堆就是一个能自我调整的二叉树

任务调度是使用优先级队列的典型场景:每个任务各有一个优先级,任务以随机的顺序添加到队列内,每当启动一个新任务时就把优先级最高的任务从队列中移除(一般会把1设置为最高优先级,也就是最小元素)。

5.1 PriorityQueue

TreeSet 一样,PriorityQueue 既可以保存对象实现的 Comparable ,也可以保存在构造器内给定的 Comparator 对象。

迭代时,PriorityQueue 并不是像 TreeSet 那样按元素的排列顺序访问,删除时总是删掉优先级数最小的元素。

PriorityQueue 底层是一个数组,通过数组来实现二叉树,固定下标位置对应二叉树结点,所以知道元素位置即可得到其父结点。

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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {

transient Object[] queue; //元素数组
int size;//元素数目
private final Comparator<? super E> comparator;//比较器
transient int modCount; //优先级队列结构被修改的次数

public PriorityQueue() {//构造一个优先级队列
this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) {//构造一个初始容量的优先级队列
this(initialCapacity, null);
}

public PriorityQueue(Comparator<? super E> comparator) {//构造一个带比较器的优先级队列
this(DEFAULT_INITIAL_CAPACITY, comparator);
}

...

@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {//构造一个优先级队列,并放入集合的所有元素,当集合是有序集或优先级队列时继承比较器
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}

...


private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}

public boolean add(E e) {
return offer(e);
}

public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
// 操作计数++
modCount++;
int i = size;
// 是否需要扩容
if (i >= queue.length)
grow(i + 1);
// 更新数目
size = i + 1;
// 第一次新增,放置首位,否则放置队尾,此处提前判断好像只是减少了一次函数调用
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}

// 二叉树插入结点,并向上排序
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
// 循环直到此时父结点大于当前元素
while (k > 0) {
// 通过固定下标来对应二叉树对应结点
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
// 放置元素
queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}

@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}

private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}

public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}

boolean removeEq(Object o) {
for (int i = 0; i < size; i++) {
if (o == queue[i]) {
removeAt(i);
return true;
}
}
return false;
}

private E removeAt(int i) {
// assert i >= 0 && i < size;
// 操作计数++
modCount++;
// 更新数目
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else { // 非队尾元素
// 先获取队尾元素
E moved = (E) queue[s];
// 将队尾置空
queue[s] = null;
// 通过下移结点,将队尾元素重新放入二叉树(排序)
siftDown(i, moved);
// 若刚好能放到i下标,则通过上移元素
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}

// 二叉树插入结点,并向下排序
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
// 循环下移二叉树结点,直到找到合适位置放置当前元素
while (k < half) {
// 获取左子结点
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
// 如果右子结点存在,且左子结点大于右子结点,则获取右子结点
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
// 如果当前子结点大于x元素,表示k是合适的位置,则结束循环
if (key.compareTo((E) c) <= 0)
break;
// 否则将子结点从二叉树上移
queue[k] = c;
k = child;
}
queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
}

通过一个简单的案例观察PriorityQueue的遍历顺序和删除顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
PriorityQueue<Person> people = new PriorityQueue<>();
people.add(new Person("Mary",17));
people.add(new Person("Lee",20));
people.add(new Person("Ada",17));
System.out.println("Iterating over elements ");
for(Person person : people)
System.out.println(person.toString());
System.out.println("Removing elements ");
while (!people.isEmpty())
System.out.println("remove:" + people.remove().toString());

}

执行结果如下:

1
2
3
4
5
6
7
8
Iterating over elements 
name: Ada
name: Lee
name: Mary
Removing elements
remove:name: Ada
remove:name: Mary
remove:name: Lee

第六节 链表实现队列

自己通过链表实现一下先进先出队列,并测试执行。

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
public class MyQueue<Item> implements Iterable<Item> {
private Node first;//指向最早添加的结点的游标
private Node last;//指向最近添加的结点的游标
private int N;//队列中元素的数量
private class Node{//定义结点的嵌套类
Item item;
Node next;
}

public boolean isEmpty(){
return N == 0;
}

public int size(){
return N;
}

public void enqueue(Item item){//向表尾添加元素
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty()) first = last;
else oldlast.next = last;
N++;
}

public Item dequeue(){//从表头删除元素
Item item = first.item;
first = first.next;
if(isEmpty())
last = null;
N--;
return item;
}

//iterator

@Override
public Iterator<Item> iterator() {
return new ListIterator();
}

private class ListIterator implements Iterator<Item>{
private Node current = first;

@Override
public boolean hasNext() {
return current != null;
}

@Override
public void remove() {
}

@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}

//测试用例: to be or not to - be - - that - - - is *
//结果: to be or not to be (2 left on queue)
public static void main(String[] args){
//创建一个队列并操作字符串入列或出列
MyQueue<String> queue = new MyQueue<String>();
Scanner input = new Scanner(System.in);
while (input.hasNext()){
String item = input.next();
if(!item.equals("-") && !item.equals("*"))
queue.enqueue(item);
else if(item.equals("-"))
System.out.print(queue.dequeue() + " ");
else if(item.equals("*")){
System.out.println("(" + queue.size() + " left on queue)");
break;
}
}
}
}

输出结果如下。

1
2
to be or not to - be - - that - - - is *
to be or not to be (2 left on queue)

第七节 BlockingQueue

阻塞队列-BlockingQueue,相关内容参考:《BlockingQueue》。

第八节 ConcurrentLinkedQueue

线程安全队列-ConcurrentLinkedQueue,相关内容参考:《ConcurrentLinkedQueue的实现原理》。


参考博客和文章书籍等:

《Java核心技术 卷Ⅰ》

因博客主等未标明不可引用,若部分内容涉及侵权请及时告知,我会尽快修改和删除相关内容