1. Toy模板网首页
  2. > Toy博客

Java 数据结构篇-用链表、数组实现栈

7月前 作者：小扳 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了Java 数据结构篇-用链表、数组实现栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍  

Java 数据结构篇-用链表、数组实现栈,Java 数据结构与算法篇,数据结构,java,链表

Java 数据结构篇-用链表、数组实现栈,Java 数据结构与算法篇,数据结构,java,链表

文章目录

        1.0 栈的说明

        2.0 用链表来实现栈

        2.1 实现栈 - 入栈方法（push）

        2.2 实现栈 - 出栈（pop）

        2.3 实现栈 - 查看栈顶元素（peek）

        2.4 实现栈 - 判断是否为空栈（isEmpty）

        2.5 实现栈 - 判断是否为满栈（isFull）

        2.6 实现栈 - 重写迭代器

        2.7 用链表实现栈的完整代码

        3.0 用数组来实现栈

        3.1 实现栈 - 入栈（push）

        3.2 实现栈 - 出栈（pop）

        3.3 实现栈 - 查找栈顶元素（peek）

        3.4 实现栈 - 判断是否为空栈（isEmpty）

        3.5 实现栈 - 判断是否为满栈（isFull）

        3.6 实现栈 - 重写迭代器

        3.7 用数组实现栈的完整代码

        1.0 栈的说明

        栈是一种数据结构，它具有后进先出（LIFO）的特性，即最后入栈的元素最先出栈。栈通常可以通过数组或链表来实现。栈有两个基本操作：入栈（push）和出栈（pop）。入栈操作将元素放入栈顶，出栈操作将栈顶元素移除并返回。栈还有一个辅助操作叫做查看栈顶元素（peek），用于查看栈顶的元素但不移除它。

        2.0 用链表来实现栈

        首先，需要准备实现带哨兵的单链表，用来存放数据。把链表的头部称为栈顶，链表的尾部称为栈底，对于栈来说，只对栈顶操作，对栈底不会有任何的操作。所以该链表中需要的成员变量有 sentry 哨兵节点、 size 记录节点的数量、capacity 栈的容量。为了更好的实现相关的API，所以另外定义了一个接口。

代码如下：


public class LinkedListStack<E> implements StackInterface<E>{

    static class Node<E> {
        public E value;
        Node<E> next;

        public Node() {
        }

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private int size;
    private final int capacity;
    private final Node<E> sentry;

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
        this.sentry = new Node<>(null,null);
    }

}

        

        2.1 实现栈 - 入栈方法（push）

        用链表实现栈中，入栈就相当于在链表中进行头插节点，需要注意的是，在进行入栈的时候需要先判断是否栈满了，若栈满了，返回 false；反则，返回 true 。

代码如下：

    public boolean push(E value) {

        if (isFull()) {
            System.out.println("栈容量满了！！！");
            return false;
        }
        sentry.next = new Node<>(value,sentry.next);
        size++;
        return true;
    }

        sentry.next 所指向的就是头节点，现在头节点要换成新入栈的节点，则就是 sentry.next 指向该节点，而新入栈的节点指向原来就旧的头节点。需要注意的是，记得进行 size++ 。

        2.2 实现栈 - 出栈（pop）

        用链表实现栈中，出栈相当于头删节点，不过结束的时候需要返回该节点的值，所以先找到头节点 head = sentry.next ，然后再让哨兵节点指向头节点的下一个节点，即可将该头节点从该链表中删除掉了，sentry.next = head.next 。最后返回 head.value 。

代码如下：

    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        sentry.next = first.next;
        size--;
        return first.value;
    }

        在进行出栈操作时，需要先判断该链表是否为空，若是空链表，则返回 null ；若不是空链表，则返回该删除节点的值。还需要注意的是，每一次删除后，都需要进行 size-- 操作。

        2.3 实现栈 - 查看栈顶元素（peek）

        用链表实现栈中，查看栈顶元素相当与查找头节点，即 head =  sentry.next，因此直接返回该头节点的值即可 head.value 。

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        return first.value;
    }

        在查看栈顶元素时，也要先判断该栈是否为空栈。若为空栈，直接返回 null 。

        2.4 实现栈 - 判断是否为空栈（isEmpty）

        当且仅当 size == 0 时，则为空栈。还有一种判断的方式，就是当 sentry.next 时，也为空栈。

代码如下：

    public boolean isEmpty() {
        return size == 0;
        //return sentry.next == null;
    }

        2.5 实现栈 - 判断是否为满栈（isFull）

        用链表实现栈时，当 size == capacity 时，则为满栈。

