java队列的使用
㈠ java 什么情况下使用 并发队列
并发队列是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait－free”算法来实现，该算法在Michael
& Scott算法上进行了一些修改。
入队列
入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化，以及head节点和tair节点的变化，每添加一个节点我就做了一个队列的快照图。
publicEpoll(){
Node</e><e>h=head;
//p表示头节点，需要出队的节点
Node</e><e>p=h;
for(inthops=0;;hops++){
//获取p节点的元素
Eitem=p.getItem();
//如果p节点的元素不为空，使用CAS设置p节点引用的元素为null,如果成功则返回p节点的元素。
if(item!=null&&p.casItem(item,null)){
if(hops>=HOPS){
//将p节点下一个节点设置成head节点
Node</e><e>q=p.getNext();
updateHead(h,(q!=null)?q:p);
}
returnitem;
}
//如果头节点的元素为空或头节点发生了变化，这说明头节点已经被另外一个线程修改了。那么获取p节点的下一个节点
Node</e><e>next=succ(p);
//如果p的下一个节点也为空，说明这个队列已经空了
if(next==null){
//更新头节点。
updateHead(h,p);
break;
}
//如果下一个元素不为空，则将头节点的下一个节点设置成头节点
p=next;
}
returnnull;
}
首先获取头节点的元素，然后判断头节点元素是否为空，如果为空，表示另外一个线程已经进行了一次出队操作将该节点的元素取走，如果不为空，则使用CAS的方式将头节点的引用设置成null，如果CAS成功，则直接返回头节点的元素，如果不成功，表示另外一个线程已经进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点。
㈡ 到底什么是消息队列Java中如何实现消息队列
消息队列，顾名思义 首先是个队列。 队列的操作有入队和出队
也就是你有一个程序在产生内容然后入队（生产者） 另一个程序读取内容，内容出队（消费者）
这是最最基本的概念。
我想你应该是缺乏一个使用场景。
当你不需要立即获得结果，但是并发量又不能无限大的时候，差不多就是你需要使用消息队列的时候。
比如你写日志，因为可能一个客户端有多个操作去写，又有很多个客户端，显然并发不能无穷大，于是你就需要把写日志的请求放入到消息队列里，在消费者那边依次把队列中产生的日志写到数据库里。
至于怎么实现消息队列，其实你本身一个普通的队列就行呀~看你需要什么附加功能而已。
㈢ JAVA如何用队列实现并发
如果是抢资源，在不作弊的情况下
按照先来先得的规则
，那么比较简单的实现就是队列
，不管请求的并发多高，如果用线程来实现为用户服务，也就是说
来一个人请求资源那么就启动一个线程，那CPU执行线程总是有顺序的，比如
当前三个人（路人甲路人乙路人丙）请求A资源
，那服务端就起了三个线程为这三个人服务，假设
这三个人不太幸运在请求的时候没有及时的获得CPU时间片，那么他们三个相当于公平竞争CPU资源，而CPU选择运行线程是不确定顺序的
，又假设
选中了路人丙的线程运行那么将其放入队列就好了,路人乙，路人丙以此类推
，那可能会想为什么不及时的处理呢
，因为后续的操作可能是耗时操作对于线程的占用时间较长那请求资源的人多了服务端就可能挂了
㈣ 到底什么是消息队列Java中如何实现消息队列
消息队列，顾名思义首先是个队列。队列的操作有入队和出队也就是有一个程序在产生内容然后入队（生产者）另一个程序读取内容，内容出队（消费者）这是最最基本的概念。java中的消息队列消息队列是线程间通讯的手段：importjava.util.*p
㈤ 在JAVA中怎么实现消息队列
java中的消息队列
消息队列是线程间通讯的手段：
importjava.util.*
publicclassMsgQueue{
privateVectorqueue=null;
publicMsgQueue(){
queue=newVector();
}
publicsynchronizedvoidsend(Objecto)
{
queue.addElement(o);
}
publicsynchronizedObjectrecv()
{
if(queue.size()==0)
returnnull;
Objecto=queue.firstElement();
queue.removeElementAt(0);//orqueue[0]=nullcanalsowork
returno;
}
}
因为java中是lockedbyobject的所以添加synchronized就可以用于线程同步锁定对象
可以作为多线程处理多任务的存放task的队列。他的client包括封装好的task类以及thread类
Java的多线程-线程间的通信2009-08-2521:58
1.线程的几种状态
线程有四种状态，任何一个线程肯定处于这四种状态中的一种：
1)产生（New）：线程对象已经产生，但尚未被启动，所以无法执行。如通过new产生了一个线程对象后没对它调用start()函数之前。
2)可执行（Runnable）：每个支持多线程的系统都有一个排程器，排程器会从线程池中选择一个线程并启动它。当一个线程处于可执行状态时，表示它可能正处于线程池中等待排排程器启动它；也可能它已正在执行。如执行了一个线程对象的start()方法后，线程就处于可执行状态，但显而易见的是此时线程不一定正在执行中。
3)死亡（Dead）：当一个线程正常结束，它便处于死亡状态。如一个线程的run()函数执行完毕后线程就进入死亡状态。
4)停滞（Blocked）：当一个线程处于停滞状态时，系统排程器就会忽略它，不对它进行排程。当处于停滞状态的线程重新回到可执行状态时，它有可能重新执行。如通过对一个线程调用wait()函数后，线程就进入停滞状态，只有当两次对该线程调用notify或notifyAll后它才能两次回到可执行状态。
2.classThread下的常用函数函数
2.1suspend()、resume()
1)通过suspend()函数，可使线程进入停滞状态。通过suspend()使线程进入停滞状态后，除非收到resume()消息，否则该线程不会变回可执行状态。
2)当调用suspend()函数后，线程不会释放它的“锁标志”。
例11：
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicsynchronizedvoidrun(){
if(shareVar==0){
for(inti=0;i<5;i++){
shareVar++;
if(shareVar==5){
this.suspend();//（1）
}}}
else{
System.out.print(Thread.currentThread().getName());
System.out.println("shareVar="+shareVar);
this.resume();//（2）
}}
}
publicclassTestThread{
publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.start();//（5）
//t1.start();//（3）
t2.start();//（4）
}}
运行结果为：
t2shareVar=5
i.当代码（5）的t1所产生的线程运行到代码（1）处时，该线程进入停滞状态。然后排程器从线程池中唤起代码（4）的t2所产生的线程，此时shareVar值不为0，所以执行else中的语句。
ii.也许你会问，那执行代码（2）后为什么不会使t1进入可执行状态呢？正如前面所说，t1和t2是两个不同对象的线程，而代码（1）和（2）都只对当前对象进行操作，所以t1所产生的线程执行代码（1）的结果是对象t1的当前线程进入停滞状态；而t2所产生的线程执行代码（2）的结果是把对象t2中的所有处于停滞状态的线程调回到可执行状态。
iii.那现在把代码（4）注释掉，并去掉代码（3）的注释，是不是就能使t1重新回到可执行状态呢？运行结果是什么也不输出。为什么会这样呢？也许你会认为，当代码（5）所产生的线程执行到代码（1）时，它进入停滞状态；而代码（3）所产生的线程和代码（5）所产生的线程是属于同一个对象的，那么就当代码（3）所产生的线程执行到代码（2）时，就可使代码（5）所产生的线程执行回到可执行状态。但是要清楚，suspend()函数只是让当前线程进入停滞状态，但并不释放当前线程所获得的“锁标志”。所以当代码（5）所产生的线程进入停滞状态时，代码（3）所产生的线程仍不能启动，因为当前对象的“锁标志”仍被代码（5）所产生的线程占有。
#p#2.2sleep()
1)sleep()函数有一个参数，通过参数可使线程在指定的时间内进入停滞状态，当指定的时间过后，线程则自动进入可执行状态。
2)当调用sleep()函数后，线程不会释放它的“锁标志”。
例12：
{
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicsynchronizedvoidrun(){
for(inti=0;i<3;i++){
System.out.print(Thread.currentThread().getName());
System.out.println(":"+i);
try{
Thread.sleep(100);//（4）
}
catch(InterruptedExceptione){
System.out.println("Interrupted");
}}}
}
publicclassTestThread{publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.start();（1）
t1.start();（2）
//t2.start();（3）
}}
运行结果为：
t1:0
t1:1
t1:2
t1:0
t1:1
t1:2
由结果可证明，虽然在run()中执行了sleep()，但是它不会释放对象的“锁标志”，所以除非代码(1)的线程执行完run()函数并释放对象的“锁标志”，否则代码（2）的线程永远不会执行。
如果把代码（2）注释掉，并去掉代码（3）的注释，结果将变为：
t1:0
t2:0
t1:1
t2:1
t1:2
t2:2
由于t1和t2是两个对象的线程，所以当线程t1通过sleep()进入停滞时，排程器会从线程池中调用其它的可执行线程，从而t2线程被启动。
例13：
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicsynchronizedvoidrun(){
for(inti=0;i<5;i++){
System.out.print(Thread.currentThread().getName());
System.out.println(":"+i);
try{
if(Thread.currentThread().getName().equals("t1"))
Thread.sleep(200);
else
Thread.sleep(100);
}
catch(InterruptedExceptione){
System.out.println("Interrupted");
}}
}}
publicclassTestThread{publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.start();
//t1.start();
t2.start();
}}
运行结果为：
t1:0
t2:0
t2:1
t1:1
t2:2
t2:3
t1:2
t2:4
t1:3
t1:4
由于线程t1调用了sleep(200)，而线程t2调用了sleep(100)，所以线程t2处于停滞状态的时间是线程t1的一半，从从结果反映出来的就是线程t2打印两倍次线程t1才打印一次。
#p#2.3yield()
1)通过yield()函数，可使线程进入可执行状态，排程器从可执行状态的线程中重新进行排程。所以调用了yield()的函数也有可能马上被执行。
2)当调用yield()函数后，线程不会释放它的“锁标志”。
例14：
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){super(name);
}
publicsynchronizedvoidrun(){for(inti=0;i<4;i++){
System.out.print(Thread.currentThread().getName());
System.out.println(":"+i);
Thread.yield();
}}
}
publicclassTestThread{publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.start();
t1.start();//（1）
//t2.start();（2）
}
}
运行结果为：
t1:0
t1:1
t1:2
t1:3
t1:0
t1:1
t1:2
t1:3
从结果可知调用yield()时并不会释放对象的“锁标志”。
如果把代码（1）注释掉，并去掉代码（2）的注释，结果为：
t1:0
t1:1
t2:0
t1:2
t2:1
t1:3
t2:2
t2:3
从结果可知，虽然t1线程调用了yield()，但它马上又被执行了。
2.4sleep()和yield()的区别
1)sleep()使当前线程进入停滞状态，所以执行sleep()的线程在指定的时间内肯定不会执行；yield()只是使当前线程重新回到可执行状态，所以执行yield()的线程有可能在进入到可执行状态后马上又被执行。
2)sleep()可使优先级低的线程得到执行的机会，当然也可以让同优先级和高优先级的线程有执行的机会；yield()只能使同优先级的线程有执行的机会。
例15：
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicvoidrun(){
for(inti=0;i<4;i++){
System.out.print(Thread.currentThread().getName());
System.out.println(":"+i);
//Thread.yield();（1）
/*（2）*/
try{
Thread.sleep(3000);
}
catch(InterruptedExceptione){
System.out.println("Interrupted");
}}}
}
publicclassTestThread{
publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.setPriority(Thread.MAX_PRIORITY);
t2.setPriority(Thread.MIN_PRIORITY);
t1.start();
t2.start();
}
}
运行结果为：
t1:0
t1:1
t2:0
t1:2
t2:1
t1:3
t2:2
t2:3
由结果可见，通过sleep()可使优先级较低的线程有执行的机会。注释掉代码（2），并去掉代码（1）的注释，结果为：
t1:0
t1:1
t1:2
t1:3
t2:0
t2:1
t2:2
t2:3
可见，调用yield()，不同优先级的线程永远不会得到执行机会。
2.5join()
使调用join()的线程执行完毕后才能执行其它线程，在一定意义上，它可以实现同步的功能。
例16：
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicvoidrun(){
for(inti=0;i<4;i++){
System.out.println(""+i);
try{
Thread.sleep(3000);
}
catch(InterruptedExceptione){
System.out.println("Interrupted");
}
}
}
}
publicclassTestThread{
publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
t1.start();
try{
t1.join();
}
catch(InterruptedExceptione){}
t1.start();
}
}
运行结果为：
0
1
2
3
0
1
2
3
#p#3.classObject下常用的线程函数
wait()、notify()和notifyAll()这三个函数由java.lang.Object类提供，用于协调多个线程对共享数据的存取。
3.1wait()、notify()和notifyAll()
1)wait()函数有两种形式：第一种形式接受一个毫秒值，用于在指定时间长度内暂停线程，使线程进入停滞状态。第二种形式为不带参数，代表waite()在notify()或notifyAll()之前会持续停滞。
2)当对一个对象执行notify()时，会从线程等待池中移走该任意一个线程，并把它放到锁标志等待池中；当对一个对象执行notifyAll()时，会从线程等待池中移走所有该对象的所有线程，并把它们放到锁标志等待池中。
3)当调用wait()后，线程会释放掉它所占有的“锁标志”，从而使线程所在对象中的其它synchronized数据可被别的线程使用。
例17：
下面，我们将对例11中的例子进行修改
{
publicstaticintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
}
publicsynchronizedvoidrun(){
if(shareVar==0){
for(inti=0;i<10;i++){
shareVar++;
if(shareVar==5){
try{
this.wait();//（4）
}
catch(InterruptedExceptione){}
}
}
}
if(shareVar!=0){
System.out.print(Thread.currentThread().getName());
System.out.println("shareVar="+shareVar);
this.notify();//（5）
}
}
}
publicclassTestThread{
publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
TestThreadMethodt2=newTestThreadMethod("t2");
t1.start();//（1）
//t1.start();（2）
t2.start();//（3）
}}
运行结果为：
t2shareVar=5
因为t1和t2是两个不同对象，所以线程t2调用代码（5）不能唤起线程t1。如果去掉代码（2）的注释，并注释掉代码（3），结果为：
t1shareVar=5
t1shareVar=10
这是因为，当代码（1）的线程执行到代码（4）时，它进入停滞状态，并释放对象的锁状态。接着，代码（2）的线程执行run()，由于此时shareVar值为5，所以执行打印语句并调用代码（5）使代码（1）的线程进入可执行状态，然后代码（2）的线程结束。当代码（1）的线程重新执行后，它接着执行for()循环一直到shareVar=10，然后打印shareVar。
#p#3.2wait()、notify()和synchronized
waite()和notify()因为会对对象的“锁标志”进行操作，所以它们必须在synchronized函数或synchronizedblock中进行调用。如果在non-synchronized函数或non-synchronizedblock中进行调用，虽然能编译通过，但在运行时会发生IllegalMonitorStateException的异常。
例18：
{
publicintshareVar=0;
publicTestThreadMethod(Stringname){
super(name);
newNotifier(this);
}
publicsynchronizedvoidrun(){
if(shareVar==0){
for(inti=0;i<5;i++){
shareVar++;
System.out.println("i="+shareVar);
try{
System.out.println("wait......");
this.wait();
}
catch(InterruptedExceptione){}
}}
}
}
classNotifierextendsThread{
privateTestThreadMethodttm;
Notifier(TestThreadMethodt){
ttm=t;
start();
}
publicvoidrun(){
while(true){
try{
sleep(2000);
}
catch(InterruptedExceptione){}
/*1要同步的不是当前对象的做法*/
synchronized(ttm){
System.out.println("notify......");
ttm.notify();
}}
}
}
publicclassTestThread{
publicstaticvoidmain(String[]args){
TestThreadMethodt1=newTestThreadMethod("t1");
t1.start();
}
}
运行结果为：
i=1
wait......
notify......
i=2
wait......
notify......
i=3
wait......
notify......
i=4
wait......
notify......
i=5
wait......
notify......
4.wait()、notify()、notifyAll()和suspend()、resume()、sleep()的讨论
4.1这两组函数的区别
1)wait()使当前线程进入停滞状态时，还会释放当前线程所占有的“锁标志”，从而使线程对象中的synchronized资源可被对象中别的线程使用；而suspend()和sleep()使当前线程进入停滞状态时不会释放当前线程所占有的“锁标志”。
2)前一组函数必须在synchronized函数或synchronizedblock中调用，否则在运行时会产生错误；而后一组函数可以non-synchronized函数和synchronizedblock中调用。
4.2这两组函数的取舍
Java2已不建议使用后一组函数。因为在调用suspend()时不会释放当前线程所取得的“锁标志”，这样很容易造成“死锁”。
㈥ 到底什么是消息队列Java中如何实现消息队列
“消息队列”是在消息的传输过程中保存消息的容器。和我们学过的LinkedHashMap，TreeSet等一样，都是容器。既然是容器，就有有自己的特性，就像LinkedHashMap是以键值对存储。存取顺序不变。而消息队列，看到队列就可以知道。这个容器里面的消息是站好队的，一般遵从先进先出原则。
java中已经为我们封装好了很多的消息队列。在java 1.5版本时推出的java.util.concurrent中有很多现成的队列供我们使用。特性繁多，种类齐全。是你居家旅游开发必备QAQ。
下面简单列举这个包中的消息队列
:阻塞队列 BlockingQueue
数组阻塞队列 ArrayBlockingQueue
延迟队列 DelayQueue
链阻塞队列 LinkedBlockingQueue
具有优先级的阻塞队列 PriorityBlockingQueue
同步队列 SynchronousQueue
阻塞双端队列 BlockingDeque
链阻塞双端队列 LinkedBlockingDeque
不同的队列不同的特性决定了队列使用的时机，感兴趣的话你可以详细了解。具体的使用方式我就不赘述了
㈦ java 线程池 工作队列是如何工作的
使用线程池的好处
1、降低资源消耗
可以重复利用已创建的线程降低线程创建和销毁造成的消耗。
2、提高响应速度
当任务到达时，任务可以不需要等到线程创建就能立即执行。
3、提高线程的可管理性
线程是稀缺资源，如果无限制地创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配、调优和监控
线程池的工作原理
首先我们看下当一个新的任务提交到线程池之后，线程池是如何处理的
1、线程池判断核心线程池里的线程是否都在执行任务。如果不是，则创建一个新的工作线程来执行任务。如果核心线程池里的线程都在执行任务，则执行第二步。
2、线程池判断工作队列是否已经满。如果工作队列没有满，则将新提交的任务存储在这个工作队列里进行等待。如果工作队列满了，则执行第三步
3、线程池判断线程池的线程是否都处于工作状态。如果没有，则创建一个新的工作线程来执行任务。如果已经满了，则交给饱和策略来处理这个任务
线程池饱和策略
这里提到了线程池的饱和策略，那我们就简单介绍下有哪些饱和策略：
AbortPolicy
为Java线程池默认的阻塞策略，不执行此任务，而且直接抛出一个运行时异常，切记ThreadPoolExecutor.execute需要try catch，否则程序会直接退出。
DiscardPolicy
直接抛弃，任务不执行，空方法
DiscardOldestPolicy
从队列里面抛弃head的一个任务，并再次execute 此task。
CallerRunsPolicy
在调用execute的线程里面执行此command，会阻塞入口
用户自定义拒绝策略（最常用）
实现RejectedExecutionHandler，并自己定义策略模式
下我们以ThreadPoolExecutor为例展示下线程池的工作流程图
3.jpg
关键方法源码分析
我们看看核心方法添加到线程池方法execute的源码如下：
// //Executes the given task sometime in the future. The task //may execute in a new thread or in an existing pooled thread. // // If the task cannot be submitted for execution, either because this // executor has been shutdown or because its capacity has been reached, // the task is handled by the current {@code RejectedExecutionHandler}. // // @param command the task to execute // @throws RejectedExecutionException at discretion of // {@code RejectedExecutionHandler}, if the task // cannot be accepted for execution // @throws NullPointerException if {@code command} is null // public void execute(Runnable command) { if (command == null) throw new NullPointerException(); // // Proceed in 3 steps: // // 1. If fewer than corePoolSize threads are running, try to // start a new thread with the given command as its first // task. The call to addWorker atomically checks runState and // workerCount, and so prevents false alarms that would add // threads when it shouldn't, by returning false. // 翻译如下： // 判断当前的线程数是否小于corePoolSize如果是，使用入参任务通过addWord方法创建一个新的线程， // 如果能完成新线程创建exexute方法结束，成功提交任务 // 2. If a task can be successfully queued, then we still need // to double-check whether we should have added a thread // (because existing ones died since last checking) or that // the pool shut down since entry into this method. So we // recheck state and if necessary roll back the enqueuing if // stopped, or start a new thread if there are none. // 翻译如下： // 在第一步没有完成任务提交；状态为运行并且能否成功加入任务到工作队列后，再进行一次check，如果状态 // 在任务加入队列后变为了非运行（有可能是在执行到这里线程池shutdown了），非运行状态下当然是需要 // reject；然后再判断当前线程数是否为0（有可能这个时候线程数变为了0），如是，新增一个线程； // 3. If we cannot queue task, then we try to add a new // thread. If it fails, we know we are shut down or saturated // and so reject the task. // 翻译如下： // 如果不能加入任务到工作队列，将尝试使用任务新增一个线程，如果失败，则是线程池已经shutdown或者线程池 // 已经达到饱和状态，所以reject这个他任务 // int c = ctl.get(); // 工作线程数小于核心线程数 if (workerCountOf(c) < corePoolSize) { // 直接启动新线程，true表示会再次检查workerCount是否小于corePoolSize if (addWorker(command, true)) return; c = ctl.get(); } // 如果工作线程数大于等于核心线程数 // 线程的的状态未RUNNING并且队列notfull if (isRunning(c) && workQueue.offer(command)) { // 再次检查线程的运行状态，如果不是RUNNING直接从队列中移除 int recheck = ctl.get(); if (! isRunning(recheck) && remove(command)) // 移除成功，拒绝该非运行的任务 reject(command); else if (workerCountOf(recheck) == 0) // 防止了SHUTDOWN状态下没有活动线程了，但是队列里还有任务没执行这种特殊情况。 // 添加一个null任务是因为SHUTDOWN状态下，线程池不再接受新任务 addWorker(null, false); } // 如果队列满了或者是非运行的任务都拒绝执行 else if (!addWorker(command, false)) reject(command); }
㈧ java中怎么实现队列
public class Queue<E> {
private Object[] data=null;
private int maxSize; //队列容量
private int front; //队列头，允许删除
private int rear; //队列尾，允许插入
//构造函数
public Queue(){
this(10);
}
public Queue(int initialSize){
if(initialSize >=0){
this.maxSize = initialSize;
data = new Object[initialSize];
front = rear =0;
}else{
throw new RuntimeException("初始化大小不能小于0：" + initialSize);
}
}
//判空
public boolean empty(){
return rear==front?true:false;
}
//插入
public boolean add(E e){
if(rear== maxSize){
throw new RuntimeException("队列已满，无法插入新的元素！");
}else{
data[rear++]=e;
return true;
}
}
//返回队首元素，但不删除
public E peek(){
if(empty()){
throw new RuntimeException("空队列异常！");
}else{
return (E) data[front];
}
}
//出队
public E poll(){
if(empty()){
throw new RuntimeException("空队列异常！");
}else{
E value = (E) data[front]; //保留队列的front端的元素的值
data[front++] = null; //释放队列的front端的元素
return value;
}
}
//队列长度
public int length(){
return rear-front;
}
}
㈨ 单调队列怎么用java实现
单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解，ect。。。
单调队列可以有两个操作：
1、插入一个新的元素，该元素从队尾开始向队首进行搜索，找到合适的位置插入之，如果该位置原本有元素，则替换它。
2、在过程中从队首删除不符合当前要求的元素。
单调队列实现起来可简单，可复杂。简单的一个数组，一个head，一个tail指针就搞定。复杂的用双向链表实现。
用处：
1、保存最优解，次优解，ect。
2、利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。也就是说，将原本会超时的N维dp降优化至N-1维，以求通过。这也是我想记录的重点
是不是任何DP都可以利用单调队列进行优化呢？答案是否定的。
记住！只有形如 dp[i]=max/min (f[k]) + g[i] （k<i && g[i]是与k无关的变量）才能用到单调队列进行优化。
优化的对象就是f[k]。
通过例题来加深感受
http://www.acm.uestc.e.cn/problem.php?pid=1685
我要长高
Description
韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i+1的高度差（1<=i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i，增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小。
Input
有若干组数据，一直处理到文件结束。 每组数据第一行为两个整数：韩子数量N(1<=N<=50000)和舟子系数C(1<=C<=100) 接下来N行分别是韩i的高度(1<=hi<=100)。
首先建立方程，很容易想到的是，dp[i][j]表示第 i 个儿子身高为 j 的最低花费。分析题目很容易知道，当前儿子的身高花费只由前一个儿子影响。因此，
dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j))；其中x[i]是第i个儿子原本的身高
我们分析一下复杂度。
首先有N个儿子，这需要一个循环。再者，每个儿子有0到100的身高，这也需要一维。再再者，0到100的每一个身高都可以有前一位儿子的身高0到100递推而来。
所以朴素算法的时间复杂度是O(n^3)。题目只给两秒，难以接受！
分析方程：
当第 i 个儿子的身高比第 i-1 个儿子的身高要高时，
dp[i][j]=min(dp[i-1][k] + j*C-k*C + X); ( k<=j ) 其中 X=(x[i]-j)*(x[i]-j)。
当第 i 个儿子的身高比第 i-1 个儿子的身高要矮时，
dp[i][j]=min(dp[i-1][k] - j*C+k*C + X); ( k>=j )
对第一个个方程，我们令 f[i-1][k]=dp[i-1][k]-k*C, g[i][j]=j*C+X; 于是 dp[i][j] = min (f[i-1][k])+ g[i][j]。转化成这样的形式，我们就可以用单调队列进行优化了。
第二个方程同理。
接下来便是如何实现，实现起来有点技巧。具体见下
View Code
还有一个比较适合理解该优化方法的题目是HDU 3401http://acm.h.e.cn/showproblem.php?pid=3401
大概题目便是：一个人知道接下来T天的股市行情，想知道最终他能赚到多少钱。
构造状态dp[i][j]表示第i 天拥有 j只股票的时候，赚了多少钱
状态转移有：
1、从前一天不买不卖:
dp[i][j]=max(dp[i-1][j],dp[i][j])
2、从前i-W-1天买进一些股:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、从i-W-1天卖掉一些股:
dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
这里需要解释一下为什么只考虑第i-W-1天的买入卖出情况即可。想想看，i-W-2天是不是可以通过不买不卖将自己的最优状态转移到第i-W-1天？以此类推，之前的都不需要考虑了，只考虑都i-W-1天的情况即可。
对买入股票的情况进行分析，转化成适合单调队列优化的方程形式
dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，则dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。
这便可以用单调队列进行优化了。卖股的情况类似分析。
View Code
最后再说一个应用，用单调队列来优化多重背包问题 h 2191
如果有n个物品，每个物品的价格是w，重量是c，且每个物品的数量是k，那么用这样的一些物品去填满一个容量为m的背包，使得得到的背包价值最大化，这样的问题就是多重背包问题。
对于多重背包的问题，有一种优化的方法是使用二进制优化，这种优化的方法时间复杂度是O(m*∑log k[i])，具体可以见
http://www.cnblogs.com/ka200812/archive/2011/08/06/2129505.html
而利用单调队列的优化，复杂度是O(mn)
首先，对于第i件物品，如果已知体积为V，价值为W，数量为K，那么可以按照V的余数，将当前的体积J分成V组(0,1,....V-1)。
对于任意一组，可以得到转移方程：f[i*V+c]=f[k*V+c]+(i-k)*W，其中c是V组分组中的任意一个
令f[i*V+c]=dp[i]，那么就得到dp[i]=dp[k]+(i-k)*W (k>=i-K)
将dp[k]-k*W看做是优化函数，那么就可以运用单调队列来优化了
㈩ java中的队列都有哪些，有什么区别
阻塞队列、普通队列，非阻塞队列。
阻塞队列与普通队列的而区别在于，当队列是空时，从队列中获取元素的操作会被阻塞，或则当队列是满的时，往队列中增加元素会被阻塞，试图从空的队列中取元素的线程或从满的队列中添加元素的线程同样会被阻塞。