精华内容
下载资源
问答
  • 1、用链表实现栈package stack;/**** @author denghb**/class Link {public long dData;public Link next;public Link(long dd) {dData = dd;}public void displayLink() {System.out.print(dData + " ");}}class ...

    1、用链表实现栈

    package stack;

    /**

    *

    * @author denghb

    *

    */

    class Link {

    public long dData;

    public Link next;

    public Link(long dd) {

    dData = dd;

    }

    public void displayLink() {

    System.out.print(dData + " ");

    }

    }

    class LinkList {

    private Link first;

    public LinkList() {

    first = null;

    }

    public boolean isEmpty() {

    return (first == null);

    }

    public void insertFirst(long dd) {

    Link newLink = new Link(dd);

    newLink.next = first;

    first = newLink;

    }

    public long deleteFirst() {

    //如果这是一个非空链表

    Link temp = first;

    first = first.next;

    return temp.dData;

    }

    public void displayList() {

    Link current = first;

    while(current != null) {

    current.displayLink();

    current = current.next;

    }

    System.out.println("");

    }

    }

    class LinkStack {

    private LinkList theList;

    public LinkStack() {

    theList = new LinkList();

    }

    public void push(long j) {

    theList.insertFirst(j);

    }

    public long pop() {

    return theList.deleteFirst();

    }

    public boolean isEmpty() {

    return (theList.isEmpty());

    }

    public void displayStack() {

    System.out.print("Stack (top-->bottom): ");

    theList.displayList();

    }

    }

    public class LinkStackApp {

    public static void main(String[] args) {

    LinkStack theStack = new LinkStack();

    theStack.push(20);

    theStack.push(40);

    theStack.displayStack();

    theStack.push(60);

    theStack.push(80);

    theStack.displayStack();

    theStack.pop();

    theStack.pop();

    theStack.displayStack();

    }

    }

    2、用链表实现队列

    package queue;

    /**

    *

    * @author denghb

    *

    */

    class Link {

    public long dData;

    public Link next;

    public Link(long dd) {

    dData = dd;

    }

    public void displayLink() {

    System.out.print(dData + " ");

    }

    }

    class FirstLastList {

    private Link first;

    private Link last;

    public FirstLastList() {

    first = null;

    last = null;

    }

    public boolean isEmpty() {

    return (first == null);

    }

    public void insertLast(long dd) {

    Link newLink = new Link(dd);

    if(isEmpty()) {

    first = newLink;

    } else {

    last.next = newLink;

    }

    last = newLink;

    }

    public long deleteFirst() {

    //如果这是一个非空链表

    long temp = first.dData;

    if(first.next == null) { //如果仅仅有一个链接点

    last = null;

    }

    first = first.next;

    return temp;

    }

    public void displayList() {

    Link current = first;

    while(current != null) {

    current.displayLink();

    current = current.next;

    }

    System.out.println("");

    }

    }

    class LinkQueue {

    private FirstLastList theList;

    public LinkQueue() {

    theList = new FirstLastList();

    }

    public void insert(long j) {

    theList.insertLast(j);

    }

    public long remove() {

    return theList.deleteFirst();

    }

    public boolean isEmpty() {

    return (theList.isEmpty());

    }

    public void displayStack() {

    System.out.print("Stack (top-->bottom): ");

    theList.displayList();

    }

    }

    public class LinkQueueApp {

    public static void main(String[] args) {

    LinkQueue theQueue = new LinkQueue();

    theQueue.insert(20);

    theQueue.insert(40);

    theQueue.displayStack();

    theQueue.insert(60);

    theQueue.insert(80);

    theQueue.displayStack();

    theQueue.remove();

    theQueue.remove();

    theQueue.displayStack();

    }

    }

    第一个源程序的输出结果:

    Stack (top-->bottom): 40 20

    Stack (top-->bottom): 80 60 40 20

    Stack (top-->bottom): 40 20

    第二个源程序的输出结果:

    Stack (top-->bottom): 20 40

    Stack (top-->bottom): 20 40 60 80

    Stack (top-->bottom): 60 80

    展开全文
  • 承接上文,今天我们来用链表实现栈和队列。先看栈,我们使用链表的头部作为栈顶,链表的尾部作为栈底。实现比较简单,直接上代码:@Override 代码基于LinkedList来实现,那么getSize(),isEmpty()等的操作就不提了...

    f12ecd44c38f2dfc60da1a49a03c9324.png

    关注公众号:EZ大数据(ID:EZ_DATA)。每天进步一点点,感觉很爽!

    承接上文,今天我们来用链表实现栈和队列。

    先看栈,我们使用链表的头部作为栈顶,链表的尾部作为栈底。实现比较简单,直接上代码:

    @Override
        

    代码基于LinkedList来实现,那么getSize(),isEmpty()等的操作就不提了。

    接下来,我们来测试下基于数组实现的栈和基于链表实现的栈的区别:

    public 

    我们随机在栈中插入1000000个数字,并取出元素,那么测试结果如下:

    arrayStack, time: 0.4852778s2
    linkedListStack, time: 2.5215067s
    

    其实这个时间比较很复杂,因为LinkedListStack中包含更多的new操作(node),需要不停的在内存中寻找地方开辟空间,当数量越多,耗时越长。实际上不管是arrayStack还是linkedListStack在我们的测试中,他们的时间复杂度都是一样的。
    现在我们来看用链表来实现队列。
    对于链表来说,头部节点head的操作是O(1),如果想实现队列,那么我们需要定义个尾部节点tail,记录最后一个元素的位置。同时,上篇文章我们说过链表的头部节点添加元素还是删除元素都是O(1),那么我们如何定义队首队尾的位置呢?

    b5ddc8fc7697bc6ee44142f805672bed.png

    如上图所示,我们使用tail来记录链表尾部元素位置,此时我们在tail端添加元素就变为O(1),但是当我们删除元素时,因为必须知道前一个元素的节点,所以需要遍历整个链表,此时就变的比较复杂。而我们在head端,无论是添加元素还是删除元素,时间复杂度都是O(1),那么我们就可以把head端作为队首出队,把tail端作为队尾入队,也就是从head端删除元素,从tail端插入元素。
    同时呢,由于没有dummyhead,那么需要注意链表为空时的情况,此时head和tail都指向同一位置。
    下面我们来用链表实现队列。

    private 

    队列实现完毕,我们来测试一波arrayQueue,loopQueue和linkedListQueue的运行效率。测试代码如下:

    // 测试使用q运行opCount个enqueue和dequeue操作所需的时间,单位:秒
    

    我们在队列中插入100000个数字,并取出。测试时间如下:

    ArrayQueue, time: 2.8499096s
    LoopQueue, time: 0.0099262s
    linkedListQueue, time: 0.0128844s
    

    由于arrayQueue出队操作时间复杂度是O(n),而loopQueue和linkedListQueue时间复杂度都是O(1),所以arrayQueue的时间消耗最多,然后linkedListQueue是基于链表来实现的,在操作的过程中,需要new出很多节点,加之各种原因(系统因素,元素数量等)的影响,所以时间会略有不同。
    好了,今天我们用链表来实现了栈和队列,也算是巩固了之前学的知识。经过这几天的总结,相信大家对于数组、栈、队列、链表的认识更加深刻。后续呢,我们会尽可能每天刷点题,提升自己的代码能力。
    OK,拜了个拜~

    展开全文
  • 1、用链表实现栈package stack;/**** @author denghb**/class Link {public long dData;public Link next;public Link(long dd) {dData = dd;}public void displayLink() {System.out.print(dData + " ");}}class ...

    1、用链表实现栈

    package stack;

    /**

    *

    * @author denghb

    *

    */

    class Link {

    public long dData;

    public Link next;

    public Link(long dd) {

    dData = dd;

    }

    public void displayLink() {

    System.out.print(dData + " ");

    }

    }

    class LinkList {

    private Link first;

    public LinkList() {

    first = null;

    }

    public boolean isEmpty() {

    return (first == null);

    }

    public void insertFirst(long dd) {

    Link newLink = new Link(dd);

    newLink.next = first;

    first = newLink;

    }

    public long deleteFirst() {

    //假设这是一个非空链表

    Link temp = first;

    first = first.next;

    return temp.dData;

    }

    public void displayList() {

    Link current = first;

    while(current != null) {

    current.displayLink();

    current = current.next;

    }

    System.out.println("");

    }

    }

    class LinkStack {

    private LinkList theList;

    public LinkStack() {

    theList = new LinkList();

    }

    public void push(long j) {

    theList.insertFirst(j);

    }

    public long pop() {

    return theList.deleteFirst();

    }

    public boolean isEmpty() {

    return (theList.isEmpty());

    }

    public void displayStack() {

    System.out.print("Stack (top-->bottom): ");

    theList.displayList();

    }

    }

    public class LinkStackApp {

    public static void main(String[] args) {

    LinkStack theStack = new LinkStack();

    theStack.push(20);

    theStack.push(40);

    theStack.displayStack();

    theStack.push(60);

    theStack.push(80);

    theStack.displayStack();

    theStack.pop();

    theStack.pop();

    theStack.displayStack();

    }

    }

    2、用链表实现队列

    package queue;

    /**

    *

    * @author denghb

    *

    */

    class Link {

    public long dData;

    public Link next;

    public Link(long dd) {

    dData = dd;

    }

    public void displayLink() {

    System.out.print(dData + " ");

    }

    }

    class FirstLastList {

    private Link first;

    private Link last;

    public FirstLastList() {

    first = null;

    last = null;

    }

    public boolean isEmpty() {

    return (first == null);

    }

    public void insertLast(long dd) {

    Link newLink = new Link(dd);

    if(isEmpty()) {

    first = newLink;

    } else {

    last.next = newLink;

    }

    last = newLink;

    }

    public long deleteFirst() {

    //假设这是一个非空链表

    long temp = first.dData;

    if(first.next == null) { //如果只有一个链接点

    last = null;

    }

    first = first.next;

    return temp;

    }

    public void displayList() {

    Link current = first;

    while(current != null) {

    current.displayLink();

    current = current.next;

    }

    System.out.println("");

    }

    }

    class LinkQueue {

    private FirstLastList theList;

    public LinkQueue() {

    theList = new FirstLastList();

    }

    public void insert(long j) {

    theList.insertLast(j);

    }

    public long remove() {

    return theList.deleteFirst();

    }

    public boolean isEmpty() {

    return (theList.isEmpty());

    }

    public void displayStack() {

    System.out.print("Stack (top-->bottom): ");

    theList.displayList();

    }

    }

    public class LinkQueueApp {

    public static void main(String[] args) {

    LinkQueue theQueue = new LinkQueue();

    theQueue.insert(20);

    theQueue.insert(40);

    theQueue.displayStack();

    theQueue.insert(60);

    theQueue.insert(80);

    theQueue.displayStack();

    theQueue.remove();

    theQueue.remove();

    theQueue.displayStack();

    }

    }

    第一个源程序的输出结果:

    Stack (top-->bottom): 40 20

    Stack (top-->bottom): 80 60 40 20

    Stack (top-->bottom): 40 20

    第二个源程序的输出结果:

    Stack (top-->bottom): 20 40  Stack (top-->bottom): 20 40 60 80  Stack (top-->bottom): 60 80

    展开全文
  • * 用链表实现栈 * @author Administrator * * @param <E> */ public class MyStackLink<E> { //定义一个初始长度为0的数组来缓存数据 Node head = null; ...

        用链表实现了栈的基本操作:入栈、出栈、查看栈顶数据以及判断栈是否有数据

    /**
     * 用链表实现栈
     * @author Administrator
     *
     * @param <E>
     */
    
    
    public class MyStackLink<E>
    {
    	//定义一个初始长度为0的数组来缓存数据
    		Node head = null;
    		int length = 0;//结点个数
    		
    		
    		//将数据压入栈中
    		public void push(E e)
    		{
    			//创建结点
    			Node n = new Node(e);
    			n.next=head;
    			head=n;
    			length++;
    			
    		}
    		//查看栈顶的数据
    		public E get()
    		{
    			
    //			return head == null?null:head.e;
    			return head.e;
    		}
    		
    		//出栈
    		public E poll()
    		{ 
    			if(head==null)
    			{
    				return null;
    			}
    			Node n=head;
    			head = n.next;
    			n.next=null;
    			length--;
    			return n.e;
    		}
    		
    		//判断栈是否为空
    		public boolean isEmpty()
    		{
    			return length == 0;
    		}
    		private class Node
    		{
    			E e;
    			Node next;
    			public Node(E e)
    			{
    				this.e = e;
    			}
    		}
    }
    

         因为代码和功能基本上差不多就在这里一起用链表实现了队列

     

    /**
     * 用链表实现队列
     * @author Administrator
     *
     * @param <E>
     */
    
    
    public class Queue<E>
    {
    
    			Node head = null;
    			private Node last = null;
    			int length = 0;//结点个数
    			
    			//将数据放入队列中
    			public void push(E e)
    			{
    				//创建结点
    				Node n = new Node(e);
    				if(head==null)
    				{
    					head = n;
    				}else
    				{
    					last.next = n;
    				}
    				last = n;
    				length++;
    				
    			}
    			//查看队列的数据
    			public E get()
    			{
    				
    				return head == null?null:head.e;
    			}
    			
    			//去队列的首数据
    			public E poll()
    			{ 
    				if(head==null)
    				{
    					return null;
    				}
    				Node n=head;
    				head = n.next;
    				n.next=null;
    				length--;
    				return n.e;
    
    			}
    			
    			//判断队列是否为空
    			public boolean isEmpty()
    			{
    				return length == 0;
    			}
    			private class Node
    			{
    				E e;
    				Node next;
    				public Node(E e)
    				{
    					this.e = e;
    				}
    			}
    }
    
     

     

     

    展开全文
  • 1.链表 1.概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的引用...2.java实现链表 public class LinkedArray<T> { //内部类 private class Node<T>{ T ele;
  • 实现 // 的基本方法 public interface Stack&lt;E&gt; { void push(E e); E pop(); E peek();...// 链表的基本方法的实现 public class LinkedList&lt;E&gt; { p...
  • :一种特殊的线性表,其只允许在固定的一端进行插入删除元素操作。进行数据插入删除操作的一端称为栈顶,另一端称为底。中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:的插入操作...
  • 上篇博客和大家分享了java链表实现,这篇博客将和大家一起分享基于链表的栈和队列。这里可以先回忆一下基于动态数组实现的栈和队列,无论是底层是链表还是动态数组,栈和队列的接口都是一致的。 首先,我们一起来...
  • 双端链表: 双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear 这样在链尾插入会变得非常容易,只需改变rear的next为新增的结点即可,而不需要循环搜索到最后一个节点 所以有insertFirst...
  • 链表实现栈和队列

    2019-09-08 12:01:00
    一、我们知道在Java中是没有指针的,那么如何在Java中创建链表呢,自我感觉比C++的好理解,Java中用类创建一个包括数据与next的类的引用就可以了。 1.首先是一个基本链表节点类的创建 public class Link { ...
  • 一、链表实现栈 1.链表代码 ... 2.链表实现栈java代码 (1)stack接口 public interface stack&lt;E&gt; { int getSize(); //获得元素个数 bo...
  • 数组和链表的对比 数组:最好用于索引有语义的情况,支持快速查询 链表:不适合用于索引有语义的情况,动态。 内部类Node public class LinkedList<E>{ private class Node{ public E e; pu
  • 链表的优点在于对表头元素的插入删除复杂度很低,所以对于链表实现复杂度很低。 链表的代码 /** * @Author: Cui * @Date: 2020/7/9 * @Description: */ public class LinkedList<E> { private ...
  • 链表---使用链表实现栈和队列

    千次阅读 2018-08-01 23:34:15
    Java中,链表实现非常简单,每个节点Node都有一个值val指向下个节点的链接next。 节点的定义: class Node {  int val;  Node next;  Node(int x) {  val = x;  next = null;  } } 实现: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,031
精华内容 412
关键字:

java链表实现栈和队列

java 订阅