java實現隊列,java隊列實現類

本文目錄一覽：

• 1、單調隊列怎麼用java實現
• 2、java 用什麼實現 FIFO隊列？
• 3、到底什麼是消息隊列？Java中如何實現消息隊列
• 4、怎麼編寫一個簡單的java隊列?
• 5、JAVA中，常用的隊列實現是哪個？
• 6、java中如何實現按隊列執行任務

單調隊列怎麼用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] （ki g[i]是與k無關的變量）才能用到單調隊列進行優化。

優化的對象就是f[k]。

通過例題來加深感受

我要長高

Description

韓父有N個兒子，分別是韓一，韓二…韓N。由於韓家演技功底深厚，加上他們間的密切配合，演出獲得了巨大成功，票房甚至高達2000萬。舟子是名很有威望的公知，可是他表面上兩袖清風實則內心陰暗，看到韓家紅紅火火，嫉妒心遂起，便發微薄調侃韓二們站成一列時身高參差不齊。由於舟子的影響力，隨口一句便會造成韓家的巨大損失，具體虧損是這樣計算的，韓一，韓二…韓N站成一排，損失即為C*（韓i與韓i+1的高度差（1=iN））之和，搞不好連女兒都賠了.韓父苦苦思索，決定給韓子們內增高（注意韓子們變矮是不科學的只能增高或什麼也不做），增高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 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

最後再說一個應用，用單調隊列來優化多重背包問題 hdu 2191

如果有n個物品，每個物品的價格是w，重量是c，且每個物品的數量是k，那麼用這樣的一些物品去填滿一個容量為m的背包，使得得到的背包價值最大化，這樣的問題就是多重背包問題。

對於多重背包的問題，有一種優化的方法是使用二進制優化，這種優化的方法時間複雜度是O(m*∑log k[i])，具體可以見

而利用單調隊列的優化，複雜度是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 用什麼實現 FIFO隊列？

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

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package linkedlisttest;

import java.util.ArrayList;

import java.util.Deque;

import java.util.LinkedList;

import java.util.List;

/**

 *

 * @author Vicky.H

 * @email eclipser@163.com

 */

public class FIFOTest {

    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) {

        FIFOA fifo = new FIFOImplA(5);

        for (int i = 0; i  20; i++) {

            A a = new A(“A:” + i);

            A head = fifo.addLastSafe(a);

            System.out.println(i + “\thead:” + head + “\tsize:” + fifo.size());

        }

        System.out.println(“—————“);

        System.out.println(“彈出數據”);

        ListA polls = fifo.setMaxSize(3);

        for (A a : polls) {

            System.out.println(“\thead:” + a);

        }

        System.out.println(“剩餘數據”);

        for (A a : fifo) {

            System.out.println(“\thead:” + a);

        }

        System.out.println(fifo.size());

    }

}

interface FIFOT extends ListT, DequeT, Cloneable, java.io.Serializable {

    /**

     * 向最後添加一個新的，如果長度超過允許的最大值，則彈出一個 *

     */

    T addLastSafe(T addLast);

    /**

     * 彈出head，如果Size = 0返回null。而不同於pop拋出異常

     * @return 

     */

    T pollSafe();

    /**

     * 獲得最大保存

     *

     * @return

     */

    int getMaxSize();

    /**

     * 設置最大存儲範圍

     *

     * @return 返回的是，因為改變了隊列大小，導致彈出的head

     */

    ListT setMaxSize(int maxSize);

}

class FIFOImplT extends LinkedListT implements FIFOT {

    private int maxSize = Integer.MAX_VALUE;

    private final Object synObj = new Object();

    public FIFOImpl() {

        super();

    }

    public FIFOImpl(int maxSize) {

        super();

        this.maxSize = maxSize;

    }

    @Override

    public T addLastSafe(T addLast) {

        synchronized (synObj) {

            T head = null;

            while (size() = maxSize) {

                head = poll();

            }

            addLast(addLast);

            return head;

        }

    }

    @Override

    public T pollSafe() {

        synchronized (synObj) {

            return poll();

        }

    }

    @Override

    public ListT setMaxSize(int maxSize) {

        ListT list = null;

        if (maxSize  this.maxSize) {

            list = new ArrayListT();

            synchronized (synObj) {

                while (size()  maxSize) {

                    list.add(poll());

                }

            }

        }

        this.maxSize = maxSize;

        return list;

    }

    @Override

    public int getMaxSize() {

        return this.maxSize;

    }

}

class A {

    private String name;

    public A() {

    }

    public A(String name) {

        this.name = name;

    }

    public String getName() {

        return name;

    }

    public void setName(String name) {

        this.name = name;

    }

    @Override

    public String toString() {

        return “A{” + “name=” + name + ‘}’;

    }

}

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

消息隊列就是在完全處理完隊列中最前面的數據之前，其他的數據信息會依次在隊列中排好隊，然後一個一個數據去處理

java的消息隊列用別人寫好的插件用就行了，java自帶的sycronization雖然可以實現，但是擴展性很差，且使用效率也不行，其他的插件有很多，都是MQ，你百度搜索消息隊列MQ 就好了

怎麼編寫一個簡單的java隊列?

import java.util.*;

public class MyQueueT {

private LinkedListT list = new LinkedListT();

public void addLast(T v) {

list.addLast(v); //隊尾插入

}

public T getFirst() {

return list.getFirst(); //取得隊受元素

}

public void remove() {

list.removeFirst(); //移除隊首元素

}

//類似功能自己擴展下

public static void main(String[] args) {

MyQueueString mq = new MyQueueString();

mq.addLast(“hello world”);

mq.addLast(“hello world2”);

System.out.println(mq.getFirst());

mq.remove();

System.out.println(mq.getFirst());

}

}

JAVA中，常用的隊列實現是哪個？

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

也可以。

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);

}

}