栈 | 黑豆的博客

# 栈的简介

栈也是一种线性结构，相比数组，栈对应的操作是数组的子集，只能从一端添加元素，取出元素的时候也只能从同一端取出元素，这一端通常称为栈顶。栈是一种后进先出（Last in First Out简称LIFO）的结构。

# 栈的应用

在计算机的世界里，栈拥有着不可思议的作用。这里举两个常见的应用：

撤销操作

比如我们在编辑文本的时候有时要撤销当前的操作恢复到之前的操作，这个撤销操作的原理实际就是靠栈来维护的。当我们向编辑器输入内容时，编辑器会记录我们输入的内容，这个记录的方式就是把新增内容放到一个栈中，当我们撤销的时候就把栈顶的内容拿出来。

程序调用的系统栈

在程序执行的过程中经常会出现在一个逻辑先终止调到另外的一个逻辑去执行的的情况，比如函数fn1内包含fn2，当执行到fn2时会先暂停fn1中剩余的代码执行，调到fn2执行，当执行完fn2后再继续执行fn1的剩余代码。在这个过程中计算机会使用一个系统栈的这样的栈数据结构来维护程序的调用过程。

# 栈的基本实现

对于栈来说我们只实现以下方法

方法名	含义
void push(E)	入栈
E pop()	出栈
E peek()	查看栈定元素
int getSize()	查看栈中一共有多少个元素
boolean isEmpty()	判断栈是否为空

这里我们使用之前实现的动态数组来实现栈这种数据结构，由于调用的都是之前数组类中的方法这里不再赘述，直接给出具体实现：

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

public class ArrayStack<E> implements Stack<E> {
    Array<E> array;
    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

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

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

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append("[");

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));

            if (i!= array.getSize() - 1)
                res.append(", ");
        }

        res.append("] top");

        return res.toString();
    }
}

下面编码来测试下上面我们实现的栈这种数据结构：

public class Main {
    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);
    }
}

控制台打印出：

Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 2] top
Stack: [0, 1, 2, 3] top
Stack: [0, 1, 2, 3, 4] top
Stack: [0, 1, 2, 3] top

# 复杂度分析

方法	时间复杂度	备注
void push(E e)	O(1)	均摊
E pop()	O(1)	均摊
E peek()	O(1)
int getSize()	O(1)
boolean isEmpty()	O(1)

# 括号匹配

前面我们实现了栈这种数据结构，下面我们通过一到力扣题来简单看下栈这种数据结构在编程方面的应用：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

思路：可以依次遍历给出的字符串，如果遍历到的字符是"{"、"("、"["这样的左括号，就将它们压如栈，如果遍历到的不是左括号，就从栈顶中取出一个元素看看这个元素是否和当前遍历到的元素是否匹配，如果匹配就继续遍历，如果不匹配则表明给出的字符串不满足条件。

代码如下：

import java.util.Stack;

class Solution {

    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{
                if(stack.isEmpty())
                    return false;

                char topChar = stack.pop();
                if(c == ')' && topChar != '(')
                    return false;
                if(c == ']' && topChar != '[')
                    return false;
                if(c == '}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

测试下我们上面所写的代码是否正确：

public class Main {
    public static void main(String[] args) {
        System.out.println((new Solution()).isValid("()[]{}"));
        System.out.println((new Solution()).isValid("([)]"));
    }
}

输出结果：

true
false

← 数组队列 →