Java基于链表实现栈的方法详解

2024-10-20 16:45:40

本文实例讲述了Java基于链表实现栈的方法。分享给大家供大家参考，具体如下：

在上几小节中我们实现了基本的链表结构，并在上一节的底部给出了有关链表的源码，此处在贴一次吧，猛戳

在开始栈的实现之前，我们再来看看关于链表的只在头部进行的增加、删除、查找操作，时间复杂度均为O(1)，基于链表的这几个优势，我们在此基础上实现栈。

前言，在写本小节之前，我们已经实现了一个基于静态数组的栈，转到查看。此处我们实现基于链表的栈。

1.链表类拷贝到Stack 包下：

在实现基于静态数组的栈的时候，我们已经新建了一个package，此时我们将已经实现的链表类拷贝到该package下，目录结构为：

2.实现栈

新建一个LinkedListStack类，实现Stack接口，相关代码如下：

Stack接口:

package Stack;

public interface Stack<E> {

  //栈中元素个数
  int getSize();

  //栈中元素个数是否为空
  boolean isEmpty();

  //进栈
  void push(E e);

  //出栈
  E pop();

  //查看栈顶元素
  E peek();
}

个LinkedListStack类:

package Stack;

public class LinkedListStack<E> implements Stack<E> {
  private LinkedList<E> list;

  public LinkedListStack() {
    list = new LinkedList<E>();
  }

  //栈中元素个数
  @Override
  public int getSize() {
    return list.getSize();
  }

  //栈中是否为空
  @Override
  public boolean isEmpty() {
    return list.isEmpty();
  }

  //在栈中添加元素
  @Override
  public void push(E e) {
    list.addFirst(e);
  }

  //从栈中删除第一个元素
  @Override
  public E pop() {
    return list.removeFirst();
  }

  //查看栈中第一个元素
  @Override
  public E peek() {
    return list.getFirst();
  }

  //主要是便于输出给对象信息
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Stack: top ");
    res.append(list);
    return res.toString();
  }

}

3.添加测试代码

为了测试的简单，我们在已经实现了Stack接口的LinkedListStack类中建立以main()方法，main中代码如下：

  //测试
  public static void main(String[] args) {
    LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
      System.out.println(stack);
    }
    System.out.println("出栈一个元素：");
    stack.pop();
    System.out.println(stack);
  }

结果为：

到此我们实现了底层是链表的栈。

关于本小节，若您觉得还行、还过得去，记得给个推荐哦~，谢谢！！

本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Stack/LinkedListStack.java

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

Java中双向链表详解及实例

Java中双向链表详解及实例写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin
JAVA实现链表面试题

这份笔记整理了整整一个星期,每一行代码都是自己默写完成,并测试运行成功,同时也回顾了一下<剑指offer>这本书中和链表有关的讲解,希望对笔试和面试有所帮助. 本文包含链表的以下内容: 1.单链表的创建和遍历 2.求单链表中节点的个数 3.查找单链表中的倒数第k个结点(剑指offer,题15) 4.查找单链表中的中间结点 5.合并两个有序的单链表,合并之后的链表依然有序[出现频率高](剑指offer,题17) 6.单链表的反转[出现频率最高](剑指offer,题16) 7.从尾到头打印单链表(
java使用数组和链表实现队列示例

(1)用数组实现的队列: 复制代码代码如下: //先自己定义一个接口 public interface NetJavaList { public void add(Student t); //继承该接口的类必须实现的方法 public Student get(int index);//队列的加入,取出,队列的大小 public int size(); } 定义一个学生类复制代码代码如下: class Student { private String na
Java实现单链表翻转实例代码

Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node
java使用链表来模拟栈的入栈出栈操作实例代码

栈:后进先出:最后一个放入堆栈中的物体总是被最先拿出来. 使用链表来模拟栈的入栈出栈操作. 1.节点类代码 public class Entry<T> { private T value; private Entry<T> next; public Entry() { this(null); } public Entry(T value) { this.value=value; this.next=null; } public void setValue(T value) { th
java双向循环链表的实现代码

例1: 复制代码代码如下: package com.xlst.util; import java.util.HashMap;import java.util.Map;import java.util.UUID; /*** 双向循环链表* 完成时间:2012.9.28* 版本1.0* @author xlst**/public class BothwayLoopLinked {/*** 存放链表长度的 map* * 如果简单使用 static int 型的 size 基本类型变量,则只能维护一个
java中stack(栈)的使用代码实例

java中stack类继承于vector,其特性为后进先出(lastinfirstout). 入栈和出栈实例图: 实例图的java代码实例: package com.lanhuigu.java.ListTest; import java.util.Stack; public class StackTest { public static void main(String[] args) { Stack<String> staffs = new Stack<String>(); //
java 中链表的定义与使用方法

java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my
Java数据结构之链表、栈、队列、树的实现方法示例

本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth
Java单链表基本操作的实现

最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵
Java中堆和栈的区别详解

当一个人开始学习Java或者其他编程语言的时候,会接触到堆和栈,由于一开始没有明确清晰的说明解释,很多人会产生很多疑问,什么是堆,什么是栈,堆和栈有什么区别?更糟糕的是,Java中存在栈这样一个后进先出(Last In First Out)的顺序的数据结构,这就是java.util.Stack.这种情况下,不免让很多人更加费解前面的问题.事实上,堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存.众所周知,所有的Java程序都运行在JVM虚拟机内部,我们这里介绍的自然
java实现单链表中是否有环的方法详解

这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇
java数据结构之实现双向链表的示例

复制代码代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{ Node<T> perv; //前节点 Node<T> next; //后节点 T data; //数据 public Node(T t){ this.data = t; } } priv

Java基于链表实现栈的方法详解

相关推荐

随机推荐