當前位置:首頁 » 編程語言 » java實現隊列

java實現隊列

發布時間: 2022-10-05 03:39:45

Ⅰ 用java編一個隊列

自己寫了個簡單的實現

class Queue<E>{
private Object[] integerQueue;//用來當隊列
public int tail;//隊尾
public int size;//隊的長度,也可以設置一個默認值,溢出時從新申請
public Queue(int size){
integerQueue=new Object[size];
this.size=size;
tail=-1;
}
/**
* 將元素插入隊列
* @return 如果該元素已添加到此隊列,則返回 true;否則返回 false
*/
public boolean offer(E e){
if(tail <size-1){
tail++;
this.integerQueue[tail]=e;
return true;
}else{
return false;
}
}

/**
* 獲取並移除此隊列的頭,如果此隊列為空,則返回 null。
*/
public E poll(){
Object tmp;
if(tail>=0){
tmp=this.integerQueue[tail];
tail--;
return (E)tmp;
}else{
return null;
}
}
}

Ⅱ java中的隊列用什麼實現

隊列的實現單純的是數據結構的問題,既可以用鏈表結構實現隊列,也可以用數組實現。這和語言不是緊密關系,java可以這樣實現,C、C++ 也可以。

Ⅲ 到底什麼是消息隊列Java中如何實現消息隊列

「消息隊列」是在消息的傳輸過程中保存消息的容器。和我們學過的LinkedHashMap,TreeSet等一樣,都是容器。既然是容器,就有有自己的特性,就像LinkedHashMap是以鍵值對存儲。存取順序不變。而消息隊列,看到隊列就可以知道。這個容器裡面的消息是站好隊的,一般遵從先進先出原則。

java中已經為我們封裝好了很多的消息隊列。在java 1.5版本時推出的java.util.concurrent中有很多現成的隊列供我們使用。特性繁多,種類齊全。是你居家旅遊開發必備QAQ。

下面簡單列舉這個包中的消息隊列

  1. :阻塞隊列 BlockingQueue

  2. 數組阻塞隊列 ArrayBlockingQueue

  3. 延遲隊列 DelayQueue

  4. 鏈阻塞隊列 LinkedBlockingQueue

  5. 具有優先順序的阻塞隊列 PriorityBlockingQueue

  6. 同步隊列 SynchronousQueue

  7. 阻塞雙端隊列 BlockingDeque

  8. 鏈阻塞雙端隊列 LinkedBlockingDeque

    不同的隊列不同的特性決定了隊列使用的時機,感興趣的話你可以詳細了解。具體的使用方式我就不贅述了

Ⅳ 在JAVA中怎麼實現消息隊列

java中的消息隊列
消息隊列是線程間通訊的手段:

import java.util.*

public class MsgQueue{

private Vector queue = null;
public MsgQueue(){
queue = new Vector();
}
public synchronized void send(Object o)
{
queue.addElement(o);
}
public synchronized Object recv()
{
if(queue.size()==0)
return null;
Object o = queue.firstElement();
queue.removeElementAt(0);//or queue[0] = null can also work
return o;
}
}

因為java中是locked by object的所以添加synchronized 就可以用於線程同步鎖定對象
可以作為多線程處理多任務的存放task的隊列。他的client包括封裝好的task類以及thread類

