本文目录一览：
- 1、链表怎么写，以clh队列为例子说了下双向链表的队列怎么实现
- 2、Java语言没有指针，怎样实现链表?
- 3、JAVA中LinkedList的底层实现是链表还是队列?
- 4、单调队列怎么用java实现
- 5、Java如何实现一个循环队列保存另一个类的对象
- 6、java如何实现链表
链表怎么写，以clh队列为例子说了下双向链表的队列怎么实现
正如tanyuguo所说，单循环链表实现队列的出列操作的复杂度过高，因此推荐用带头指针的双向循环链表实现队列操作。前几天已经写过了，但代码不在身边。
Java语言没有指针，怎样实现链表?
Java语言中的对象引用实际上是一个指针（这里的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
程序代码：
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
链表的数据结构我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点，因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。如何得到当前结点呢？我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
package cn.javatx; import java.io.IOException;/**
* @author ljfan
*
*/
public class List {
private Node Head = null;
private Node Tail = null;
private Node Pointer = null;
private int Length = 0;public void deleteAll() {
Head = null;
Tail = null;
Pointer = null;
Length = 0;
}public void reset() {
Pointer = null;
}public boolean isEmpty() {
return (Length == 0);
}public boolean isEnd() {
if (Length == 0)
throw new java.lang.NullPointerException();
else if (Length == 1)
return true;
else
return (cursor() == Tail);
}public Object nextNode() {
if (Length == 1)
throw new java.util.NoSuchElementException();
else if (Length == 0)
throw new java.lang.NullPointerException();
else {
Node temp = cursor();
Pointer = temp;
if (temp != Tail)
return (temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}public Object currentNode() {
Node temp = cursor();
return temp.data;
}public void insert(Object d) {
Node e = new Node(d);
if (Length == 0) {
Tail = e;
Head = e;
} else {
Node temp = cursor();
e.next = temp;
if (Pointer == null)
Head = e;
else
Pointer.next = e;
}
Length++;
}public int size() {
return (Length);
}public Object remove() {
Object temp;
if (Length == 0)
throw new java.util.NoSuchElementException();
else if (Length == 1) {
temp = Head.data;
deleteAll();
} else {
Node cur = cursor();
temp = cur.data;
if (cur == Head)
Head = cur.next;
else if (cur == Tail) {
Pointer.next = null;
Tail = Pointer;
reset();
} else
Pointer.next = cur.next;
Length--;
}
return temp;
}private Node cursor() {
if (Head == null)
throw new java.lang.NullPointerException();
else if (Pointer == null)
return Head;
else
return Pointer.next;
}public static void main(String[] args) {
List a = new List();
for (int i = 1; i = 10; i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while (!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while (!a.isEnd()) {
a.remove();
}
a.remove();
a.reset();
if (a.isEmpty())
System.out.println("There is no Node in List n");
System.out.println("You can press return to quitn");
try {
System.in.read();
} catch (IOException e) {
}
}
}class Node {
Object data;
Node next;Node(Object d) {
data = d;
next = null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中
JAVA中LinkedList的底层实现是链表还是队列?
是链表实现，通过引用来找到前面或后面的对象，所以相对来说LinkedList插入、删除操作比较快，查找较慢，是双向链表。
单调队列怎么用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如何实现一个循环队列保存另一个类的对象
这里说下我的思路。循环队列。首先你要想清楚队列。队列有多种实现方式。链表和数组。
如果是固定的个数那可以用数组实现否则用双向循环链表实现。 具体说实现方式可以参考link list或arrayDequeue
java如何实现链表
链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的示意图：
链表的数据结构
我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位，使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值，并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在当前结点前插入一个结点，并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length＋＋;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length－－;
}
return temp;
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*链表的简单应用举例*/
{
List a=new List ();
for(int i=1;i=10;i＋＋)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现：
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。
希望对你有帮助。
