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
一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。
下表总结了上述 12 种方法：
第一个元素（头部） 最后一个元素（尾部） 抛出异常 特殊值 抛出异常 特殊值 插入 addFirst(e)offerFirst(e)addLast(e)offerLast(e)移除 removeFirst()pollFirst()removeLast()pollLast()检查 getFirst()peekFirst()getLast()peekLast()
此接口扩展了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：
Queue
方法 等效 Deque 方法 add(e)addLast(e)offer(e)offerLast(e)remove()removeFirst()poll()pollFirst()element()getFirst()peek()peekFirst()
双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：
堆栈方法 等效 Deque
方法 push(e)addFirst(e)pop()removeFirst()peek()peekFirst()
注意，在将双端队列用作队列或堆栈时，peek 方法同样正常工作；无论哪种情况下，都从双端队列的开头抽取元素。
此接口提供了两种移除内部元素的方法：removeFirstOccurrence 和 removeLastOccurrence。
与 List 接口不同，此接口不支持通过索引访问元素。
虽然 Deque 实现没有严格要求禁止插入 null 元素，但建议最好这样做。建议任何事实上允许 null 元素的 Deque 实现用户最好不 要利用插入 null 的功能。这是因为各种方法会将 null 用作特殊的返回值来指示双端队列为空。
Deque 实现通常不定义基于元素的 equals 和 hashCode 方法，而是从 Object 类继承基于身份的 equals 和 hashCode 方法。
从以下版本开始：
-
1.6
方法摘要 booleanadd(E e)
将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。 voidaddFirst(E e)
将指定元素插入此双端队列的开头（如果可以直接这样做而不违反容量限制）。 voidaddLast(E e)
将指定元素插入此双端队列的末尾（如果可以直接这样做而不违反容量限制）。 booleancontains(Object o)
如果此双端队列包含指定元素，则返回 true。 Iterator<E>descendingIterator()
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 Eelement()
获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。 EgetFirst()
获取，但不移除此双端队列的第一个元素。 EgetLast()
获取，但不移除此双端队列的最后一个元素。 Iterator<E>iterator()
返回以恰当顺序在此双端队列的元素上进行迭代的迭代器。 booleanoffer(E e)
将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用的空间，则返回 false。 booleanofferFirst(E e)
在不违反容量限制的情况下，将指定的元素插入此双端队列的开头。 booleanofferLast(E e)
在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾。 Epeek()
获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。 EpeekFirst()
获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。 EpeekLast()
获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。 Epoll()
获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。 EpollFirst()
获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。 EpollLast()
获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。 Epop()
从此双端队列所表示的堆栈中弹出一个元素。 voidpush(E e)
将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。 Eremove()
获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。 booleanremove(Object o)
从此双端队列中移除第一次出现的指定元素。 EremoveFirst()
获取并移除此双端队列第一个元素。 booleanremoveFirstOccurrence(Object o)
从此双端队列移除第一次出现的指定元素。 EremoveLast()
获取并移除此双端队列的最后一个元素。 booleanremoveLastOccurrence(Object o)
从此双端队列移除最后一次出现的指定元素。 intsize() 返回此双端队列的元素数。
队列(queue)是一种常用的数据结构，可以将队列看做是一种特殊的线性表，该结构遵循的先进先出原则。Java中，LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高
相关常用方法：
boolean offer(E e):将元素追加到队列末尾,若添加成功则返回true。
E poll():从队首删除并返回该元素。
E peek():返回队首元素，但是不删除
示例代码：
复制代码public class QueueDemo {
public static void main(String [] args) {
Queue<String> queue = new LinkedList<String>();
//追加元素
queue.offer("one");
queue.offer("two");
queue.offer("three");
queue.offer("four");
System.out.println(queue);
//从队首取出元素并删除
String poll = queue.poll();
System.out.println(poll);
System.out.println(queue);
//从队首取出元素但是不删除
String peek = queue.peek();
System.out.println(peek);
System.out.println(queue);
//遍历队列，这里要注意，每次取完元素后都会删除，整个
//队列会变短，所以只需要判断队列的大小即可
while(queue.size() > 0) {
System.out.println(queue.poll());
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
运行结果：
[one, two, three, four]
one
[two, three, four]
two
[two, three, four]
two
three
four
双向队列(Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则
Deque在Queue的基础上增加了更多的操作方法
从上图可以看到，Deque不仅具有FIFO的Queue实现，也有FILO的实现，也就是不仅可以实现队列，也可以实现一个堆栈。
同时在Deque的体系结构图中可以看到，实现一个Deque可以使用数组（ArrayDeque），同时也可以使用链表（LinkedList），还可以同实现一个支持阻塞的线程安全版本队列LinkedBlockingDeque。
对于数组实现的Deque来说，数据结构上比较简单，只需要一个存储数据的数组以及头尾两个索引即可。由于数组是固定长度的，所以很容易就得到数组的头和尾，那么对于数组的操作只需要移动头和尾的索引即可。
特别说明的是ArrayDeque并不是一个固定大小的队列，每次队列满了以后就将队列容量扩大一倍（doubleCapacity()），因此加入一个元素总是能成功，而且也不会抛出一个异常。也就是说ArrayDeque是一个没有容量限制的队列。
同样继续性能的考虑，使用System.arraycopy复制一个数组比循环设置要高效得多。
常用方法如下：
void push(E e):将给定元素”压入”栈中。存入的元素会在栈首。即:栈的第一个元素
E pop():将栈首元素删除并返回。
示例代码：
复制代码public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);
//获取栈首元素后，元素不会出栈
String str = deque.peek();
System.out.println(str);
System.out.println(deque);
while(deque.size() > 0) {
//获取栈首元素后，元素将会出栈
System.out.println(deque.pop());
}
System.out.println(deque);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
运行结果：
[c, b, a]
c
[c, b, a]
c
b
a
[]
1Deque接口继承了Queue接口,而Queue接口继承了Collection接口,
LinkedList实现了Deque接口;
(顶级接口)Collection-->Queue-->Deque-->LinkedList(实现类)
最后
以上就是老迟到长颈鹿最近收集整理的关于deque的全部内容，更多相关deque内容请搜索靠谱客的其他文章。
发表评论 取消回复