代码如下：

    public boolean isFull() {
        return size == capacity;
    }

         2.6 实现栈 - 重写迭代器

        先实现该接口 Iterable<E> ，再重写该接口的两个方法，hasNext() 与 next() 。对于 hasNext() ，当 p != null 时，继续循环下去，p == null 时，循环结束；对于 next() ，需要进行 p = p.next，将 p 往后移一步的动作，还得需要完成每一次返回对应的数据的动作。 

代码如下：

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentry.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E key = p.value;
                p = p.next;
                return key;
            }
        };
    }

        2.7 用链表实现栈的完整代码

相关的接口：

public interface StackInterface <E>{

    /**
     * 先栈顶压入元素
     * value - 代压入值
     * 压入成功返回true,否则返回false
     */
    boolean push(E value);

    /**
     * 从栈顶弹出元素
     * 栈非空返回栈顶元素，栈为空返回 null
     */
    E pop();

    /**
     返回栈顶元素，不弹出
     栈非空返回栈顶元素，栈为空返回 null
     */
    E peek();

    /**
     * 判断栈是否为空
     * 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 判断栈是否满
     * 满返回true,否则返回false
     */
    boolean isFull();

}

用链表实现栈的代码：

import java.util.Iterator;
public class LinkedListStack<E> implements StackInterface<E>,Iterable<E>{

    static class Node<E> {
        public E value;
        Node<E> next;

        public Node() {
        }

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private int size;
    private final int capacity;
    private final Node<E> sentry;

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
        this.sentry = new Node<>(null,null);
    }


    @Override
    public boolean push(E value) {

        if (isFull()) {
            System.out.println("栈容量满了！！！");
            return false;
        }
        sentry.next = new Node<>(value,sentry.next);
        size++;
        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        sentry.next = first.next;
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = sentry.next;
        return first.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
        //return sentry.next == null;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentry.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E key = p.value;
                p = p.next;
                return key;
            }
        };
    }
}

        3.0 用数组来实现栈

        该类中的成员变量有 Object[] array 的数组，来存放数据；还有 int top ，用来记录数据的个数，当 top - 1 索引对应该位置，称为栈顶；0 索引对应的位置，称为栈底。这样的设置，提高了对栈顶操作的效率。

代码如下：

public class ArrayStack<E> {


    private int top;
    private Object[] arrayStack;

    public ArrayStack() {
    }

    public ArrayStack(int capacity) {
        arrayStack = new Object[capacity];
    }
}

        利用该类的构造方法，可以自定义初始化数组的容量。

        3.1 实现栈 - 入栈（push）

        用数组实现栈，相当与在数组 top 位置中存放数据，即 arrayStack[top] = value 。

代码如下：

 
    public boolean push(E value) {
        if (isFull()) {
            return false;
        }
        arrayStack[top++] = value;
        return true;
    }

        但是在入栈之前需要先判断该栈是否满了，若为满栈，则不能继续存放数据了。若存放数据之后，需要将 top++ 进行自加的操作。

        3.2 实现栈 - 出栈（pop）

        用数组实现栈，出栈相当于进行尾删，不过先得记录要删除的数据，将其返回即可。

代码如下：

    public E pop() {
        if (isEmpty()) {
            return null;
        }

        return (E)arrayStack[--top];
    }

        但是，在出栈之前需要先判断该栈是否为空栈。

         3.3 实现栈 - 查找栈顶元素（peek）

        用数组实现栈，查找栈顶元素相当于去查找数组 top - 1索引的值。

代码如下：

    public E peek() {
        if (top == 0) {
            return  null;
        }
        return (E) arrayStack[top - 1];
    }

        在查找栈顶元素之前，需要先判断 top 是否为 0 ，为 0 即为空，没有必要查找了。

        3.4 实现栈 - 判断是否为空栈（isEmpty）

        用数组实现栈，判断是否为空栈，就是判断 top 是否等于 0 。

代码如下：

    public boolean isEmpty() {
        return top == 0;
    }

        3.5 实现栈 - 判断是否为满栈（isFull）

        用数组实现栈，判断是否为满栈，就是判断 top 是否等于该数组的长度 arrayStack.length 。

代码如下：

    @Override
    public boolean isFull() {
        return arrayStack.length == top;
    }

        3.6 实现栈 - 重写迭代器

        先实现该接口 Iterable<E> ，再重写该接口的两个方法，hasNext() 和 next() 。对于 hasNext() ，当 top > 0 时，继续循环下去，top == 0 时，循环结束；对于 next() ，完成需要进行 top-- 的动作，还得需要完成每一次返回对应的数据的动作。 

代码如下：


    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = top;
            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public E next() {
                return (E)arrayStack[--p];
            }
        };
    }

        3.7 用数组实现栈的完整代码

接口代码：

public interface StackInterface <E>{

    /**
     * 先栈顶压入元素
     * value - 代压入值
     * 压入成功返回true,否则返回false
     */
    boolean push(E value);

    /**
     * 从栈顶弹出元素
     * 栈非空返回栈顶元素，栈为空返回 null
     */
    E pop();

    /**
     返回栈顶元素，不弹出
     栈非空返回栈顶元素，栈为空返回 null
     */
    E peek();

    /**
     * 判断栈是否为空
     * 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 判断栈是否满
     * 满返回true,否则返回false
     */
    boolean isFull();

}

用数组实现栈的代码：

import java.util.Iterator;

public class ArrayStack<E> implements StackInterface<E>,Iterable<E>{


    private int top;
    private Object[] arrayStack;

    public ArrayStack() {
    }

    public ArrayStack(int capacity) {
        arrayStack = new Object[capacity];
    }


    @Override
    public boolean push(E value) {
        if (isFull()) {
            return false;
        }
        arrayStack[top++] = value;

        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }

        return (E)arrayStack[--top];
    }

    @Override
    public E peek() {
        if (top == 0) {
            return  null;
        }
        return (E) arrayStack[top - 1];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public boolean isFull() {
        return arrayStack.length == top;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = top;
            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public E next() {
                return (E)arrayStack[--p];
            }
        };
    }
}

Java 数据结构篇-用链表、数组实现栈,Java 数据结构与算法篇,数据结构,java,链表

 文章来源地址https://www.toymoban.com/news/detail-752161.html

到了这里，关于Java 数据结构篇-用链表、数组实现栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】使用数组的结构实现链表（单向或双向）

    【数据结构和算法】使用数组的结构实现链表（单向或双向）

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现，我们或许在其他老师的教学中，只学到了用结构体的形式来实现链表、队列、栈等数据结构，本文我想告诉你的是，我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(45)
  • Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出，先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(28)

  • 数据结构——链表的实现（Java版）

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 （1）在头部添加 （2）在尾部添加 （3）在索引位置添加 （4）对头插法和尾插法代码进行简化（调用任意位置添加的方法） 7.打印链表（遍历，重写toString方

    2024年01月23日
    浏览(35)
  • 数据结构——线性数据结构（数组，链表，栈，队列）

    数据结构——线性数据结构（数组，链表，栈，队列）

    数组（Array） 是一种很常见的数据结构。它由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引（index）可以计算出该元素对应的存储地址。 数组的特点是： 提供随机访问 并且容量有限。 2.1. 链表简介 链表（LinkedList） 虽然是

    2024年02月11日
    浏览(30)
  • 数据结构（Java实现）LinkedList与链表（上）

    数据结构（Java实现）LinkedList与链表（上）

    链表 逻辑结构 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(37)
  • 数据结构（Java实现）LinkedList与链表（下）

    数据结构（Java实现）LinkedList与链表（下）

    ** ** 结论 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下： 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(31)

  • 数据结构——用Java实现数组

    数据结构是一门基础的学科，是研究数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据和修改数据的。 1.线性结构：数组、队列、栈、链表、哈希表… 2.树形结构：二叉树、二分搜索树、AVL树，红黑树、堆、Trie、线段树、并查集… 3.图结构：邻接矩阵、邻接

    2024年01月18日
    浏览(32)
  • 【数据结构与算法——TypeScript】数组、栈、队列、链表

    【数据结构与算法——TypeScript】数组、栈、队列、链表

    解决问题 的过程中，不仅仅 数据的存储方式会影响效率，算法的优劣也会影响效率 什么是算法？ 定义： 🟢 一个有限指令集，每条指令的描述不依赖于言语 （编写指令：java/c++/ts/js） 🟢 接收一些输入（有些情况下不需要输入）（接收：排序：无序数组） 🟢 产生输出 （

    2024年02月14日
    浏览(26)
  • 【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）

    【数据结构与算法】1、学习动态数组数据结构（基本模拟实现 Java 的 ArrayList 实现增删改查）

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表（数组、链表、栈、队列、哈希表） 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 （n = 0） a1 是首节点

    2024年02月10日
    浏览(60)
  • Java 数据结构篇-用数组、堆实现优先级队列

    Java 数据结构篇-用数组、堆实现优先级队列

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 优先级队列说明         2.0 用数组实现优先级队列         3.0 无序数组实现优先级队列         3.1 无序数组实现优先级队列 - 入队列 offer(E value)         3.2 无序数组实现优先

    2024年02月04日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包