我们都知道队列(Queue)是一种先进先出(FIFO)的数据结构,Java中定义了java.util.Queue
接口用来表示队列。Java中的Queue
与List
、Set
属于同一个级别接口,它们都是继承于Collection
接口。
Java中还定义了一种双端队列java.util.Deque
,我们常用的LinkedList
就是实现了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
是双相链表结构,在添加和删除元素时具有比ArrayList
更好的性能。但在 Get 与 Set 方面弱于ArrayList
。当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比。java.util.Comparator
接口的排序类来指定元素排列的顺序。ConcurrentLinkedQueue
是基于链接节点的并且线程安全的队列。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大小 ConcurrentLinkedQueue
对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。阻塞队列定义在了java.util.concurrent
包中,java.util.concurrent.BlockingQueue
继承了Queue
接口,它有 5 个实现类,分别是:
Integer.MAX_VALUE
,也可以看成容量无限大。此队列按 FIFO(先进先出)排序元素 。下面简单介绍一下其中常用的方法:
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();
}
}
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){
}
}
}