【JDK】JDK源码-Queue, Deque
概述
Queue 和 Deque 都是接口。其中 Queue 接口定义的是一个队列,它包含队列的基本操作:入队(enqueue)和出队(dequeue)。
Deque 接口继承自 Queue 接口,表示双端队列(Double-ended queue),同时具备「队列」和「栈」的性质。二者的继承关系如下:
PS: 图中还包括阻塞队列 BlockingQueue 和 BlockingDeque,这里暂不分析。
Queue
Queue 接口定义如下:
它定义了 6 个方法,根据操作可以分为三类:入队、出队和遍历。
1. 入队:add() 和 offer()
二者区别在于:当队列空间已满无法入队时,add() 方法会抛出异常;而 offer() 会返回 false。
2. 出队:remove() 和 poll()
二者区别在于:当队列为空时,remove() 方法会抛出异常,而 poll() 会返回 null。
3. 遍历:element() 和 peek()
element() 和 peek() 都表示检索但不移除队列头部元素,可用于从头开始遍历队列。
二者区别在于:当队列为空时,element() 方法会抛出异常,而 peek() 会返回 null。
Queue 接口的几个方法可归纳如下:
Throws exception |
Returns special value |
|
Insert |
add(e) |
offer(e) |
Remove |
remove() |
poll() |
Examine |
element() |
peek() |
Deque
Deque 接口继承自 Queue 接口,可以将 Deque 理解为「双端队列 」和「栈(Stack)」的组合。
PS: 根据前面「数据结构与算法笔记(一)」的概念,该栈是一个「链式栈」。
一般的队列是从尾部插入元素、头部移除元素;而双端队列则可以分别从两端插入元素、两端移除元素。
Deque 接口方法定义如下:
Deque 作为双端队列,其定义的方法可以归纳如下:
First Element (Head) |
Last Element (Tail) |
|||
Throws exception |
Special value |
Throws exception |
Special value |
|
Insert |
addFirst(e) |
offerFirst(e) |
addLast(e) |
offerLast(e) |
Remove |
removeFirst() |
pollFirst() |
removeLast() |
pollLast() |
Examine |
getFirst() |
peekFirst() |
getLast() |
peekLast() |
由于 Deque 继承了 Queue 接口,因此 Queue 的方法在 Deque 中也有体现,而且与 Deque 定义的方法存在如下对应关系:
Queue Method |
Equivalent Deque Method |
add(e) |
addLast(e) |
offer(e) |
offerLast(e) |
remove() |
removeFirst() |
poll() |
pollFirst() |
element() |
getFirst() |
peek() |
peekFirst() |
此外,Deque 还可以作为栈,有关栈的操作和在 Deque 中的对应方法如下:
Stack Method |
Equivalent Deque Method |
push(e) |
addFirst(e) |
pop() |
removeFirst() |
peek() |
peekFirst() |
Deque 还有几个独有的方法:
1. removeFirstOccurrence()
从该双端队列中移除第一次出现的指定元素;
2. removeLastOccurrence()
从该双端队列中移除最后一次出现的指定元素;
3. descendingIterator()
以相反顺序返回此双端队列中元素的迭代器,可以认为是 iterator() 反过来。
小结
1. Queue 和 Deque 都可用于表示队列;
2. Queue 表示基本的队列,包含队列的「入队」和「出队」操作;
3. Deque 继承自 Queue,除了基本的队列操作,Deque 是一个「双端队列」,可以认为它有两个头、两个尾;而且,Deque 还可以作为一个栈。
Stay hungry, stay foolish.
PS: 本文首发于微信公众号。
最新文章
- C# 反射
- Python描述符(descriptor)解密(转)
- 不需要了解任何底层知识,就可以汉化!Let`s go!!!
- Git的常用操作
- eclipse里面设置JVM参数的问题
- Install MongoDB on Red Hat Enterprise, CentOS, Fedora, or Amazon Linux
- Innodb 表修复(转)
- windows下制作u盘启动的工具
- 机房收费系统之uml图——初版
- 使用winform来递归实现资源管理器
- Android 如何修改默认的searchable items。
- 《锋利的Jquery第二版》读书笔记 第二章
- 【转】如何判断CPU是大端还是小端模式
- python2.6.6在centos6.4下安装
- JS中金额转换以及格式化
- OpenCV4.1.0实践(2) - Dlib+OpenCV人脸特征检测
- React-native搭建移动端ios开发环境实践笔记
- [W3bsafe]分享一个爬SQL注入漏洞的工具
- CreateProjectFormat——初始项目目录格式
- Java连接SqlServer2008数据库
热门文章
- Python自学day-3
- mac下mysql的卸载和安装
- PATB 1032 挖掘机技术哪家强(20)
- HDU 1724:Ellipse(自适应辛普森积分)
- POJ 3686:The Windy's(最小费用最大流)***
- redis 文件事件模型
- scrapy实战3利用fiddler对手机app进行抓包爬虫图片下载(重写ImagesPipeline):
- Nginx+Tomat8负载后,利用Redis实现Tomcat8的session共享
- 工作经验之石氏thinking
- Spring Cloud Alibaba | Sentinel: 分布式系统的流量防卫兵初探