动图演示：手撸堆栈的两种实现方法！

2020-09-23 11:31:53 浏览数 (34)

文章来源于公众号：Java中文社群 作者：磊哥

随着软件开发行业竞争的日益激烈，面试的难度也在逐渐增加，因为企业要从众多的面试人中选出最优秀的人，只能提高面试的难度，而算法和数据结构比较烧脑的硬核技能之一，自然也就成了面试的首选科目。并且随着时间的推移，算法和数据结构出现的频率和占比也会不断增加，因此为了顺应时代发展的潮流，我们也要做一些调整，所以在后面的一些文章中，我会陆续更新一些关于算法和数据结构的文章，希望大家能够喜欢。

PS：当然随着智能系统的普及（如今日头条和抖音），算法和数据结构在企业中应用也越来越多，因此学习算法和数据结构也是迫在眉睫的事了。

栈定义

栈（Stack）又叫堆栈（简称栈），它是在同一端进行插入和删除数据的线性表。

栈是最基础也是最常见的数据结构之一，它的数据结构和操作流程如下图所示：

栈的数据结构和操作流程

其中，允许进行插入和删除的一端叫作栈顶（Top），另一端叫作栈底（Bottom），栈底固定，栈顶浮动。

当栈中的元素为零时，该栈叫作空栈。添加数据时一般叫作入栈或进栈（Push），删除数据叫作出栈或退栈（Pop）。栈是后进先出（Last In First Out，LIFO）的线性表。

栈是后进先出的线性表

物理结构 & 逻辑结构

在手撸算法之前，我们先来认识一下数据结构中的两个重要概念：物理结构和逻辑结构。

当谈到“物理”和“逻辑”一词时，我们可以会想到数据库中的逻辑删除和物理删除。

所谓的物理删除是指通过删除命令真实的将数据从物理结构中删除的过程；而逻辑删除是指通过修改命令将数据更改为“已删除”的状态，并非真实的删除数据。

这里的逻辑结构和物理结构和上面的概念类似，所谓的物理结构是指可以将数据存储在物理空间中，比如数组和链表都属于物理数据结构；而逻辑结构则是用于描述数据间的逻辑关系的，比如本文要讲的栈就属于逻辑结构。

太难了，我不听

可能有些人看到这里就蒙了，没关系，我这里举一个例子你就明白了。

如果用人来表示物理结构和逻辑结构的话，那么真实存在的有血有肉的人就属于物理结构，而人的思想和信念就属于逻辑结构了。

物理结构和逻辑结构

自定义栈I：数组实现

通过上面的内容，我们知道了栈属于逻辑结构，因此它的实现方式就可以有很多种了，比如数组的实现方式或者是链表的实现方式。那么我们就先用数组实现一下，栈的主要方法有：

栈的主要方法

① 定义结构

那么我们先来定义它的结构：

public class MyStack {
    private Object[] value = null; // 栈存储容器
    private int top = -1; // 栈顶（的指针）
    private int maxSize = 0; // 栈容量


    // 构造函数（初始化默认容量）
    MyStack() {
        this.maxSize = 10;
    }


    // 有参构造函数
    MyStack(int initSize) throws Exception {
        if (initSize  Hello


从上述代码可以看出，我们添加栈的顺序是 `Hello`、`Java` 而输出的顺序是 `Java`、 `Hello` 符合栈的定义（后进先出）。


## 自定义栈II：链表实现


除了数组之外，我们可以还可使用链表来实现栈结构，它的实现稍微复杂一些，我们先来看链表本身的数据结构：


![链表的数据结构](https://atts.zijiebao.com/attachments/image/20200923/1600831705876009.png "链表的数据结构")


使用链表实现栈的流程如下：


![链表实现栈的流程](https://atts.zijiebao.com/attachments/image/20200923/1600831725907957.gif "链表实现栈的流程")


也就是说，入栈时我们将数据存储在链表的头部，出栈时我们从头部进行移除，并将栈顶指针指向原头部元素的下一个元素，实现代码如下。


我们先来定义一个链表节点：

public class Node { Object value; // 每个节点的数据 Node next; // 下一个节点

public Node(Object value) { this(value, null); }

/**

  • 创建新节点
  • @param value 当前节点数据
  • @param next 指向下一个节点（头插法） */ public Node(Object value, Node next) { this.value = value; this.next = next; } }

接下来我们使用链表来实现一个完整的栈：


public class StackByLinked {


    private Node top = null; // 栈顶数据
    private int maxSize = 0; // 栈最大容量
    private int leng = 0; // 栈实际容量


    public StackByLinked(int initSize) throws Exception {
        if (initSize = maxSize;
    }


    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty() {
        return leng  Java
>
> Hello


## 总结


本文我们使用了数组和链表等物理结构来实现了栈，当然我们也可以使用其他容器来实现，比如 [Java](https://www.zijiebao.com/java/) 中的 `List`，我们只需要保证在操作栈时是后进先出的执行顺序，并且至少包含 3 个重要方法：入栈、出栈和查询栈顶元素就可以了。


## 最后


**算法和数据结构的学习是 3 分学 7 分练**，只看不练是没办法学好算法的，而且**学习算法和数据结构是一个循序渐进的过程，短时间内不会有明显的收效**。因为这些算法经过了几百年的发展和积累才得以流传下来的，所以想要“玩得转”还需要一点耐心。


这里给你讲一个学习算法的“秘诀”：**看不懂的知识要反复看，如果反复看还是看不懂，那么别着急，休息一下再继续看！**相信我，对于学习算法这件事，所有人的过程都是一样的。


以上就是`W3Cschool字节宝`关于**动图演示：手撸堆栈的两种实现方法！**的相关介绍了，希望对大家有所帮助。
Java

0 人点赞