笔记 Java 备忘单

Java 对应数据结构可用的类型

栗子℃

Sep 12, 2021 • 4 min read

队列

ref: https://docs.oracle.com/javase/11/docs/api/java/util/Queue.html

Queue接口

Queue：基本上都是先进先出（反例：Priority Queue, LIFO Queue/Stack）

All Superinterfaces: Collection<E>, Iterable<E>

All Known Subinterfaces: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

方法

有exception的：

add: 入队一个元素并返回true。如果无法入队（比如队列容量固定，并超出容量了），IllegalStateException。这个方法是从Collection<E>接口来的。
remove: 队列开头的元素出队（并返回该元素）。如果队列为空，NoSuchElementException 。
element: 返回开头元素但不出队。如果队列为空，NoSuchElementException 。

没exception的：

offer: 入队一个元素并返回true。如果无法入队，返回false。
poll: 队列开头元素出队（并返回该元素）。如果队列为空，返回null。
peek: 返回开头元素但不出队。如果队列为空，返回null。

其他接口

BlockingQueue：线程安全的Queue（但Collection的批处理操作不是现成安全的addAll, containsAll, retainAll ,removeAll）。offer和poll可以指定timeout，在无法入队、无法出队（队为空）的情况下等待一段时间，直到可以出入队。不允许放null。
Deque (Double-ended Queue): 头和尾都能出入队的队列。各种方法都有First和Last (e.g. pollFirst, pollLast)
BlockingDeque
TransferQueue: 一种BlockingQueue。这种队列里，producer可以等consumer接收元素。可以有一堆consumer等着拿东西。。。

现成的可用的类

LinkedList

是List，也是Deque，基于双向链表实现。

add, remove: O(1)

get: O(n)

ArrayDeque

是List，也是Deque，基于循环数组实现。不允许存放null。

据API说，作为队列时很可能比LinkedList快，作为栈时很可能比Stack快。

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

add, remove: O(n)

get: O(1)

PriorityQueue

基于最小堆（完全二叉树）的队列，自带排序的队列，也因为自带排序，并不是先进先出，而是小的先出。默认小的元素放前面，也可以在构造的时候指定一个Comparator。如果想换成最大堆，new PriorityQueue((x,y)->(y-x))就行了。

poll, remove, peek, element都是访问队头。

get, add, offer, remove, poll: O(log(N))

栈

栈可以使用push和pop方法。

推荐使用Deque接口，ArrayDeque或者LinkedList都可以。

不推荐使用Stack类（不过它是synchronized的）：

Stack继承Vector，而Vector有效率问题
与Deque相比，只能从一个方向进出

Stack的方法有push, pop, peek。以及，虽然它叫stack，但由于它是用List做的，其实还是有一些会破坏stack意义的方法的，可以按index进行get, insert, remove…

注意：如果使用了Stack的Iterator，返回的顺序是由堆底至堆顶。而用Deque的Iterator时（使用push入栈时），返回顺序是堆顶至堆底。

堆

使用PriorityQueue, 见上文。

哈希

Set

Set是Iterable，也是Collection，所以可以forEach也可以toArray

HashSet

方法：add, remove, size, isEmpty, clear

注意clone方法是shallow copy，复制出的Set里面的元素还是那些地址。

Map

Map不是Iterable的（SortedMap是Iterable的）
Hashtable是线程安全的，但不接受null (没写错，table就是小写的…）。每次同步执行时都锁定整个结构。ConcurrentHashMap同步时锁的颗粒度更小，所以更推荐使用。
HashMap是非线程安全的，但可以接受null。Collections.synchronizedMap(HashMap)时几乎等同于Hashtable，靠锁住整个Map来进行同步。

方法： get, put, remove, size, isEmpty, containsKey, containsValue

keySet返回所有key, putAll可以用于复制另一个Map全部键值（注：如有重复的键，值会覆盖）

Ref:

队列