栈（Stack）又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。

题解报告LeetCode#71：简化路径

题意：LeetCode#71：简化路径

思路：

  1. 一句话解释，栈解决，把当前目录压入栈中，遇到`..`弹出栈顶，最后返回栈中元素。

代码：

class Solution {

    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();

        for (String item : path.split("/")) {
            if (item.equals("..")) {
                if (!stack.isEmpty()) stack.pop();
            } else if (!item.equals(".") && !item.equals("")) {
                stack.push(item);
            }
        }

        String ans = "";
        for (String item : stack) {
            ans = "/" + item + ans;
        }

        return ans.isEmpty() ? "/" : ans;
    }
}

题解报告LeetCode#150：逆波兰表达式求值

题意：LeetCode#150：逆波兰表达式求值

思路：用栈，试一下 switch，在这里代码更规范些

代码：

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t){
                case "+": 
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int num = stack.pop();
                    stack.push(stack.pop() - num);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int num2 = stack.pop();
                    stack.push(stack.pop() / num2);
                    break;
                default:
                    stack.push(Integer.valueOf(t));
            }
        }
        return stack.pop();
    }
}

题解报告LeetCode#844：比较含退格的字符串

题意：LeetCode#844：比较含退格的字符串

思路：

通过栈来构造去除了退格符和被删除字符后的字符栈，然后比较它们是否相等。

代码：

class Solution {
    public boolean backspaceCompare(String S, String T) {
        Stack<Character> stack1 = build(S);
        Stack<Character> stack2 = build(T);

        if (stack1.size() != stack2.size()) {
            return false;
        }

        while (!stack1.isEmpty()) {
            if (stack1.pop() != stack2.pop()) {
                return false;
            }
        }

        return true;
    }

    private Stack<Character> build (String S) {
        Stack<Character> stack = new Stack<>();
        for (char c : S.toCharArray()) {
            if (c == '#') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } 
            }else {
                stack.push(c);
            }
        } 
        return stack;
    }
}