Java的多線程-線程間的通信2009-08-25 21:58
1. 線程的幾種狀態
線程有四種狀態,任何一個線程肯定處於這四種狀態中的一種:
1) 產生(New):線程對象已經產生,但尚未被啟動,所以無法執行。如通過new產生了一個線程對象後沒對它調用start()函數之前。
2) 可執行(Runnable):每個支持多線程的系統都有一個排程器,排程器會從線程池中選擇一個線程並啟動它。當一個線程處於可執行狀態時,表示它可能正處於線程池中等待排排程器啟動它;也可能它已正在執行。如執行了一個線程對象的start()方法後,線程就處於可執行狀態,但顯而易見的是此時線程不一定正在執行中。
3) 死亡(Dead):當一個線程正常結束,它便處於死亡狀態。如一個線程的run()函數執行完畢後線程就進入死亡狀態。
4) 停滯(Blocked):當一個線程處於停滯狀態時,系統排程器就會忽略它,不對它進行排程。當處於停滯狀態的線程重新回到可執行狀態時,它有可能重新執行。如通過對一個線程調用wait()函數後,線程就進入停滯狀態,只有當兩次對該線程調用notify或notifyAll後它才能兩次回到可執行狀態。
2. classThread下的常用函數函數
2.1 suspend()、resume()
1) 通過suspend()函數,可使線程進入停滯狀態。通過suspend()使線程進入停滯狀態後,除非收到resume()消息,否則該線程不會變回可執行狀態。
2) 當調用suspend()函數後,線程不會釋放它的「鎖標志」。
例11:
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public synchronized void run(){
if(shareVar==0){
for(int i=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)
}}
}
public class TestThread{
public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("t2");
t1.start();//(5)
//t1.start();//(3)
t2.start();//(4)
}}
運行結果為:
t2 shareVar = 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.2 sleep()
1) sleep ()函數有一個參數,通過參數可使線程在指定的時間內進入停滯狀態,當指定的時間過後,線程則自動進入可執行狀態。
2) 當調用sleep ()函數後,線程不會釋放它的「鎖標志」。
例12:
class TestThreadMethod extends Thread{
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public synchronized void run(){
for(int i=0; i<3; i++){
System.out.print(Thread.currentThread().getName());
System.out.println(" : " + i);
try{
Thread.sleep(100);//(4)
}
catch(InterruptedException e){
System.out.println("Interrupted");
}}}
}
public class TestThread{public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("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:
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public synchronized void run(){
for(int i=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(InterruptedException e){
System.out.println("Interrupted");
}}
}}
public class TestThread{public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("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.3 yield()
1) 通過yield ()函數,可使線程進入可執行狀態,排程器從可執行狀態的線程中重新進行排程。所以調用了yield()的函數也有可能馬上被執行。
2) 當調用yield ()函數後,線程不會釋放它的「鎖標志」。
例14:
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){super(name);
}
public synchronized void run(){for(int i=0; i<4; i++){
System.out.print(Thread.currentThread().getName());
System.out.println(" : " + i);
Thread.yield();
}}
}
public class TestThread{public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("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.4 sleep()和yield()的區別
1) sleep()使當前線程進入停滯狀態,所以執行sleep()的線程在指定的時間內肯定不會執行;yield()只是使當前線程重新回到可執行狀態,所以執行yield()的線程有可能在進入到可執行狀態後馬上又被執行。
2) sleep()可使優先順序低的線程得到執行的機會,當然也可以讓同優先順序和高優先順序的線程有執行的機會;yield()只能使同優先順序的線程有執行的機會。
例15:
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public void run(){
for(int i=0; i<4; i++){
System.out.print(Thread.currentThread().getName());
System.out.println(" : " + i);
//Thread.yield();(1)
/* (2) */
try{
Thread.sleep(3000);
}
catch(InterruptedException e){
System.out.println("Interrupted");
}}}
}
public class TestThread{
public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("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.5 join()
使調用join()的線程執行完畢後才能執行其它線程,在一定意義上,它可以實現同步的功能。
例16:
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public void run(){
for(int i=0; i<4; i++){
System.out.println(" " + i);
try{
Thread.sleep(3000);
}
catch(InterruptedException e){
System.out.println("Interrupted");
}
}
}
}
public class TestThread{
public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
t1.start();
try{
t1.join();
}
catch(InterruptedException e){}
t1.start();
}
}
運行結果為:
0
1
2
3
0
1
2
3
#p#3. classObject下常用的線程函數
wait()、notify()和notifyAll()這三個函數由java.lang.Object類提供,用於協調多個線程對共享數據的存取。
3.1 wait()、notify()和notifyAll()
1) wait()函數有兩種形式:第一種形式接受一個毫秒值,用於在指定時間長度內暫停線程,使線程進入停滯狀態。第二種形式為不帶參數,代表waite()在notify()或notifyAll()之前會持續停滯。
2) 當對一個對象執行notify()時,會從線程等待池中移走該任意一個線程,並把它放到鎖標志等待池中;當對一個對象執行notifyAll()時,會從線程等待池中移走所有該對象的所有線程,並把它們放到鎖標志等待池中。
3) 當調用wait()後,線程會釋放掉它所佔有的「鎖標志」,從而使線程所在對象中的其它synchronized數據可被別的線程使用。
例17:
下面,我們將對例11中的例子進行修改
class TestThreadMethod extends Thread{
public static int shareVar = 0;
public TestThreadMethod(String name){
super(name);
}
public synchronized void run(){
if(shareVar==0){
for(int i=0; i<10; i++){
shareVar++;
if(shareVar==5){
try{
this.wait();//(4)
}
catch(InterruptedException e){}
}
}
}
if(shareVar!=0){
System.out.print(Thread.currentThread().getName());
System.out.println(" shareVar = " + shareVar);
this.notify();//(5)
}
}
}
public class TestThread{
public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("t1");
TestThreadMethod t2 = new TestThreadMethod("t2");
t1.start();//(1)
//t1.start();(2)
t2.start();//(3)
}}
運行結果為:
t2 shareVar = 5
因為t1和t2是兩個不同對象,所以線程t2調用代碼(5)不能喚起線程t1。如果去掉代碼(2)的注釋,並注釋掉代碼(3),結果為:
t1 shareVar = 5
t1 shareVar = 10
這是因為,當代碼(1)的線程執行到代碼(4)時,它進入停滯狀態,並釋放對象的鎖狀態。接著,代碼(2)的線程執行run(),由於此時shareVar值為5,所以執行列印語句並調用代碼(5)使代碼(1)的線程進入可執行狀態,然後代碼(2)的線程結束。當代碼(1)的線程重新執行後,它接著執行for()循環一直到shareVar=10,然後列印shareVar。
#p#3.2 wait()、notify()和synchronized
waite()和notify()因為會對對象的「鎖標志」進行操作,所以它們必須在synchronized函數或synchronizedblock中進行調用。如果在non-synchronized函數或non-synchronizedblock中進行調用,雖然能編譯通過,但在運行時會發生IllegalMonitorStateException的異常。
例18:
class TestThreadMethod extends Thread{
public int shareVar = 0;
public TestThreadMethod(String name){
super(name);
new Notifier(this);
}
public synchronized void run(){
if(shareVar==0){
for(int i=0; i<5; i++){
shareVar++;
System.out.println("i = " + shareVar);
try{
System.out.println("wait......");
this.wait();
}
catch(InterruptedException e){}
}}
}
}
class Notifier extends Thread{
private TestThreadMethod ttm;
Notifier(TestThreadMethod t){
ttm = t;
start();
}
public void run(){
while(true){
try{
sleep(2000);
}
catch(InterruptedException e){}
/*1 要同步的不是當前對象的做法 */
synchronized(ttm){
System.out.println("notify......");
ttm.notify();
}}
}
}
public class TestThread{
public static void main(String[] args){
TestThreadMethod t1 = new TestThreadMethod("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中如何實現按隊列執行任務

package com.tone.example;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.tone.task.TaskProperty;
import com.tone.task.TaskSignature;
import com.tone.task.impl.BasicTask;
import com.tone.task.runner.TaskRunner;

/**
* 任務隊列示常式序
* @author zlf
*/
public class TaskExample {
private TaskRunner taskRunner;

/**
* 做任務隊列的初始化工作
*/
@Before
public void init() {
// 獲取任務運行器
taskRunner = TaskRunner.getInstance();
// 將任務運行器放入線程進行調度
Thread thread = new Thread(taskRunner);
thread.start();
}

/**
* 等待任務執行完成,並做最後的退出工作
*/
@After
public void exit() throws InterruptedException {
Thread.sleep(600);
System.exit(0);
}

/**
* 最簡單的任務運行示例
*/
@Test
public void example1() {
// 添加任務到任務運行器
taskRunner.addTask(new BasicTask() {
@Override
public void run() {
System.out.println("This is running in task runner thread, and thread is " + Thread.currentThread());
}
});
}

/**
* 加入優先執行順序的任務運行器
*/
@Test
public void example2() {
// 添加任務到任務運行器
taskRunner.addTask(new BasicTask(0) {
@Override
public void run() {
System.out.println("This is a normal task");
}
});
taskRunner.addTask(new BasicTask(-1) {
@Override
public void run() {
System.out.println("This is a task a bit high than normal");
}
});
}

/**
* 重復添加的任務只會運行第一個
*/
@Test
public void example3() {
// 添加任務到任務運行器
taskRunner.addTask(new BasicTask(TaskSignature.ONE) {
@Override
public void run() {
System.out.println("This is task one");
}
}, TaskProperty.NOT_REPEAT);
taskRunner.addTask(new BasicTask(TaskSignature.ONE) {
@Override
public void run() {
System.out.println("This is also task one");
}
}, TaskProperty.NOT_REPEAT);
}

/**
* 重復添加的任務只會運行最後一個
*/
@Test
public void example4() {
// 添加任務到任務運行器
taskRunner.addTask(new BasicTask(TaskSignature.ONE) {
@Override
public void run() {
System.out.println("This is task one");
}
}, TaskProperty.NOT_REPEAT_OVERRIDE);
taskRunner.addTask(new BasicTask(TaskSignature.ONE) {
@Override
public void run() {
System.out.println("This is also task one");
}
}, TaskProperty.NOT_REPEAT_OVERRIDE);
}
}

Ⅵ JAVA中,常用的隊列實現是哪個

隊列的實現單純的是數據結構的問題,既可以用鏈表結構實現隊列,也可以用數組實現。這和語言不是緊密關系,java可以這樣實現,c、c++
也可以。

Ⅶ java 用什麼實現 FIFO隊列

java使用數據結構來實現FIFO先進先出的隊列,實例如下:

/*
*Tochangethistemplate,chooseTools|Templates
*andopenthetemplateintheeditor.
*/
packagelinkedlisttest;

importjava.util.ArrayList;
importjava.util.Deque;
importjava.util.LinkedList;
importjava.util.List;

/**
*
*@authorVicky.H
*@[email protected]
*/
publicclassFIFOTest{

/**
*@
*/
publicstaticvoidmain(String[]args){
FIFO<A>fifo=newFIFOImpl<A>(5);
for(inti=0;i<20;i++){
Aa=newA("A:"+i);
Ahead=fifo.addLastSafe(a);
System.out.println(i+" head:"+head+" size:"+fifo.size());
}

System.out.println("---------------");

System.out.println("彈出數據");
List<A>polls=fifo.setMaxSize(3);
for(Aa:polls){
System.out.println(" head:"+a);
}

System.out.println("剩餘數據");
for(Aa:fifo){
System.out.println(" head:"+a);
}
System.out.println(fifo.size());
}
}

interfaceFIFO<T>extendsList<T>,Deque<T>,Cloneable,java.io.Serializable{

/**
*向最後添加一個新的,如果長度超過允許的最大值,則彈出一個*
*/
TaddLastSafe(TaddLast);

/**
*彈出head,如果Size=0返回null。而不同於pop拋出異常
*@return
*/
TpollSafe();

/**
*獲得最大保存
*
*@return
*/
intgetMaxSize();

/**
*設置最大存儲范圍
*
*@return返回的是,因為改變了隊列大小,導致彈出的head
*/
List<T>setMaxSize(intmaxSize);

}

classFIFOImpl<T>extendsLinkedList<T>implementsFIFO<T>{

privateintmaxSize=Integer.MAX_VALUE;
privatefinalObjectsynObj=newObject();

publicFIFOImpl(){
super();
}

publicFIFOImpl(intmaxSize){
super();
this.maxSize=maxSize;
}

@Override
publicTaddLastSafe(TaddLast){
synchronized(synObj){
Thead=null;
while(size()>=maxSize){
head=poll();
}
addLast(addLast);
returnhead;
}
}

@Override
publicTpollSafe(){
synchronized(synObj){
returnpoll();
}
}

@Override
publicList<T>setMaxSize(intmaxSize){
List<T>list=null;
if(maxSize<this.maxSize){
list=newArrayList<T>();
synchronized(synObj){
while(size()>maxSize){
list.add(poll());
}
}
}
this.maxSize=maxSize;
returnlist;
}

@Override
publicintgetMaxSize(){
returnthis.maxSize;
}
}

classA{

privateStringname;

publicA(){
}

publicA(Stringname){
this.name=name;
}

publicStringgetName(){
returnname;
}

publicvoidsetName(Stringname){
this.name=name;
}

@Override
publicStringtoString(){
return"A{"+"name="+name+'}';
}
}

Ⅷ 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動態增長隊列的實現

java裡面支持隊列這種數據結構,只要實現Queue<E>介面即可,比如下面實現了一個能容納String的隊列:
import java.util.*;
public class DynamicQueue{
private Queue<String> queue = new LinkedList<String>();
public void enque(String s) {
queue.offer(s);
}
public String deque() {
return queue.poll();
}
public static void main(String[] args){
DynamicQueue d_queue = new DynamicQueue();
d_queue.enque("123");
d_queue.enque("234");
d_queue.enque("345");
System.out.println(d_queue.deque());
System.out.println(d_queue.deque());
System.out.println(d_queue.deque());
}
}

Ⅹ 單調隊列怎麼用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看做是優化函數,那麼就可以運用單調隊列來優化了

熱點內容
監控腳本實用 發布:2022-11-30 14:14:28 瀏覽:371
九陰真經顯血腳本 發布:2022-11-30 14:14:22 瀏覽:190
浪潮伺服器mgn口地址 發布:2022-11-30 14:13:41 瀏覽:789
linux鎖屏設置 發布:2022-11-30 14:08:20 瀏覽:886
演算法轉讓 發布:2022-11-30 14:07:24 瀏覽:16
我的世界為什麼從伺服器斷開連接 發布:2022-11-30 14:07:04 瀏覽:383
怎麼擠出母乳存儲袋中的空氣 發布:2022-11-30 14:05:32 瀏覽:27
linuxbin文件 發布:2022-11-30 14:01:19 瀏覽:474
購物網站源碼php 發布:2022-11-30 13:58:15 瀏覽:466
python執行java 發布:2022-11-30 13:56:23 瀏覽:936