java隊列的實現
⑴ java中的隊列用什麼實現
隊列的實現單純的是數據結構的問題，既可以用鏈表結構實現隊列，也可以用數組實現。這和語言不是緊密關系，java可以這樣實現，C、C++ 也可以。
⑵ 到底什麼是消息隊列Java中如何實現消息隊列
消息隊列，顧名思義 首先是個隊列。 隊列的操作有入隊和出隊
也就是你有一個程序在產生內容然後入隊（生產者） 另一個程序讀取內容，內容出隊（消費者）
這是最最基本的概念。
我想你應該是缺乏一個使用場景。
當你不需要立即獲得結果，但是並發量又不能無限大的時候，差不多就是你需要使用消息隊列的時候。
比如你寫日誌，因為可能一個客戶端有多個操作去寫，又有很多個客戶端，顯然並發不能無窮大，於是你就需要把寫日誌的請求放入到消息隊列里，在消費者那邊依次把隊列中產生的日誌寫到資料庫里。
至於怎麼實現消息隊列，其實你本身一個普通的隊列就行呀~看你需要什麼附加功能而已。
⑶ 到底什麼是消息隊列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中是locked by object的所以添加synchronized 就可以用於線程同步鎖定對象
可以作為多線程處理多任務的存放task的隊列。他的client包括封裝好的task類以及thread類
⑷ 到底什麼是消息隊列Java中如何實現消息隊列
「消息隊列」是在消息的傳輸過程中保存消息的容器。和我們學過的LinkedHashMap，TreeSet等一樣，都是容器。既然是容器，就有有自己的特性，就像LinkedHashMap是以鍵值對存儲。存取順序不變。而消息隊列，看到隊列就可以知道。這個容器裡面的消息是站好隊的，一般遵從先進先出原則。
java中已經為我們封裝好了很多的消息隊列。在java 1.5版本時推出的java.util.concurrent中有很多現成的隊列供我們使用。特性繁多，種類齊全。是你居家旅遊開發必備QAQ。
下面簡單列舉這個包中的消息隊列
:阻塞隊列 BlockingQueue
數組阻塞隊列 ArrayBlockingQueue
延遲隊列 DelayQueue
鏈阻塞隊列 LinkedBlockingQueue
具有優先順序的阻塞隊列 PriorityBlockingQueue
同步隊列 SynchronousQueue
阻塞雙端隊列 BlockingDeque
鏈阻塞雙端隊列 LinkedBlockingDeque
不同的隊列不同的特性決定了隊列使用的時機，感興趣的話你可以詳細了解。具體的使用方式我就不贅述了
⑸ 用java實現循環隊列
簡單寫了下，希望你能看明白
import java.util.ArrayList;
public class SeqQueue {
ArrayList<String> list;
public SeqQueue() {
list = new ArrayList<String>();
}
public String getFirst() {
if (!list.isEmpty()) {
String s = list.get(0);
list.remove(0);
return s;
}
return null;
}
public void insertLast(String s) {
list.add(s);
}
public static void main(String[] args) {
SeqQueue seq = new SeqQueue();
seq.insertLast("111");
seq.insertLast("222");
seq.insertLast("333");
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
}
}
⑹ 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] （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 用什麼實現 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中如何實現按隊列執行任務
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如何用隊列實現並發
如果是搶資源，在不作弊的情況下
按照先來先得的規則
，那麼比較簡單的實現就是隊列
，不管請求的並發多高，如果用線程來實現為用戶服務，也就是說
來一個人請求資源那麼就啟動一個線程，那CPU執行線程總是有順序的，比如
當前三個人（路人甲路人乙路人丙）請求A資源
，那服務端就起了三個線程為這三個人服務，假設
這三個人不太幸運在請求的時候沒有及時的獲得CPU時間片，那麼他們三個相當於公平競爭CPU資源，而CPU選擇運行線程是不確定順序的
，又假設
選中了路人丙的線程運行那麼將其放入隊列就好了,路人乙，路人丙以此類推
，那可能會想為什麼不及時的處理呢
，因為後續的操作可能是耗時操作對於線程的佔用時間較長那請求資源的人多了服務端就可能掛了