数据结构-栈和队列

栈的特点

栈是一种线性结构
相比数组，栈对应操作的是数组的子集
只能从一端添加数据，也只能在一端取出数据
这一端被称之为栈顶
先进后出的特点（Last In First Out）

压栈（入栈）和弹栈（出栈）

元素放入栈的过程就叫做入栈，也可以叫压栈。元素取出来的过程就叫做出栈，也可以叫弹栈。 可以理解成机枪的弹夹，弹夹就是一个栈，子弹一颗一颗压进去，就是压栈，把子弹打出来的过程就是弹栈，当然每次打出的子弹一定是弹夹最上面那颗。这里说的元素可以是任意类型，比如方法的出入栈，普通数据类型的出入栈。数据结构是数据的存储方式，并不限定具体的数据是什么。

虽然这种数据结构看起来很简单，但应用非常广泛和强大，比如程序的撤销功能，把每次操作都进行压栈，每次撤销就取栈顶的操作进行弹栈。在比如程序中的递归，这点应该都不陌生了。比如A方法里面调用B，B方法里面调用C，那么过程就是这样的，不断加载方法进栈，等到加载完成后，栈顶的方法先执行，执行后弹栈，紧接着执行最新栈顶的方法。如果使用递归，是要注意递归条件的，不断的加载方法进栈，内存很快就会撑爆。
!

栈的实现

首先根据栈的特点，大概总结出5个方法，把他们定义成接口

public interface Stack<E> {
    //获取栈容量
    int getSize();
    //栈是否为空
    boolean isEmpty();
    //压栈
    void push(E e);
    //弹栈
    E pop();
    //查看一下栈顶的值
    E peek();
}

接着定义一个类，具体实现栈的方法，如果看过上一篇关于数组数据结构的文章，那就很轻松了，这个栈的设计也是基于动态数组的。但是数组操作元素可以很随意，栈对外暴漏的接口只能操作栈顶，对应的方法就是压栈和弹栈以及查看一下栈顶的数据。

public class ArrayStack implements Stack{

    MyArray myArray;

    public ArrayStack(){
        myArray = new MyArray();
    }
    public ArrayStack(int capacity)
    {
        myArray = new MyArray(capacity);
    }

    @Override
    public int getSize() {
        return myArray.getSize();
    }

    @Override
    public boolean isEmpty() {
        return myArray.isEmpty();
    }

    @Override
    public void push(Object o) {
        myArray.addLast(o);
    }

    @Override
    public Object pop() {
        return myArray.removeLast();
    }

    @Override
    public Object peek() {
        return myArray.getLast();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Stack: bottom[");
        for(int x = 0; x < myArray.getSize(); x++)
        {
            sb.append(myArray.getByIndex(x));
            if(x != myArray.getSize() - 1)
            {
                sb.append(",");
            }
        }
        sb.append("]top");
        return sb.toString();
    }
}

栈的另一个应用

下面看一下LeetCode上面的一道题

正确：{()} , (){}，{{}} 错误：[)，[]][，[{]}

这道题的截图解题思路其实也是利用了栈数据结构的特点
1.遍历整个字符串，将左括号的字符压入栈

2.如果是右括号，取出栈顶的字符，判断当前右括号和栈顶的左括号能匹配不，匹配不了，代表括号格式错误。
如果能匹配，就继续下次循环，以此类推，如果全部能匹配，栈内的数据也应该会为空。

private static boolean isValid(String s)
{
    //1.遍历整个字符串
    //2.如果是{[(这种左括号就存入到栈中
    //3.如果是右括号，就从栈顶取出，看一下栈顶和括号和当前右括号是否能匹配上
    //4.循环结束后，如果都能正确匹配上，那么代表栈顶被取空
    //使用Java提供的栈，用法和自己定义的没啥区别
    Stack<Character> stack = new Stack();
    for(int x = 0; x < s.length(); x++)
    {
        char c = s.charAt(x);
        if(c == '{' || c == '[' || c == '(') {
            stack.push(c);
        }
        else
        {
            //栈顶为空直接返回false
            if(stack.isEmpty())
                return false;
            //从栈顶取数据，匹配一下
            char topChar = stack.pop();
            if(topChar == '{' && c != '}')
                return false;
            if(topChar == '[' && c != ']')
                return false;
            if(topChar == '(' && c != ')')
                return false;
        }
    }
    return stack.isEmpty();
}