栈和队列

1047. 删除字符串中的所有相邻重复项

version01

class Solution {
    public String removeDuplicates(String s) {
        Deque stack = new LinkedList<>();
        char[] a = s.toCharArray();
        for (char c : a) {
            if (stack.isEmpty()) {
                stack.push(c);
            } else if (stack.peek().equals(c)) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        String res = "";
        while (!stack.isEmpty()) {
            res = stack.pop() + res;
        }
        return res;
    }
}

效率很低

class Solution {
    public String removeDuplicates(String s) {
        //字符串做栈
        StringBuffer sb = new StringBuffer();
        int len;
        for (char c : s.toCharArray()) {
            len = sb.length(); //当前字符串容量
            if (len == 0 || c != sb.charAt(len - 1)) {
                sb.append(c);
            } else {
                sb.deleteCharAt(len - 1);
            }
        }
        return sb.toString();
    }
}

 ok,还可以，下面是双指针的效率，设置快慢指针，快指针的内容给慢指针，如指向内容相等则慢指针回退一步，即跳过。

150. 逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        Deque stack = new LinkedList();
        for (String c : tokens) {
            if (c.equals("+")){
                stack.push(stack.pop() + stack.pop());
            } else if (c.equals("-")) {
                stack.push(-stack.pop() + stack.pop());
            } else if (c.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (c.equals("/")) {
                int t = stack.pop();
                stack.push(stack.pop() / t);
            } else {
                stack.push(Integer.valueOf(c));
            }
        }//for
        return stack.pop();
    }
}

这里用String[]存表达式而不用Char[]是因为不是一位数的运算，为什么说这个是因为哥们用switch case语句取String i的charAt(0)作为case的判断式导致出现问题。

参考：programmercarl.com