阻塞队列BlokingQueue与双向队列Deque

Queue：基本上，一个队列就是一个先入先出（FIFO）的数据结构

Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接口。

Queue的实现

1、没有实现的阻塞接口的LinkedList：实现了java.util.Queue接口和java.util.AbstractQueue接口

　　内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue

　　PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。

　　PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。

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

2)实现阻塞接口的：

　　java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。

五个队列所提供的各有不同：

　　* ArrayBlockingQueue ：一个由数组支持的有界队列。

　　* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。

　　* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。

　　* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。

　　* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

阻塞队列BlokingQueue与双向队列Deque

下表显示了jdk1.5中的阻塞队列的操作：

　　add 增加一个元索如果队列已满，则抛出一个IIIegaISlabEepeplian异常

　　remove 移除并返回队列头部的元素如果队列为空，则抛出一个NoSuchElementException异常

　　element 返回队列头部的元素如果队列为空，则抛出一个NoSuchElementException异常

　　offer 添加一个元素并返回true 如果队列已满，则返回false

　　poll 移除并返问队列头部的元素如果队列为空，则返回null

　　peek 返回队列头部的元素如果队列为空，则返回null

　　put 添加一个元素如果队列满，则阻塞

　　take 移除并返回队列头部的元素如果队列为空，则阻塞

remove、element、offer 、poll、peek 其实是属于Queue接口。

阻塞队列的操作可以根据它们的响应方式分为以下三类：aad、removee和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时抛出异常。当然，在多线程程序中，队列在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时只是给出一个出错示而不会抛出异常。

注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的

最后，我们有阻塞操作put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。

LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。

ArrayBlockingQueue在构造时需要指定容量，并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列，此队列按 FIFO（先进先出）原则对元素进行排序。

PriorityBlockingQueue是一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元素要具有比较能力。

DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

阻塞队列BlokingQueue与双向队列Deque

package com.lx.bale;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

import org.junit.Test;

