数据基础结构--栈（Stack，基于Array底层实现）

#栈 Stack

• 栈也是一种线性结构
• 相比数组，栈对应的操作是数组的子集
• 只能从一端添加元素，也只能从一端取出元素，这一端称为栈顶
• 栈是一种后进先出的数据结构（Last In First Out – LIFO）
• 在计算机的世界里，栈拥有着不可思议的作用

其实⾮常好理解，我们将栈可以看成⼀个箱⼦：

• 往箱⼦⾥⾯放东⻄叫做⼊栈
• 往箱⼦⾥⾯取东⻄叫做出栈
• 箱⼦的底部叫做栈底
• 箱⼦的顶部叫做栈顶

说到栈的特性，肯定会有⼀句经典的⾔语来概括： 先进后出(LIFO, Last In First Out)

• 往箱⼦⾥边放苹果，箱⼦底部的苹果想要拿出来，得先把箱⼦顶部的苹果取⾛才⾏

栈的应用

• 无处不在的Undo操作（撤销）– 编辑器

  • 例如：编辑器输入“沉迷 学习 无法 自拔”

    

    进行删除/撤销的操作，都是从“栈顶”开始

• 程序调用的系统栈 ，系统调用，子逻辑调用的内部实现过程（断点执行）

栈的基本实现

• Interface Stack
  • void push(E)
  • E pop()
  • E peek()
  • int getSize()
  • boolean isEmpty
• 从用户角度看，支持这些操作就好
• 具体底层实现，用户不关心
• 实际底层有多种实现方式

定义栈的基本实现的接口，可以不同底层实现方式实现定义栈的接口

package demo.structure.stack;

/**
 * 栈的基本实现--接口
 *
 * @author jingLv
 * @date 2020/11/30
 */
public interface Stack<E> {

    /**
     * 获取栈的个数
     *
     * @return 元素个数
     */
    int getSize();

    /**
     * 判断栈是否为空
     *
     * @return boolean
     */
    boolean isEmpty();

    /**
     * 入栈
     *
     * @param e 入栈的元素
     */
    void push(E e);

    /**
     * 弹栈
     *
     * @return 弹栈的元素
     */
    E pop();

    /**
     * 返回栈顶元素
     *
     * @return 栈顶元素
     */
    E peek();
}

数组（Array）实现栈

以数组为底层实现方式（依赖上面的数组实现）

package demo.structure.stack;

import demo.structure.array.Array;

/**
 * 数组实现栈
 *
 * @author jingLv
 * @date 2020/11/30
 */
public class ArrayStack<E> implements Stack<E> {

    /**
     * 定义数组
     */
    Array<E> array;

    /**
     * 构造函数--初始化栈
     *
     * @param capacity 数组的容量
     */
    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    /**
     * 无参构造函数
     */
    public ArrayStack() {
        array = new Array<>();
    }

    /**
     * 栈中元素的个数
     *
     * @return 元素的个数
     */
    @Override
    public int getSize() {
        return array.getSize();
    }

    /**
     * 判断栈是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 入栈
     *
     * @param e 入栈的元素
     */
    @Override
    public void push(E e) {
        array.addLast(e);
    }

    /**
     * 弹栈
     *
     * @return 弹出栈的元素
     */
    @Override
    public E pop() {
        return array.removeLast();
    }

    /**
     * 获取栈顶的元素
     *
     * @return 栈顶元素
     */
    @Override
    public E peek() {
        return array.getLast();
    }

    /**
     * 数组实现栈的容量
     *
     * @return 容量值
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 格式化输出栈
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append("Stack:");
        result.append('[');
        for (int i = 0; i < array.getSize(); i++) {
            result.append(array.get(i));
            if (i != array.getSize() - 1) {
                result.append(",");
            }
        }
        result.append("] top");
        return result.toString();
    }
}

测试方法

package demo.structure.stack;

import java.util.Random;

/**
 * 测试数组实现栈
 *
 * @author jingLv
 * @date 2020/12/10
 */
public class ArrayStackMain {
    public static void main(String[] args) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

执行结果：

栈的应用实现

括号匹配

• 有效的括号（leetcode 20题）
• 栈顶元素反应了在嵌套的层次关系中，最近的需要匹配的元素

package demo.structure.stack;

import java.util.Stack;

/**
 * 有效的括号（leetcode 20题）
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 *
 * @author jingLv
 * @date 2020/12/01
 */
public class ValidParentheses {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // 将字符串拆为字符数组
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                // 左侧括号压入栈
                stack.push(c);
            } else {
                // 栈为空，则直接返回false
                if (stack.isEmpty()) {
                    return false;
                }
                // 右侧括号和目前栈顶的元素进行匹配，如果匹配成功，则出栈
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        // 匹配完成，栈为空，则表示都已匹配，直接返回true
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println("[{()}]，是否匹配？" + new ValidParentheses().isValid("[{()}]"));
        System.out.println("[]{}()，是否匹配？" + new ValidParentheses().isValid("[]{}()"));
        System.out.println("[({)}]，是否匹配？" + new ValidParentheses().isValid("[({)}]"));
    }
}

执行结果：

栈的复杂度分析

• ArrayStack<E>

  • void push(E) O(1)均摊

  • E pop() O(1)均摊

  • E peek() O(1)

  • int getSize() O(1)

  • boolean isEmpty O(1)