4，常见数据结构-栈

基础知识

栈也是一种特殊的线性表，他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作，他就好像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的时候不允许从中间放进去，拿书的时候也是先从最上面开始拿，不允许从下边或中间抽出来。

栈的原理图

栈的实现可以使用数组也可以使用链表，我们这里分析的主要是使用数组的形式。

在这里插入图片描述

代码实现

栈的实现其实非常简单，常见的就两种操作，一种是压栈一种是出栈，我们来看下代码

public class Stack<E> {
    private Object[] data;
    private int size;

    public Stack(int capacity) {
        if (capacity <= 0)
            throw new IllegalArgumentException("栈的大小必须大于0");
        data = new Object[capacity];
    }

    public void push(E item) {
        if (isFull())
            throw new IllegalArgumentException("栈已经满了");
        data[size++] = item;
    }

    public E pop() {
        if (isEmpty())
            throw new IllegalArgumentException("栈是空的");
        E temp = (E) data[--size];
        data[size] = null;
        return temp;
    }

    public E peek() {
        if (isEmpty())
            throw new IllegalArgumentException("栈是空的");
        return (E) data[size - 1];
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean isFull() {
        return size() == data.length;
    }

    public int size() {
        return size;
    }
}

这里为了方便，栈的空间大小在初始化的时候就就已经固定了，并且栈满的时候没有扩容，栈是一个非常有用的数据结构，尤其在算法中用到的还是比较多的。栈是一种先进后出的数据结构，他和队列正好相反，队列是一种先进先出的数据结构。

例子

我们来看个非常简单的例子，验证括号的有效性，括号只包含"("，")"，"["，"]"，"{"，"}"这6个字符，比如()，{()}，{}都是有效的，而{]，{(]}都是无效的。

我们来分析一下这道题，当我们遍历到括号的左半边的时候，我们把括号的右半边压栈，当我们遍历到括号右半边的时候，我们就把栈顶的元素弹出，然后在和我们遍历的符号比较看是否一样，我们以字符串"{()}"为例来画图分析一下，

在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

搞懂了上面的图，写出代码就容易多了，我们来看下代码怎么实现

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>(s.length());
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}