Java版-数据结构-栈

voidking 发布于2019-08-16 16:10 / 1608人阅读

摘要：介绍栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。

介绍

栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。栈，只有两种操作，分为入栈（压栈）和出栈（退栈）；向栈中添加元素的操作叫做入栈，相反从栈中删除元素叫做出栈。

特点

只能从栈顶添加元素或者删除元素

后进先出的数据结构，Last In First Out（LIFO）

为了大家更好的形象了解我们通过示意图来看一下栈的入栈和出栈操作

入栈操作示意图

出栈操作示意图（后进的元素先出）

栈的基本操作

向栈中添加一个元素（入栈）

void push(E e)

从栈中删除一个元素（出栈）

E pop()

查看栈顶元素

E peek()

查看栈中元素个数

int getSize()

判断栈是否为空

boolean isEmpty()

实现栈的方式，实际上底层有多种实现方式，比如：动态数组等，这里我们使用Java语言本身为我们提供的集合LinkedList

接口定义：Stack

public interface Stack {

    /**
     * 向栈中添加元素
     *
     * @param e
     */
    void push(E e);

    /**
     * 从栈中删除元素
     */
    void pop();

    /**
     * 获取栈顶元素
     *
     * @return
     */
    E peek();

    /**
     * 获取栈中元素个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断栈中是否为空
     *
     * @return
     */
    boolean isEmpty();

}

LinkedListStack 类实现接口Stack

public class LinkedListStack implements Stack {
    /**
     * 存放栈元素
     */
    LinkedList list;

    /**
     * 构造栈结构
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(E e) {
        list.addLast(e);
    }

    @Override
    public void pop() {
        list.removeLast();
    }

    @Override
    public E peek() {
        return list.getLast();
    }

    @Override
    public int getSize() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        return "LinkedListStack{" +
                "list=" + list +
                "}";
    }
}

测试类：LinkedListStackTest

@Test
public void testLinkedListStack() {
    // 栈
    Stack stack = new LinkedListStack<>();
    // 准备入栈元素
    List prepareElements = Arrays.asList("A", "B", "C", "D", "E");
    // 入栈
    prepareElements.forEach(x -> {
        stack.push(x);
        System.out.println("入栈操作：" + stack);
    });
    // 出栈
    stack.pop();
    System.out.println("出栈操作：" + stack);
    // 获取栈顶元素
    String peekElement = stack.peek();
    System.out.println("栈顶元素：" + peekElement);
    // 获取栈中元素的个数
    int stackSize = stack.getSize();
    System.out.println("栈中元素个数：" + stackSize);
}

运行结果

入栈操作：LinkedListStack{list=[A]}
入栈操作：LinkedListStack{list=[A, B]}
入栈操作：LinkedListStack{list=[A, B, C]}
入栈操作：LinkedListStack{list=[A, B, C, D]}
入栈操作：LinkedListStack{list=[A, B, C, D, E]}
出栈操作：LinkedListStack{list=[A, B, C, D]}
栈顶元素：D
栈中元素个数：4

栈的应用

虚拟机栈的入栈和出栈操作

在Java虚拟机运行时数据区有一块被称之为：虚拟机栈，它是线程私有的，声明周期与线程相同。

我们编写的每个Java方法，每个方法都会在执行的时候同时都会创建一个栈帧（Stack Frame）用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应这一个栈帧在虚拟机栈中入栈到出栈的过程。

现在我们假设有A、B、C三个方法，在A方法中调用B方法（A->B），在B方法中调用C方法（B->C），C方法执行本方法业务逻辑。

当程序执行到A()方法的中的第二行时，此时程序会中断A()方法并开始调用B()方法，然后会在虚拟机栈中记录调用B()方法的栈帧，我这里暂且称之为A2（实际存储的并不是O(∩_∩)O哈！）示意图如下：

同理，当程序执行到B()方法中第二行时，此时程序也会中断B()方法开始调用C()方法，然后同样地会在虚拟机栈中生成调用C()方法的栈帧并记录，我这里暂且称之为B2，示意图如下：

当程序开始执行到C()方法时，直到执行完C()方法时，这时候，程序该如何执行呢？

此时就要查看一下虚拟机栈了，发现虚拟机栈，栈中栈顶的元素是B2，我们的程序就知道了，它是执行到B()方法的B2位置就中断了，去执行C()方法了；现在C()方法执行完成之后，它就可以跳回到B2的位置继续执行了，当B()方法执行完之后，虚拟机栈中的B2栈帧也就可以出栈了，依次类推....

如果一个方法，使用递归调用，若递归临界点判断有误，则方法就会一直的被进行入栈操作，如果超过虚拟机栈的默认容量大小，则会出现我们常见的 StackOverflowError 异常

完整版代码GitHub仓库地址：Java版数据结构-栈欢迎大家【关注】和【Star】

本次我们完成的是基于Java自身自带的集合LinkedList来实现栈，有兴趣的童鞋，可以使用动态数组方式来实现；接下来，笔者还会一一的实现其它常见的数组结构。

静态数组

动态数组

栈

队列

链表

循环链表

二分搜索树

优先队列

堆

线段树

字典树

AVL

红黑树

哈希表

....

持续更新中，欢迎大家关注公众号：小白程序之路（whiteontheroad），第一时间获取最新信息！！！

笔者博客地址：http:www.gulj.cn

云服务器 GPU云服务器 c语言版数据结构栈设计栈java java单调栈 java线程栈

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73943.html

Java版-数据结构-队列（数组队列）

摘要：队列的操作方式和栈类似，唯一的区别在于队列只允许新数据在后端进行添加。前言看过笔者前两篇介绍的Java版数据结构数组和栈的盆友，都给予了笔者一致的好评，在这里笔者感谢大家的认可！！！由于本章介绍的数据结构是队列，在队列的实现上会基于前面写的动态数组来实现，而队列又和栈不论是从特点上和操作上都有类似之处，所以在这里对这两种数据结构不了解的朋友，可以去看一下笔者前两篇文章介绍的数据结...

khs1994 2019-08-16 16:10 评论0 收藏0
屌炸天，Oracle 发布了一个全栈虚拟机 GraalVM，支持 Python！

摘要：前阵子，发布了一个黑科技，号称是一个全新的通用全栈虚拟机，并具有高性能跨语言交互等逆天特性，真有这么神奇简介是一个跨语言的通用虚拟机，不仅支持了等基于的语言，以及等基于的语言，还支持其他像和语言等。原生镜像加速来看这段代码，同样来自官网。前阵子，Oracle 发布了一个黑科技 GraalVM，号称是一个全新的通用全栈虚拟机，并具有高性能、跨语言交互等逆天特性，真有这么神奇？ Graa...

hiYoHoo 2019-08-19 10:49 评论0 收藏0
数据结构之栈（java版）

摘要：本文力求简洁，只包含基础的栈功能，不想将大片的代码展示出来，让读者兴趣索然，阅读起来也十分费力，如有需要可以自行添加相关功能比如包中的类包含的，等等函数能力有限，有误之处还请不吝赐教定义内部类用于存储栈元素指向下一个栈元素的泛型元素方法方法本文力求简洁，只包含基础的栈功能，不想将大片的代码展示出来，让读者兴趣索然，阅读起来也十分费力，如有需要可以自行添加相关功能比如java.util...

hizengzeng 2019-08-14 18:03 评论0 收藏0
《JavaScript快速全栈开发》作者Azat Mardanov：现在是拥抱Node技术栈的最佳时

摘要：长期以来，他都是和等机构的讲师，其技术课程获得一致好评。但是，如果让我预测的话，我认为未来是很光明的，而现在就是拥抱技术栈的最佳时机。所以在浏览器和服务器之间代码不需要上下文切换。如果没有上下文切换，那么生产力也会更高。非商业转载请注明作译者、出处，并保留本文的原始链接：http://www.ituring.com.cn/article/195742 Azat Mardan...

Rango 2019-08-21 10:28 评论0 收藏0