数据结构之栈篇

Hello，大家好！我是老丑，今天给大家分享的是一种数据结构——栈。

数据结构是什么？

数据结构是计算机存储、组织数据的方式。数据结构是指互相之间存在一种或多种特定关系的数据元素的集合。
——【百度百科】

这样听好像晦涩难懂，那么大白话来了。

数据结构其实就是一个以它所具备的方式存取数据的容器。（这里还不懂，那你过来，我来捶你）

栈是什么？

大家可能会说“你这标题不是写了吗，数据结构之栈篇”，那栈肯定是数据结构啊。

你们说的对！

栈是那么多数据结构中的一种。也是面试常问的一种，当然面试常问的很多，今天我们只讨论这个迷人的栈。

必要的概念

栈顶、栈底、入栈（进栈，压栈）、出栈（退栈）、栈顶元素。（先让大家有个初步的印象，后面会具体解释）

栈的定义

栈是一种线性表，限定仅在表的末端进行插入和删除操作的线性表。我们称表的末端称之为栈顶，相反地，我们称表的顶端称之为栈底。

栈的一些操作

push：向一个栈加入新元素称之为进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。

pop：从一个栈中删除一个元素称之为出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素（知道指哪一个吗？栈顶的上面是没有元素的，现在应该知道了吧）成为新的栈顶元素。

size：返回目前栈存储的元素容量

peek：返回栈顶元素，但是不会删除栈顶元素

empty：判断栈是否为空，这个空的概念就是不存储元素

栈的特性

根据栈的定义和栈的push和pop操作，其实我们不难发现栈的特性。使用栈存储的元素都是先进后出（FILO，First in Last out），后进先出（LIFO，Last in First out），这两个描述都可。

图解

怕大家理解概念脑补太累，因此我就画了一个图省得大家累。哎，我太贴心了。

栈的具体实现

很开心，大家能看到这里呀，证明大家还是想学习这篇的知识。

下面我会讲一下Java中栈的具体实现。为什么选择Java，因为老丑爱Java！就像老鼠爱大米一样爱。

在Java中，有一个类叫Stack，也就是栈。我们来看看它的Diagram：

图中的继承关系一目了然对吧，其实Stack的底层就是使用Vector实现的，Vector是一款线程安全的集合。

Stack类中定义的一些方法

public E push(E item) {}
public synchronized E pop() {}
public synchronized E peek() {}
public boolean empty(){}

在这里，我主要是列举了一些栈的操作方法。

在这里不知道大家是否有注意到我们的push方法和empty方法并没有使用synchronized进行修饰，但是其他元素操作方法都使用了synchronized操作，其实也就是意味着Stack是一款线程安全的集合，但是push方法为什么没有采用synchronized进行修饰，我希望大家可以自己阅读源码找到答案。大家也可以阅读Java中的并发会有什么问题呢？如何解决呢？

自实现线程安全Stack

在这里我们采用ArrayList来实现我们的Stack（当然不止一种实现方式），如果对ArrayList不熟悉的小伙伴，可以阅读ArrayList源码解析，里面有分享ArrayList的一些知识。

public class MyStack {

    // 承载元素的容器
    private ArrayList<String> stacks;

    // 栈的大小
    private int size;

    public MyStack() {
        stacks = new ArrayList<>();
        size = 0;
    }

    // push 压栈
    public synchronized String push(String item) {
        stacks.add(item);
        size++;
        return item;
    }

    // 判断栈是否为空
    public synchronized boolean empty() {
        return size == 0;
    }

    // 获取栈的大小
    public synchronized int size() {
        return size;
    }

    // 获取栈顶元素
    public synchronized String peek() {
        if(empty()) {
            return null;
        }
        return stacks.get(size - 1);
    }

    // 出栈
    public synchronized String pop() {
        if(empty()) {
            return null;
        }
        String item = stacks.get(size - 1);
        size--;
        stacks.remove(size);
        return item;
    }

}

小测试

如果大家看到这里，想必大家已经对栈有了一定的认识。

纸上得来终觉浅，绝知此事要躬行！

那么下面我就出一道题来测试测试大家呀，帮大家回顾回顾呢。

问题： 现在有一个栈，我们将ABCDE以A，B，C，D，E的次序放入到栈中，在放入的过程中是允许出栈的，而且最后栈保证是空的（也就是将栈中的元素全部弹出），那么下面哪一个是不可能是出栈顺序。

BCDAE
EDACB
BCADE
AEDCB

想看答案吗？没有。

答案在本文末尾，就怕大家不小心看到（偷瞄）答案。大家可以花点时间来做下这题，也可以将前面的概念融合进来进行巩固。

终极测试

可是有些小伙伴就是特别优秀，什么都难不住他。

那么就出道题给大家思考啦。(这道题是LeetCode上面的呢，Easy题)

这题目可以使用栈来解决，大家加油呀。

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode）