您的位置:

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;

}

}