js css html

日拱一卒:栈(Stack)

2023-02-02  本文已影响0人  Tinyspot

1. 栈(Stack)

public class Stack<E> extends Vector<E> {
    public E push(E item) {
        addElement(item);
        return item;
    }

    // 出栈,弹出栈顶元素,并将栈顶元素返回
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }

    // 获取栈顶元素
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
}

2. 手写栈

2.1 方式一:继承 ArrayList

缺点:可以调用父类的 add(), get(index), 实际并不应该对外提供

public class MyStack<E> extends ArrayList<E> {
    public void push(E element) {
        add(element);
    }
    public E pop() {
        return remove(size() - 1);
    }
    public E peek() {
        return get(size() - 1);
    }
}

测试

MyStack<Integer> stack = new MyStack<>();
stack.push(1);

2.2 方式二:组合方式

public class MyStack<E> {
    // 组合方式,ArrayList 作为一个属性
    private List<E> list = new ArrayList<>();
    public void push(E element) {
        list.add(element);
    }
}

3. 练习

3.1 Leetcode 20 括号序列

方式一:用字符串处理

public static boolean check(String s) {
    // 此处是 while 循环,只要还有能匹配的字符就会一直循环
    while (s.contains("{}") || s.contains("()") || s.contains("[]")) {
        s = s.replace("{}", "");
        s = s.replace("()", "");
        s = s.replace("[]", "");
    }
    return s.isEmpty();
}

方式二:使用栈

  1. 左括号入栈,右括号出栈并比较
  2. 所有字符比较完后,栈应该为空
/**
 * check("{[()]}")
 * 1. 遇见左字符直接入栈
 * 2. 遇见右字符开始比较
 * 3. 注意判断左字符多于右字符的情况 {{[()]}
 */
public static boolean check(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '{' || c == '[' || c == '(') {
            stack.push(c);
        } else {
            // isEmpty 没有左字符了,可能是本身就没有,或出栈完了
            if (stack.isEmpty()) return false;

            char left = stack.pop();
            if (c == '}' && left != '{') return false;
            if (c == ']' && left != '[') return false;
            if (c == ')' && left != '(') return false;
        }
    }
    // 所有字符扫描完后,判断stack.isEmpty,避免左括号多于右括号判断出错
    return stack.isEmpty();
}

补充:其他获取字符的方式

public static boolean check(String s) {
    Stack<Character> stack = new Stack<>();
    int len = s.length();
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        // ...
    }
    return stack.isEmpty();
}

3.2 浏览器的前进后退

上一篇 下一篇

猜你喜欢

热点阅读