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

什么是栈? 算法 第1张

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

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

什么是栈? 算法 第2张

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

什么是栈? 算法 第3张

接下来,数据 Red 入栈。

什么是栈? 算法 第4张

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

什么是栈? 算法 第5张

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

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

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

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

如何理解栈?

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

什么是栈? 算法 第6张

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

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

栈的实现

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

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

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

什么是栈? 算法 第7张

那么我先用 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;
    }
}

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

什么是栈? 算法 第8张

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

/**
 * 基于链表实现的链式栈
 *
 * @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)。

参考

《我的第一本算法书》

《算法图解》

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