雙向鏈表實現隊列java（雙向鏈表實現隊列c語言）

本文目錄一覽：

• 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類的代碼稍加改動即可。

希望對你有幫助。