数据结构-栈和队列

jiezi

5 年前

栈是一种线性结构
相比数组，栈对应操作的是数组的子集
只能从一端添加数据，也只能在一端取出数据
这一端被称之为栈顶
先进后出的特点（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();}

数据结构-栈和队列

栈的特点

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

栈的实现

栈的另一个应用