java鏈表實現堆棧思想,定義一個棧,要求用鏈表實現

本文目錄一覽：

• 1、關於JAVA數據結構堆棧用鏈表實現的問題 想問問入棧代碼的作用就是代碼功能怎麼實現的 不要把思
• 2、java怎麼用鏈表實現
• 3、我要用java實現一個棧，基本操作就是出棧入棧。請問如何實現效率比較高。
• 4、java用鏈表實現棧
• 5、Java鏈表
• 6、java 中用雙向鏈表模擬棧

關於JAVA數據結構堆棧用鏈表實現的問題 想問問入棧代碼的作用就是代碼功能怎麼實現的 不要把思

晚上3點還在學習，你也真是蠻拼的。

不知道你Node的代碼是怎樣的，getNext和setNext方法具體內容。姑且按你說的，head為null，Next為下一Node節點來說吧。(其實我覺得setNext應該是set data的值才對，不是Next。不過沒所謂了。按你假設的來說吧)

初始化時，MyLinkedStack中的head如下：head.data=null, head.next=null;

然後第一次入棧，倒數第三行時，n如下：n.data=data, n.next=null;

倒數第二行的head鏈如下：head.data=null, head.next=n;

若是有再次入棧，我設Node對象為n1，然後數據為data1吧。那n1新建的時候也是：n1.data=data1, n1.next=null;

倒數第三行的n1如下：n1.data=data1, n1.next=n;

倒數第二行的head鏈如下：head.data=null, head.next=n1, n1.next=n;

當然，這是不知道你getNext和setNext具體代碼的情況下，我覺得是head.data=n1, head.next=n;這樣才好的。重點來了：棧是後進先出的。

java怎麼用鏈表實現

在數據結構中經常看見的一個基本概念-鏈表。

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

在Java中，對於鏈表的實現都是基於引用數據類型操作的。實現大致如下：

定義節點類Node，節點的概念很重要，一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用，再增加一個添加節點的方法即可完成鏈表實現。

鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。在執行效率上，相比數組而言，鏈表插入快查找慢，開發中得根據實際業務使用。

我要用java實現一個棧，基本操作就是出棧入棧。請問如何實現效率比較高。

//這是JDK提供的棧

import java.util.Stack;

public class UsingStack {

public static void main(String[] args) {

//構造棧對象，使用類型限制，只能存儲Integer數據

StackInteger s = new StackInteger();

//1、2、3依次入棧

s.push(1);

s.push(2);

s.push(3);

//3、2、1依次出棧

System.out.println(s.pop());

System.out.println(s.pop());

System.out.println(s.pop());

}

}

//這是我寫的順序結構的棧

import java.util.EmptyStackException;

import java.util.Vector;

public class UsingStack{

public static void main(String[] args){

//構造棧對象，使用類型限制，只能存儲Integer數據

MyStackInteger s = new MyStackInteger();

//1、2、3依次入棧

s.push(1);

s.push(2);

s.push(3);

//3、2、1依次出棧

System.out.println(s.pop());

System.out.println(s.pop());

System.out.println(s.pop());

}

}

/**

* 棧類

* @author developer_05

* @param T

*/

class MyStackT extends VectorT{

/**

* 構造方法

*/

public MyStack(){

}

/**

* 入棧方法

* @param item 待入棧的元素

* @return 返回入棧的元素

*/

public T push(T item) {

addElement(item);

return item;

}

/**

* 出棧方法(同步處理)

* @return 返回出棧元素

*/

public synchronized T pop() {

T obj;

int len = size();

if (len == 0)

throw new EmptyStackException();

obj = elementAt(len – 1);

removeElementAt(len – 1);

return obj;

}

/**

* 判斷棧是否為空的方法

* @return 返回true(棧空)或false(棧非空)

*/

public boolean empty() {

return size() == 0;

}

private static final long serialVersionUID = 1L;

}

java用鏈表實現棧

public Object setEle(Object element)

{

Object oldElement = this.element;

this.element = element;

return oldElement;

}

是啥意思，給值還return？？把這函數刪了

public Linked()

{

nextNode = null;

element = null;

}

改成

public Linked(Object element)

{

this.element = element;

nextNode = null;

}

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

如果對您有幫助，請記得採納為滿意答案，謝謝！祝您生活愉快！

vaela

java 中用雙向鏈表模擬棧

這裡只是實現了Stack的部分功能

public class Stack{

private Node top;

public Stack(){

this.top = null;

}

public void push(Node node){

if(node == null)

return;

if(this.top == null){

this.top = node;

node.setNext(null);

node.setPre(null);

}

else{

this.top.setNext(node);

node.setPre(this.top);

node.setNext(null);

this.top = node;

}

}

public Node pop(){

if(this.top == null)

return null;

Node curr = this.top;

Node pre = curr.getPre();

pre.setNext(null);

this.top = pre;

return curr;

}

public Node top(){

return this.top;

}

public boolean isEmpty(){

return this.top == null ? true : false;

}

public void empty(){

this.top = null;

}

public static void main(String[] args){

Stack stack = new Stack();

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

System.out.println(stack.isEmpty());

stack.push(n1);

System.out.println(stack.top().getValue());

stack.push(n2);

stack.push(n3);

System.out.println(stack.pop().getValue());

stack.empty();

}

}

class Node {

private int value;

private Node next;

private Node pre;

public Node(int value, Node next, Node pre){

this.value = value;

this.next = next;

this.pre = pre;

}

public Node(int value){

this.value = value;

this.next = null;

this.pre = null;

}

public int getValue() {

return value;

}

public void setValue(int value) {

this.value = value;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

public Node getPre() {

return pre;

}

public void setPre(Node pre) {

this.pre = pre;

}

}