0%

8.5.2 Deque接口与ArrayDeque实现类

发表于 更新于 分类于 ， ，

8.5.2 Deque接口与ArrayDeque实现类

Deque接口是Queue接口的子接口,它代表一个双端队列, Deque接口里定义了一些双端队列的方法,这些方法允许从两端来操作队列的元素。

Deque接口方法

方法 描述
void addFirst(Object e) 将指定元素插入该双端队列的开头。
void addLast(Object e) 将指定元素插入该双端队列的末尾。
boolean offerFirst(Object e) 将指定元素插入该双端队列的开头。
boolean offerLast(Object e) 将指定元素插入该双端队列的末尾。
Object getFirst() 获取但不删除双端队列的第一个元素。
Object getLast() 获取但不删除双端队列的最后一个元素。
Iterator descendinglterator() 返回该双端队列对应的迭代器,该迭代器将以逆向顺序来迭代队列中的元素。
Object peekFirst() 获取但不删除该双端队列的第一个元素:如果此双端队列为空,则返回null
Object peekLast() 获取但不删除该双端队列的最后一个元素:如果此双端队列为空,则返回null
Object pollFirst() 获取并删除该双端队列的第一个元素:如果此双端队列为空,则返回null
Object pollLast() 获取并删除该双端队列的最后一个元素;如果此双端队列为空,则返回null
Object removeFirst() 获取并删除该双端队列的第一个元素。
Object removeFirstOccurrence(Object o) 删除该双端队列中的第一次出现的元素o。
Object removeLast() 获取并删除该双端队列的最后一个元素。
boolean removeLastOccurrence(Object o) 删除该双端队列的最后一次出现的元素o。
Object pop() 这是个栈方法,pop出该双端队列所表示的栈的栈顶元素。相当于removeFirst()
void push(Object e) 这是个栈方法,将一个元素push进该双端队列所表示的栈的栈顶。相当于addFirst(Object e)方法.

Deque的方法与Queue的方法对照

从上面方法中可以看出, Deque不仅可以当成双端队列使用,而且可以被当成栈来使用,因为该类里还包含了pop(出栈)、push(入栈)两个方法。
Deque的方法与Queue的方法对照表如表8.2所示。

表8.2 Deque的方法与Queue的方法对照表
Queue的方法 Deque的方法
add() addLast()
offer() offerLast()
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
## Deque的方法与Stack的方法对照 ##
Deque的方法与Stack的方法对照表如表8.3所示。
表8.3 Deque的方法与Stack的方法对照表
Stack的方法 Deque的方法
push() addFirst()或offerFirst()
pop() removeFirst或pollFirst()
peek() getFirst()或peekFirst()
Deque接口提供了一个典型的实现类: ArrayDeque,从该名称就可以看出,它是一个基于数组实现的双端队列,创建Deque时同样可指定一个numElements参数,该参数用于指定Object数组的长度;如果不指定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();
		// 依次将三个元素push入"栈"
		stack.push("疯狂Java讲义");
		stack.push("轻量级Java EE企业应用实战");
		stack.push("疯狂Android讲义");
		// 输出：[疯狂Android讲义, 轻量级Java EE企业应用实战, 疯狂Java讲义]
		System.out.println(stack);
		// 访问第一个元素，但并不将其pop出"栈"，输出：疯狂Android讲义
		System.out.println(stack.peek());
		// 依然输出：[疯狂Android讲义, 疯狂Java讲义, 轻量级Java EE企业应用实战]
		System.out.println(stack);
		// pop出第一个元素，输出：疯狂Android讲义
		System.out.println(stack.pop());
		// 输出：[轻量级Java EE企业应用实战, 疯狂Java讲义]
		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作为栈的行为,因此当程序中需要使用”栈”这种数据结构时,推荐使用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讲义");
		// 输出：[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
		System.out.println(queue);
		// 访问队列头部的元素，但并不将其poll出队列"栈"，输出：疯狂Java讲义
		System.out.println(queue.peek());
		// 依然输出：[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
		System.out.println(queue);
		// poll出第一个元素，输出：疯狂Java讲义
		System.out.println(queue.poll());
		// 输出：[轻量级Java EE企业应用实战, 疯狂Android讲义]
		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不仅可以作为栈使用,也可以作为队列使用。

原文链接: 8.5.2 Deque接口与ArrayDeque实现类