掌握情况

题目	通关
用栈实现队列	未通过
用队列实现栈	未通过
有效的括号	未通过
删除字符串中的所有相邻重复项
逆波兰表达式求值	未通过
滑动窗口最大值	未通过
前 K 个最大元素

用栈实现队列

232. 用栈实现队列

问题

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

算法思想

将一个栈作为输入栈，用于压入 push 传入的数据；另一个栈作为输出栈，用于 pop 和 peek 操作
每次 pop 或 peek 时，若输出栈为空，则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序

参考答案

class MyQueue {

    // 输入栈，负责入队
    private Stack<Integer> inStack;
    // 输出栈，负责出队
    private Stack<Integer> outStack;

    public MyQueue() {
        this.inStack = new Stack<>();
        this.outStack = new Stack<>();
    }

    // 入队：向 in 栈压入元素，如果 in 栈满了，则将 in 栈元素依次出栈并压入 out 栈
    // Java API 栈属于无界的
    public void push(int x) {
        inStack.push(x);
    }

    // 出队：将 out 栈元素依次弹出，如果 out 栈为空，则将 in 栈元素依次出栈并压入 out
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

用队列实现栈

225. 用队列实现栈

问题

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

算法思想

把队列当成一个环用，每次都把除了队列末端的元素都出队然后依次加到原本末端元素的后端，这样原本最后的元素就被推到了队列最前端，实现了 Last In First Out。

参考答案

有效的括号

20. 有效的括号

问题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

算法思想

当遇到一个左括号时，会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶。
当遇到一个右括号时，需要将一个相同类型的左括号闭合。此时，可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。
为快速判断括号的类型，可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

参考答案

public boolean isValid(String s) {

    // base case
    // 如果不是偶数，直接 pass
    if (s.length() % 2 == 1) {
        return false;
    }

    // 匹配字典
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');

    Stack<Character> stack = new Stack<>();
    // 循环遍历字符串
    for (int i = 0; i < s.length(); i++) {
        // 遍历当前字符
        Character ch = s.charAt(i);
        // 如果是右括号
        if (map.containsKey(ch)) {
            // 1. 如果栈为空，说明无法匹配
            // 2. 如果右括号与栈顶括号（左括号）不匹配
            if (stack.isEmpty() ||
                map.get(ch) != stack.peek()) {
                return false;
            }
            // 如果右括号能匹配相应的左括号，则出栈栈顶元素
            stack.pop();
        } else {
            // 如果是左括号
            stack.push(ch);
        }
    }
    // 栈中没有元素，菜鸟证明完全匹配
    return stack.isEmpty();
}

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

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

问题

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一

逆波兰表达式求值

150. 逆波兰表达式求值

问题

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

算法思想

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

如果遇到操作数，则将操作数入栈；
如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

参考答案

public int evalRPN(String[] tokens) {

    // 逆波兰表达式严格遵循「从左到右」的运算
    // 计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式
    //  1. 如果遇到操作数，则将操作数入栈；
    //  2. 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，
    // 使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < tokens.length; i++) {
        String token = tokens[i];
        if (isNumber(token)) { // 如果遇到操作数，将操作数入栈
            stack.push(Integer.parseInt(token));
        } else { // 如果遇到运算符，先出栈右操作数，再出栈左操作数
            // 右操作数
            int rightNum = stack.pop();
            // 左操作数
            int leftNum = stack.pop();
            stack.push(calExpression(leftNum, rightNum, token));
        }
    }
    return stack.pop();
}

// 计算表达式
public Integer calExpression(int leftNum, int rightNum, String operator) {

    int ans = 0;
    switch (operator) {
        case "+":
            ans = leftNum + rightNum;
            break;
        case "-":
            ans = leftNum - rightNum;
            break;
        case "*":
            ans = leftNum * rightNum;
            break;
        case "/":
            ans = leftNum / rightNum;
            break;
        default:
    }
    return ans;
}

public boolean isNumber(String token) {
    return !("+".equals(token) ||
             "-".equals(token) || 
             "*".equals(token) || 
             "/".equals(token));
}