8.5.2 Deque接口与ArrayDeque实现类
Deque接口是Queue接口的子接口，它代表一个双端队列，Deque接口里定义了一些双端队列的方法,这些方法允许从两端来操作队列的元素。
Deque接口方法
插入队列头部
| 方法 |
描述 |
void addFirst(E e) |
将指定元素插入该双端队列的开头。 |
boolean offerFirst(E e) |
将指定元素插入该双端队列的开头。 |
插入队列尾部
| 方法 |
描述 |
void addLast(E e) |
将指定元素插入该双端队列的末尾。 |
boolean offerLast(E e) |
将指定元素插入该双端队列的末尾。 |
查看队头
| 方法 |
描述 |
E getFirst() |
获取但不删除该双端队列的第一个元素。 |
E peekFirst() |
获取但不删除该双端队列的第一个元素；如果此双端队列为空,则返回null |
返回迭代器
| 方法 |
描述 |
Iterator<E> descendingIterator() |
返回该双端队列对应的迭代器,该迭代器将以逆向顺序来迭代队列中的元素。 |
查看队尾
| 方法 |
描述 |
E getLast() |
获取但不删除该双端队列的最后一个元素。 |
E peekLast() |
获取但不删除该双端队列的最后一个元素；如果此双端队列为空,则返回null |
获取并删除队头
| 方法 |
描述 |
E removeFirst() |
获取并删除该双端队列的第一个元素。 |
E pollFirst() |
获取并删除该双端队列的第一个元素；如果此双端队列为空,则返回null |
获取并删除队尾
| 方法 |
描述 |
E removeLast() |
获取并删除该双端队列的最后一个元素。 |
E pollLast() |
获取并删除该双端队列的最后一个元素；如果此双端队列为空,则返回null |
删除第一次出现的元素
| 方法 |
描述 |
boolean removeFirstOccurrence(Object o) |
删除该双端队列中的第一次出现的元素o。 |
boolean removeLastOccurrence(Object o) |
删除该双端队列的最后一次出现的元素o。 |
栈方法
| 方法 |
描述 |
E pop() |
这是个栈方法,pop出该双端队列所表示的栈的栈顶元素。相当于removeFirst() |
void push(E e) |
这是个栈方法,将一个元素push进该双端队列所表示的栈的栈顶。相当于addFirst(Object e)方法. |
Deque的方法与Queue的方法对照
从上面方法中可以看出, Deque不仅可以当成双端队列使用,而且可以被当成栈来使用,因为该类里还包含了pop(出栈)、push(入栈)两个方法。
Deque的方法与Queue的方法对照表如下所示
Queue的方法 |
Deque的方法 |
描述 |
add() |
addLast() |
将指定元素加入此队列的尾部 |
offer() |
offerLast() |
将指定元素加入此队列的尾部。当使用有容量限制的队列时,此方法通常比add(Object e)方法更好。 |
remove() |
removeFirst() |
获取队列头部的元素,并删除该元素。 |
poll() |
pollFirst() |
获取队列头部的元素,并删除该元素。如果此队列为空,则返回null |
element() |
getFirst() |
获取队列头部的元素,但是不删除该元素。 |
peek() |
peekFirst() |
获取队列头部的元素,但是不删除该元素。如果此队列为空,则返回null |
Deque的方法与Stack的方法对照
Deque的方法与Stack的方法对照表如下所示
Stack的方法 |
Deque的方法 |
描述 |
push() |
addFirst()或offerFirst() |
进栈 |
pop() |
removeFirst或pollFirst() |
出站 |
peek() |
getFirst()或peekFirst() |
查看栈顶 |
ArrayDeque实现类
Deque接口提供了一个典型的实现类: ArrayDeque，从该名称就可以看出,ArrayDeque是一个基于数组实现的双端队列，创建Deque时同样可指定一个numElements参数,该参数用于指定Object数组的长度;
| 方法 |
描述 |
ArrayDeque(int numElements) |
Constructs an empty array deque with an initial capacity sufficient to hold the specified number of elements. |
如果不指定numElements参数, 则Deque默认的底层数组的长度为16。
提示
ArrayList和ArrayDeque两个集合类的实现机制基本相似,它们的底层都采用一个动态的、可重分配的Object数组来存储集合元素，当集合元素超出了该数组的容量时,系统会在底层重新分配一个Object数组来存储集合元素。
程序 ArrayDeque当成栈使用
下面程序示范了把ArrayDeque当成”栈”来使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.*;
public class ArrayDequeStack {
public static void main(String[] args) {
ArrayDeque stack = new ArrayDeque();
stack.push("疯狂Java讲义");
stack.push("轻量级Java EE企业应用实战");
stack.push("疯狂Android讲义");
System.out.println(stack);
System.out.println(stack.peek());
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack);
}
}
|
运行结果:
1
2
3
4
5
6
7
| [疯狂Android讲义, 轻量级Java EE企业应用实战, 疯狂Java讲义]
疯狂Android讲义
[疯狂Android讲义, 轻量级Java EE企业应用实战, 疯狂Java讲义]
疯狂Android讲义
[轻量级Java EE企业应用实战, 疯狂Java讲义]
轻量级Java EE企业应用实战
[疯狂Java讲义]
|
需要栈时用ArrayDeque而不是Stack
上面程序的运行结果显示了ArrayDeque作为栈的行为，因此当程序中需要使用”栈”这种数据结构时,推荐使用ArrayDeque,尽量避免使用Stack,因为Stack是古老的集合,性能较差。
程序 ArrayDeque当成队列使用
当然ArrayDeque也可以当成队列使用,此处ArrayDeque将按”先进先出“的方式操作集合元素。
例如如下程序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.*;
public class ArrayDequeQueue {
public static void main(String[] args) {
ArrayDeque queue = new ArrayDeque();
queue.offer("疯狂Java讲义");
queue.offer("轻量级Java EE企业应用实战");
queue.offer("疯狂Android讲义");
System.out.println(queue);
System.out.println(queue.peek());
System.out.println(queue);
System.out.println(queue.poll());
System.out.println(queue);
System.out.println(queue.poll());
System.out.println(queue);
}
}
|
运行结果
1
2
3
4
5
6
7
| [疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
疯狂Java讲义
[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
疯狂Java讲义
[轻量级Java EE企业应用实战, 疯狂Android讲义]
轻量级Java EE企业应用实战
[疯狂Android讲义]
|
上面程序的运行结果显示了ArrayDeque作为队列的行为通过上面两个程序可以看出, ArrayDeque不仅可以作为栈使用,也可以作为队列使用。