栈 Stack

• 栈也是一种线性结构
• 相比数组，栈对应的操作是数组的子集
• 只能从一端添加元素，也只能从一端取出元素
• 这一端称为栈顶
• 栈数据结构对于计算机世界组建逻辑非常重要
• 栈是一种后进先出的数据结构
• Last In First Out (FIFO)
• 在计算机的世界里，栈拥有这不可思议的作用

栈的应用

• 无处不在的 Undo 操作（撤销）
• 程序调用的系统栈

栈的实现

Stack

• void push(E)
• E pop()
• E peek()
• int getSize()
• boolean isEmpty()

1. 从用户的角度看，支持这些操作就好
2. 具体底层实现，用户不关心
3. 实际底层有多种实现方式

Interface Stack <—— ArrayStack implement

• void push(E)
• E pop()
• E peek()
• int getSize()
• boolean isEmpty()

Stack.java

/**
 * @author harrytsz
 * @create 2020-04-28 下午3:21
 */
public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

ArrayStack.java

/**
 * @author harrytsz
 * @create 2020-04-28 下午3:22
 */
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();
    }

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

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

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

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

    @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();
    }
}

Main.java

import org.junit.Test;

public class Main {
    @Test
    public void test1(){
        ArrayStack<Integer> myStack = new ArrayStack<>();
        for(int i = 0; i < 5; i++) {
            myStack.push(i);
        }
        System.out.println(myStack);
    }
}

栈的应用

undo 操作 —— 编辑器

系统调用栈 —— 操作系统

括号匹配 —— 编译器

• 20. Valid Parentheses

  栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur == '{' || cur == '[' || cur == '('){
                stack.push(cur);
            }
            else {
                if(stack.isEmpty()) return false;
                
                char topChar = stack.pop();
                if(cur == ')' && topChar != '(') return false;
                if(cur == ']' && topChar != '[') return false;
                if(cur == '}' && topChar != '{') return false;
             }
        }
        return stack.isEmpty();
    }
}

import org.junit.Test;

/**
 * @author harrytsz
 * @create 2020-04-28 下午4:14
 */
public class Parentheses {
    public boolean isValid(String s){
        ArrayStack<Object> stk = new ArrayStack<>();
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur == '{' || cur == '(' || cur == '[')
                stk.push(cur);
            else {
                if(stk.isEmpty()) return false;
                char top = (char) stk.pop();
                if(cur == ']' && top != '[') return false;
                if(cur == ')' && top != '(') return false;
                if(cur == '}' && top != '{') return false;
            }
        }
        return stk.isEmpty();
    }

    @Test
    public void test(){
        System.out.println(isValid("(){}[]"));
        System.out.println(isValid("(){}["));
        System.out.println(isValid("([{}])"));
    }
}

学习方法讨论

• 不要完美主义，掌握好“度”；
• 学习本着自己的目标去；
• 对于这个课程，大家的首要目标，是了解各个数据结构的底层实现原理。