public class QueueTest {
	public static void main(String[] args) throws InterruptedException {
		final BlockingQueue<Object> queue = new LinkedBlockingQueue<Object>(3);
		queue.add("11");
		queue.add("22");
		queue.add("33");
		new Thread(new Runnable() {
			public void run() {
				try {
					Thread.sleep(3000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println(queue.poll());
			}
		}).start();
		queue.put("44");
		System.out.println(queue.poll());
		System.out.println(queue.poll());
		System.out.println(queue.poll());

	}
	
	@Test
	public void fun01() throws InterruptedException{
		/**
		 * ArrayBlockingQueue 等待时间长的线程优先加入,但LinkedBlokingQueue貌似也是一样 等待长的先加入
		 */
		final BlockingQueue<Object> queue = new ArrayBlockingQueue<Object>(1);
		queue.offer("baseData");
		
		//线程1
		final Thread t1 = new Thread(new Runnable() {
			@Override
			public void run() {
				int count = 0;
				while (true) {
					try {
						Thread.sleep(1000);
						count ++;
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
					if (count > 8) {
						//System.out.println("跳出循环");
						break;
					}
				}
			}
		});
		t1.start();
		// 启动线程2
		final Thread t2 = new Thread(new Runnable() {
			@Override
			public void run() {
				int count = 0;
				while (true) {
					try {
						Thread.sleep(1000);
						count ++;
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
					if (count > 8) {
						//System.out.println("跳出循环");
						break;
					}
				}
			}
		});
		t2.start();
		
		
		//插入t1 阻塞
		Thread t1Insert = new Thread(new Runnable() {
			@Override
			public void run() {
				try {
					System.out.println("t1插入阻塞");
					queue.put(t1);
					System.out.println("t1插入成功");
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});
		t1Insert.start();
		Thread.sleep(1000);
		//插入t2 阻塞
		Thread t2Insert = new Thread(new Runnable() {
			@Override
			public void run() {
				try {
					System.out.println("t2插入阻塞");
					queue.put(t2);
					System.out.println("t2插入成功");
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		});
		t2Insert.start();
		
		
		
		Thread.sleep(3000);
		System.out.println("取出原始对象"+queue.poll());
		
		/*while (true) {
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			if (t1.isAlive()) {
				System.out.println("线程存活");
			}else{
				System.out.println("线程完毕");
			}
		}*/
		
	}
	@Test
	public void fun02(){
		PriorityBlockingQueue<Object> queue = new PriorityBlockingQueue<Object>();
		queue.put(new String());
	}
}

双向队列Deque

一.概述

　　Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素,因此Deque既可以支持LIFO形式也可以支持LIFO形式.Deque接口是一种比Stack和Vector更为丰富的抽象数据形式,因为它同时实现了以上两者.

二.主要方法

修饰符和返回值	方法名	描述
添加功能
void	push(E)	向队列头部插入一个元素,失败时抛出异常
void	addFirst(E)	向队列头部插入一个元素,失败时抛出异常
void	addLast(E)	向队列尾部插入一个元素,失败时抛出异常
boolean	offerFirst(E)	向队列头部加入一个元素,失败时返回false
boolean	offerLast(E)	向队列尾部加入一个元素,失败时返回false
获取功能
E	getFirst()	获取队列头部元素,队列为空时抛出异常
E	getLast()	获取队列尾部元素,队列为空时抛出异常
E	peekFirst()	获取队列头部元素,队列为空时返回null
E	peekLast()	获取队列尾部元素,队列为空时返回null
删除功能
boolean	removeFirstOccurrence(Object)	删除第一次出现的指定元素,不存在时返回false
boolean	removeLastOccurrence(Object)	删除最后一次出现的指定元素,不存在时返回false
弹出功能
E	pop()	弹出队列头部元素,队列为空时抛出异常
E	removeFirst()	弹出队列头部元素,队列为空时抛出异常
E	removeLast()	弹出队列尾部元素,队列为空时抛出异常
E	pollFirst()	弹出队列头部元素,队列为空时返回null
E	pollLast()	弹出队列尾部元素,队列为空时返回null
迭代器
Iterator<E>	descendingIterator()	返回队列反向迭代器

可以看出Deque在Queue的方法上新添了对队列头尾元素的操作,add,remove,get形式的方法会在有界队列满员和空队列时抛出异常,offer,poll,peek形式的方法则会返回false或null.

此外方法表中需要注意push = addFirst,pop = removeFirst,只是使用了不同的方法名体现队列表示栈结构时的特点.

三.实现

　　同Queue一样Deque的实现也可以划分成通用实现和并发实现.

　　通用实现主要有两个实现类ArrayDeque和LinkedList.

　　ArrayDeque是个可变数组,它是在Java 6之后新添加的,而LinkedList是一种链表结构的list.LinkedList要比ArrayDeque更加灵活,因为它也实现了List接口的所有操作,并且可以插入null元素,这在ArrayDeque中是不允许的.

　　从效率来看,ArrayDeque要比LinkedList在两端增删元素上更为高效,因为没有在节点创建删除上的开销.最适合使用LinkedList的情况是迭代队列时删除当前迭代的元素.此外LinkedList可能是在遍历元素时最差的数据结构,并且也LinkedList占用更多的内存,因为LinkedList是通过链表连接其整个队列,它的元素在内存中是随机分布的,需要通过每个节点包含的前后节点的内存地址去访问前后元素.

　　总体ArrayDeque要比LinkedList更优越,在大队列的测试上有3倍与LinkedList的性能,最好的是给ArrayDeque一个较大的初始化大小,以避免底层数组扩容时数据拷贝的开销.

　　LinkedBlockingDeque是Deque的并发实现,在队列为空的时候,它的takeFirst,takeLast会阻塞等待队列处于可用状态

阻塞队列BlokingQueue与双向队列Deque

双向队列Deque

一.概述

二.主要方法

三.实现

继续阅读

UVA - 210 Concurrency Simulator(双端队列)

STL源码剖析笔记之四序列式容器

队列（二）：Deque

队列Queue、双端队列Deque源码分析及底层原理队列Queue优先队列PriorityQueue双端队列Deque

双端队列Deque基本操作的C语言实现

STL学习--deque简介特性面试题源码（STL3.3）

stl标准库系列之--deque

使用PriorityQueue实现大小根堆

剑指offer JZ29 最小的K个数

【Java-8-源码-1】LinkedList、Queue、Deque

一文弄懂java中的Queue家族

leetcode1091. 二进制矩阵中的最短路径（bfs）

爬虫基础利用xpath,requests,lxml,多线程爬取斗图啦表情包

从上到下打印二叉树（Java）

Timer和TimerTask源码解读（面试题：双重定时器）Timer和TimerTask源码解读

Python多线程和多进程Python多线程python多进程