什么是栈?

本文将介绍一个重要的数据结构—栈,和之前讲到的链表数组一样也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数据。栈就像是一摞书,拿到新书时我们会把它放在书堆的最上面,取书时也只能从最上面的新书开始取。

如上就是栈的概念图,现在存储在栈中的只有数据 Blue。往栈中添加数据的时候,新数据被放在最上面。

然后,我们往栈中添加了数据 Green。往栈中添加数据的操作叫作入栈

接下来,数据 Red 入栈。

从栈中取出数据时,是从最上面,也就是最新的数据开始取出的,即 Red。从栈中取出数据的操作叫作出栈

如果再进行一次出栈操作,取出的就是 Green 了。

像栈这种最后添加的数据最先被取出,即后进先出的结构,我们称为 Last In First Out,简称 LIFO

与链表和数组一样,栈的数据也是线性排列,但在栈中,添加和删除数据的操作只能在一端进行,访问数据也只能访问到顶端的数据,想要访问中间的数据时,就必须通过出栈操作将目标数据移到栈顶才行。

介绍完栈的基本知识后,接下来举一个例子,比如大家正在看公众号文章,那我就拿微信的订阅号为例。

如何理解栈?

首先你打开订阅号,是一个公众号列表,之后你点击了一个公众号-武培轩,进入了相应的文章列表界面,之后你点击了文章-什么是数组?,进入了文章详情页面。

好了,现在你想返回订阅号怎么办呢?向右滑两次吧,第一次回到文章列表界面,第二次回到订阅号界面。

这时候你就发现了,这些界面的储存结构可以说是一个栈结构,你打开文章详情页面,必须经过两次入栈才能达到,你想回到订阅号界面(位于栈底),必须经历两次出栈把前面两个界面移除。

栈的实现

看到这里,相信你已经对栈有了初步的理解,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。光理解还不够,我们还要动手去实现栈,接下来让我们来看一看如何用代码实现一个栈。

栈有两种存储结构,即顺序存储链式存储,也就是说栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈

首先来看下用数组实现的栈是怎么样的,其实现如下图所示:

那么我先用 Java 语言来实现下顺序栈,代码如下:

/**
 * 基于数组实现的顺序栈
 *
 * @author wupx
 * @date 2020/02/11
 */
public class ArrayStack {
    /**
     * 数组
     */
    private String[] items;
    /**
     * 栈中元素个数
     */
    private int count;
    /**
     * 栈的大小
     */
    private int n;

    /**
     * 初始化数组,申请一个大小为 n 的数组空间
     *
     * @param n
     */
    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }

    /**
     * 入栈
     *
     * @param item
     * @return
     */
    public boolean push(String item) {
        // 数组空间不够了,直接返回 false,入栈失败。
        if (count == n) {
            return false;
        }
        // 将 item 放到下标为 count 的位置,并且 count 加一
        items[count] = item;
        ++count;
        return true;
    }

    /**
     * 出栈
     *
     * @return
     */
    public String pop() {
        // 栈为空,则直接返回 null
        if (count == 0) {
            return null;
        }
        // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
        String tmp = items[count - 1];
        --count;
        return tmp;
    }
}

另外一种就是链式栈,它的实现如下图所示:

再用链表去实现栈,代码如下:

/**
 * 基于链表实现的链式栈
 *
 * @author wupx
 * @date 2020/02/11
 */
public class LinkedListStack {
    private Node top = null;

    /**
     * 入栈
     *
     * @param value
     */
    public void push(int value) {
        Node newNode = new Node(value, null);
        // 判断是否栈空
        if (top != null) {
            newNode.next = top;
        }
        top = newNode;
    }

    /**
     * 出栈
     *
     * @return
     */
    public int pop() {
        if (top == null) {
            // -1 表示栈中没有数据
            return -1;
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    public void printAll() {
        Node p = top;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    private static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }
}

在对栈有了更深一步的理解和实践后,让我们来看下它的空间、时间复杂度各是多少呢?

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)

入栈和出栈只会影响到最后一个元素,不涉及其他元素的整体移动,所以无论是以数组还是以链表实现,入栈、出栈的时间复杂度都是 O(1)

总结

看完之后,相信大家都对栈有了一定的了解,让我们总结下这篇文章的内容,栈是一种线性逻辑结构,只支持入栈和出栈操作,遵循后进先出的原则(FILO)。栈既可以通过数组实现,也可以通过链表来实现,不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。

参考 《我的第一本算法书》 《算法图解》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java 中的 final、finally、finalize 有什么不同?

    Java 中 final、finally、finalize 有什么不同?这是在 Java 面试中经常问到的问题,他们究竟有什么不同呢?

    武培轩
  • TCP三次握手和四次挥手

    TCP三次握手 所谓三次握手(Three-Way Handshake)即建立TCP连接,就是指建立一个TCP连接时,需要客户端和服务端总共发送3个包以确认连接的...

    武培轩
  • 剑指Offer-二进制中1的个数

    package Other; /** * 二进制中1的个数 * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 */ public c...

    武培轩
  • Spring中的Cache

    在其父类AdviceModeImportSelector的selectImports方法中,最终会回调子类的selectImports方法

    spilledyear
  • 笔记20 | 学习整理开源APP(BaseAnimation)程序源码“中的通讯录效果(一)

    项勇
  • 设计模式(二)- 建造者模式 /反射+抽象工厂

    建造者模式又称为“生成器模式”,建造者模式可以将一个产品的内部表象与产品的生产过程分割开来,从而可以使一个建造过程生成具有不同的内部产品对象。当使用建造者模式,...

    用户2288853
  • Eureka源码探索(一)-客户端服务端的启动和负载均衡

    老梁
  • JAVA多线程并发的基础知识

    并发编程是Java程序员最重要的技能之一,也是最难掌握的一种技能。它要求编程者对计算机最底层的运作原理有深刻的理解,同时要求编程者逻辑清晰、思维缜密,这样才能写...

    用户5640963
  • 设计模式(终)

    “ 这一篇文章把剩下剩下的行为型设计模式全部讲完,然后设计模式这一个模块就算结束了,在后面抽出时间再整理一下”

    每天学Java
  • Android混淆设置

    对sighed APK进行代码混淆和精简,从而使得发布的代码可以防止被别人反编译解析。

    剑行者

扫码关注云+社区

领取腾讯云代金券