栈链式存储java实现（栈链式存储java实现什么）

发布时间：2022-11-15

本文目录一览：

  1. java多线程添加学生 用链式结构怎么写
  2. java用链表实现栈
  3. 我要用java实现一个栈，基本操作就是出栈入栈。请问如何实现效率比较高。
  4. java语言中用LinkList实现堆栈

java多线程添加学生 用链式结构怎么写

Java队列的链式存储结构及实现： 类似于使用链式结构保存线性表，也可以采用链式结构来保存队列的元素，采用链式存储结构的队列也被称为链队列。 对于链队列而言，由于程序需要从rear端添加元素，然后从front端删除元素，因此考虑对链队列增加front、rear两个引用变量，使他们分别指向链队列的头、尾两个节点。

  1. 插入队列
    对于链队列而言，插入操作的实现非常简单，只要创建一个新节点，让原rear节点的next指向新节点，再让rear指向新节点即可。
  2. 移除队列
    对于链队列而言，删除操作的实现也是非常的简单，只要将原front节点指向原front节点的next节点，当然不要忘记释放原front节点的引用。

JAVA集合中的队列：

从JDK 1.5开始，Java的集合框架提供了一个Queue接口，该接口代表了一个队列。实现该接口或者实现继承了该接口的类可以当做队列来使用。Queue里包含了6个方法，用于代表队列所包含的3个标志性方法，如下所示：

  • 插入：在rear端插入元素。
  • 移除：在front端删除元素。
  • 访问：在front端访问元素。 JDK提供的工具类非常强大，它分别代表了线性表、队列、栈三种数据结构提供了两种实现：顺序结构和链式结构。虽然LinkedList工具类的功能非常强大，既可以作为线性表来使用、又可以作为队列来使用，还可作为栈来使用，但对大部分程序而言，使用ArrayList和ArrayDeque时性能可能比LinkedList更好。

java用链表实现栈

public Object setEle(Object element) {
    Object oldElement = this.element;
    this.element = element;
    return oldElement;
}

这段代码的作用是设置节点的值，并返回旧的值。虽然看起来有些多余，但这种设计在某些场景下可以提供额外的灵活性。

public Linked() {
    nextNode = null;
    element = null;
}

可以改为：

public Linked(Object element) {
    this.element = element;
    nextNode = null;
}

我要用java实现一个栈，基本操作就是出栈入栈。请问如何实现效率比较高。

使用JDK提供的栈

import java.util.Stack;
public class UsingStack {
    public static void main(String[] args) {
        // 构造栈对象，使用类型限制，只能存储Integer数据
        Stack<Integer> s = new Stack<>();
        // 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数据
        MyStack<Integer> s = new MyStack<>();
        // 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 MyStack<T> extends Vector<T> {
    /**
     * 构造方法
     */
    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语言中用LinkList实现堆栈

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。 LinkedList数据结构是一种双向的链式结构，每一个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素，和数组的顺序存储结构（如：ArrayList）相比，插入和删除比较方便，但速度会慢一些。

栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

  • 通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
  • 当表中没有元素时称为空栈。
  • 栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

实现代码

package com.weisou.dataStruct;
import java.util.LinkedList;
@SuppressWarnings("unchecked")
public class MyStack {
    LinkedList<Object> linkList = new LinkedList<>();
    public void push(Object object) {
        linkList.addFirst(object);
    }
    public boolean isEmpty() {
        return linkList.isEmpty();
    }
    public void clear() {
        linkList.clear();
    }
    // 移除并返回此列表的第一个元素
    public Object pop() {
        if (!linkList.isEmpty())
            return linkList.removeFirst();
        return "栈内无元素";
    }
    public int getSize() {
        return linkList.size();
    }
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
    }
}

队列定义

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

  • 允许删除的一端称为队头（Front）。
  • 允许插入的一端称为队尾（Rear）。
  • 当队列中没有元素时称为空队列。
  • 队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

实现代码

package com.weisou.dataStruct;
import java.util.LinkedList;
/**
 *
 * @author gf
 * @date 2009-11-13
 */
public class MyQueue {
    LinkedList<Object> linkedList = new LinkedList<>();
    // 队尾插
    public void put(Object o) {
        linkedList.addLast(o);
    }
    // 队头取 取完并删除
    public Object get() {
        if (!linkedList.isEmpty())
            return linkedList.removeFirst();
        else
            return "";
    }
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
    public int size() {
        return linkedList.size();
    }
    public void clear() {
        linkedList.clear();
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.put(1);
        myQueue.put(2);
        myQueue.put(3);
        System.out.println(myQueue.get());
    }
}
推荐文章