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

}

}