Java 中的队列 Queue

一、队列的定义

我们都知道队列(Queue)是一种先进先出(FIFO)的数据结构,Java中定义了java.util.Queue接口用来表示队列。Java中的QueueListSet属于同一个级别接口,它们都是继承于Collection接口。

Java中还定义了一种双端队列java.util.Deque,我们常用的LinkedList就是实现了Deque接口。

下面我们看一下类的定义:

Queue & Deque
public interface Queue<E> extends Collection<E> {

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}
public interface Deque<E> extends Queue<E> {

    void addFirst(E e);

    void addLast(E e);

    boolean offerFirst(E e);

    boolean offerLast(E e);

    E removeFirst();

    E removeLast();

    E pollFirst();

    E pollLast();

    E getFirst();

    E getLast();

    E peekFirst();

    E peekLast();

    boolean removeFirstOccurrence(Object o);

    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();

    // *** Stack methods ***

    void push(E e);

    E pop();

	// *** Collection methods ***

    boolean remove(Object o);

    boolean contains(Object o);

    public int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();

}

二、队列的实现

Java中对于队列的实现分为非阻塞阻塞两种。

$ 非阻塞队列分为如下:

  • LinkedList

    LinkedList是双相链表结构,在添加和删除元素时具有比ArrayList更好的性能。但在 Get 与 Set 方面弱于ArrayList。当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比。

  • PriorityQueue

    PriorityQueue维护了一个有序列表,存储到队列中的元素会按照自然顺序排列。当然,我们也可以给它指定一个实现了 java.util.Comparator 接口的排序类来指定元素排列的顺序。

  • ConcurrentLinkedQueue

    ConcurrentLinkedQueue 是基于链接节点的并且线程安全的队列。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大小 ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。

$ 阻塞队列分为如下:

阻塞队列定义在了java.util.concurrent包中,java.util.concurrent.BlockingQueue 继承了Queue接口,它有 5 个实现类,分别是:

  • ArrayBlockingQueue

    一个内部由数组支持的有界队列。初始化时必须指定队列的容量,还可以设置内部的ReentrantLock是否使用公平锁。但是公平性会使你在性能上付出代价,只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列,此队列按 FIFO(先进先出)原则对元素进行排序。

    它的思想就是如果BlockQueue是空的,那么从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒。同样,如果BlockingQueue是满的,任何试图往里存东西的操作也会被阻断进入等待状态,直到BlockingQueue里有空间才会被唤醒继续操作。

  • **LinkedBlockingQueue **

    一个内部由链接节点支持的可选有界队列。初始化时不需要指定队列的容量,默认是Integer.MAX_VALUE ,也可以看成容量无限大。此队列按 FIFO(先进先出)排序元素 。

  • PriorityBlockingQueue

    一个内部由优先级堆支持的*优先级队列。PriorityBlockingQueue是对 PriorityQueue的再次包装,队列中的元素按优先级顺序被移除。

  • DelayQueue

    一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素,只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll中元素,否则poll()方法会返回null。  

  • SynchronousQueue

    一个利用 BlockingQueue 接口的简单聚集(rendezvous)机制。

下面简单介绍一下其中常用的方法:

  • add         增加一个元索                      如果队列已满,则抛出一个IIIegaISlabEepeplian异常   
  • remove   移除并返回队列头部的元素    如果队列为空,则抛出一个NoSuchElementException异常   
  • element  返回队列头部的元素              如果队列为空,则抛出一个NoSuchElementException异常   
  • offer        添加一个元素并返回true        如果队列已满,则返回false   
  • poll          移除并返问队列头部的元素    如果队列为空,则返回null   
  • peek        返回队列头部的元素              如果队列为空,则返回null   
  • put          添加一个元素                       如果队列满,则阻塞   
  • take         移除并返回队列头部的元素   如果队列为空,则阻塞

三、示例

package com.ysc.thread;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue; public class BlockingQueueTest { public static void main(String[] args) {
final BlockingQueue queue = new ArrayBlockingQueue(3);
for(int i=0;i<2;i++){
new Thread(){
public void run(){
while(true){
try {
Thread.sleep((long)(Math.random()*1000));
System.out.println(Thread.currentThread().getName() + "准备放数据!");
queue.put(1);
System.out.println(Thread.currentThread().getName() + "已经放了数据," +
"队列目前有" + queue.size() + "个数据");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}.start();
} new Thread(){
public void run(){
while(true){
try {
//将此处的睡眠时间分别改为100和1000,观察运行结果
Thread.sleep(1000);
System.out.println(Thread.currentThread().getName() + "准备取数据!");
queue.take();
System.out.println(Thread.currentThread().getName() + "已经取走数据," +
"队列目前有" + queue.size() + "个数据");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}.start();
}
}
package com.ysc.thread;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock; public class BlockingQueueCondition { public static void main(String[] args) {
ExecutorService service = Executors.newSingleThreadExecutor();
final Business business = new Business();
service.execute(new Runnable(){
@Override
public void run() {
for(int i=0;i<50;i++){
business.sub();
}
}
}); for(int i=0;i<50;i++){
business.main();
}
} } class Business {
BlockingQueue subQueue = new ArrayBlockingQueue(1);
BlockingQueue mainQueue = new ArrayBlockingQueue(1);
//这里是匿名构造方法,只要new一个对象都会调用这个匿名构造方法,它与静态块不同,静态块只会执行一次,
//在类第一次加载到JVM的时候执行
//这里主要是让main线程首先put一个,就有东西可以取,如果不加这个匿名构造方法put一个的话程序就死锁了
{
try {
mainQueue.put(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void sub(){
try {
mainQueue.take();
for(int i=0;i<10;i++){
System.out.println(Thread.currentThread().getName() + " : " + i);
}
subQueue.put(1);
} catch (Exception e){
}
} public void main() {
try {
subQueue.take();
for(int i=0;i<5;i++){
System.out.println(Thread.currentThread().getName() + " : " + i);
}
mainQueue.put(1);
} catch (Exception e){
}
}
}
上一篇:EF6 Code First & Auto Migration on Appharbor


下一篇:Java中的队列Queue,优先级队列PriorityQueue