随手笔记（四十二）——关于Stack部分原理分析

我做了LeetCode上的316题：去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

解法用了栈

public String removeDuplicateLetters(String s) {
            Stack stack = new Stack<>();
        for (int i=0;i
            Character c = s.charAt(i);
            if (stack.contains(c)) continue;
            while (!stack.isEmpty() && stack.peek()>c && s.indexOf(stack.peek(),i)!=-1)
                stack.pop();
            stack.push(c);
        }
        char [] res = new char[stack.size()];
        for (int i=0;i
            res[i] = stack.get(i);
        }
        return new String(res);
    }

关于Stack简述：

他是Java里数据结构栈的一种实现方式，在同步容器中属于线程安全的，Vector也是线程同步的，只不过vector底层是一个数组，Stack继承了Vector，事实上他是我们的顺序栈以数组的形式实现的栈结构。

关于add()和push()

add()直接调用的就是Vector的，push()调了一个addElement(),这个addElement是Vector的，modeCount++之后调用了add()，modeCount就是版本号，记录修改次数，遍历时如果遇到非原子性操作就会通过modeCount来检查，检查出问题就会触发fail-fast

关于get()、peek()、pop()

get()方法直接调的Vector，这个方法属于数组的方法根据下标获取元素；

peek()是Stack自己的，属于栈的方法，获取栈顶元素的值；

源码的话首先获取size但是不知道为啥拿int len 接收的时候len 和int直接有5个空格，如果长度为0直接EmptyStackException，正常的话调了elementAt(len-1)并返回就是去拿了队尾元素；

elementAt()是属于Vector的方法，判断了一下下标是否超过了数量，之后调了elementData(),这个方法就是直接从底层数组取值并返回了。

pop()是Stack自己的，属于栈的方法，获取并弹出栈顶元素；

首先获取size，他比peek多了一步，准确的说它调用了peek()最后返回了peek的值；

调完peek()之后调用了removeElementAt(len-1)，这个方法显然也是调的Vector的，他就是根据下标删除相应数组元素的方法，简单校验一下下标是否合法，增加modeCount，减少elementCount，将当前要删除元素置为null。