本文共 4170 字,大约阅读时间需要 13 分钟。
队列, 一种常用的数据结构,可以将队列看做是一种特殊的线性表,该结构遵循的先进先出原则。Java中,LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高
相关方法:
boolean offer(E e):将元素追加到队列末尾,若添加成功则返回true。 E poll():从队首删除并返回该元素。 E peek():返回队首元素,但是不删除public interface Queueextends Collection {...}
操作 | 抛出异常 | 返回特殊值 |
---|---|---|
插入 | add() | offer() |
删除 | remove() | poll() |
查询 | element() | peek() |
双向队列,指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队,则可实现栈的数据结构。对于栈而言,有入栈(push)和出栈(pop),遵循先进后出原则
常用方法如下:
void push(E e):将给定元素”压入”栈中。存入的元素会在栈首。即:栈的第一个元素 E pop():将栈首元素删除并返回。public interface Dequeextends Queue {...}
Stack是继承于Vector(矢量队列)的,由于Vector是通过数组实现的,这就意味着,Stack也是通过数组实现的,而非链表。当然,我们也可以将LinkedList当作栈来使用
public class Stackextends Vector {...}
方法名 | 返回类型 | 说明 |
---|---|---|
empty | boolean | 判断stack是否为空。 |
peek | E | 返回栈顶端的元素。 |
pop | E | 弹出栈顶的元素 |
push | E | 将元素压入栈 |
search | int | 返回最靠近顶端的目标元素到顶端的距离。 |
操作 | 数组 | 链表 |
---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
随机访问性强
查找速度快插入和删除效率低
可能浪费内存 内存空间要求高,必须有足够的连续内存空间。 数组大小固定,不能动态拓展插入删除速度快
内存利用率高,不会浪费内存 大小没有固定,拓展很灵活。不能随机查找,必须从第一个开始遍历,查找效率低
为了具有调用行为,存放到DelayDeque的元素必须继承Delayed接口。Delayed接口使对象成为延迟对象,它使存放在DelayQueue类中的对象具有了激活日期。该接口强制执行下列两个方法。
CompareTo(Delayed o):Delayed接口继承了Comparable接口,因此有了这个方法。
getDelay(TimeUnit unit):这个方法返回到激活日期的剩余时间,时间单位由单位参数指定。DelayQueue的使用步骤:
1)创建实现Delayed接口的类,然后在创建对象的时候,指定延迟到什么时间。
2)实现getDelay方法,该方法返回当前元素还需要延时多长时间,单位是纳秒。
实现compareTo方法来指定元素的顺序。例如,让延时时间最长的放在队列的末尾。
参考:
实现BlockingQueue接口的有ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue,
而这几种常见的阻塞队列也是在实际编程中会常用的,下面对这几种常见的阻塞队列进行说明:ArrayBlockingQueue
是由数组
实现的有界阻塞队列
。该队列命令元素FIFO(先进先出)。因此,对头元素时队列中存在时间最长的数据元素,而对尾数据则是当前队列最新的数据元素。ArrayBlockingQueue可作为“有界数据缓冲区”,生产者插入数据到队列容器中,并由消费者提取。ArrayBlockingQueue一旦创建,容量不能改变。
当队列容量满时,尝试将元素放入队列将导致操作阻塞;尝试从一个空队列中取一个元素也会同样阻塞。
ArrayBlockingQueue默认情况下不能保证线程访问队列的公平性,所谓公平性是指严格按照线程等待的绝对时间顺序,即最先等待的线程能够最先访问到ArrayBlockingQueue。而非公平性则是指访问ArrayBlockingQueue的顺序不是遵守严格的时间顺序,有可能存在,一旦ArrayBlockingQueue可以被访问时,长时间阻塞的线程依然无法访问到ArrayBlockingQueue。如果保证公平性,通常会降低吞吐量。如果需要获得公平性的ArrayBlockingQueue,可采用如下代码:
private static ArrayBlockingQueueblockingQueue = new ArrayBlockingQueue (10,true);
LinkedBlockingQueue
是用链表
实现的有界阻塞队列
,同样满足FIFO的特性,与ArrayBlockingQueue相比起来具有更高的吞吐量,为了防止LinkedBlockingQueue容量迅速增,损耗大量内存。通常在创建LinkedBlockingQueue对象时,会指定其大小,如果未指定,容量等于Integer.MAX_VALUE
PriorityBlockingQueue是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序进行排序,也可以通过自定义类实现compareTo()方法来指定元素排序规则,或者初始化时通过构造器参数Comparator来指定排序规则。
SynchronousQueue每个插入操作必须等待另一个线程进行相应的删除操作,因此,SynchronousQueue实际上没有存储任何数据元素,因为只有线程在删除数据时,其他线程才能插入数据,同样的,如果当前有线程在插入数据时,线程才能删除数据。SynchronousQueue也可以通过构造器参数来为其指定公平性。
LinkedTransferQueue是一个由链表数据结构构成的无界阻塞队列.
Queue Method | Equivalent Deque Method | 说明 |
---|---|---|
add(e) | addLast(e) | 向队尾插入 元素,失败则抛出异常 |
offer(e) | offerLast(e) | 向队尾插入 元素,失败则返回false |
remove() | removeFirst() | 获取并删除 队首元素,失败则抛出异常 |
poll() | pollFirst() | 获取并删除 队首元素,失败则返回null |
element() | getFirst() | 获取但不删除 队首元素,失败则抛出异常 |
peek() | peekFirst() | 获取但不删除 队首元素,失败则返回null |
一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常,而只是得到由 offer() 返回的 false。
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似,
但是新的 poll() 方法在用空集合调用时不是抛出异常,只是返回 null。因此新的方法更适合容易出现异常条件的情况。
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null
Stack Method | Equivalent Deque Method | 说明 |
---|---|---|
push(e) | addFirst(e) | 向栈顶插入 元素,失败则抛出异常 |
无 | offerFirst(e) | 向栈顶插入 元素,失败则返回false |
pop() | removeFirst() | 获取并删除 栈顶元素,失败则抛出异常 |
无 | pollFirst() | 获取并删除 栈顶元素,失败则返回null |
peek() | peekFirst() | 获取但不删除 栈顶元素,失败则抛出异常 |
无 | peekFirst() | 获取但不删除 栈顶元素,失败则返回null |
Deque
是Queue
的子接口。
Deque
有两个比较重要的类:ArrayDeque
和LinkedList
当使用队列功能时建议使用LikedList
当使用栈功能时建议使用ArrayDeque
转载地址:http://hsnii.baihongyu.com/