代码随想录-刷题第十一天

232. 用栈实现队列

题目连接：232. 用栈实现队列

思路：一个栈作为输入栈，一个栈作为输出栈。在push数据的时候，直接将数据放到输入栈，在pop数据的时候，如果输出栈为空，将输入栈的数据全部导入到输出栈，如果输出栈不为空，直接pop输出栈。如果两个栈都为空，模拟队列为空。

class MyQueue {
    private Stack<Integer> s1, s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    /**
     * 添加元素到队尾
     */
    public void push(int x) {
        s1.push(x);
    }

    /**
     * 删除队头的元素并返回
     */
    public int pop() {
        // 先调用 peek 保证 s2 非空
        peek();
        return s2.pop();
    }

    /**
     * 返回队头元素
     */
    public int peek() {
        if (s2.isEmpty())
            // 把 s1 中元素全部压入 s2
            while (!s1.isEmpty())
                s2.push(s1.pop());
        return s2.peek();
    }

    /**
     * 判断队列是否为空
     */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

225. 用队列实现栈

题目连接：225. 用队列实现栈

思路：一个队列在模拟栈弹出元素的时候只要将队尾元素前面的所有元素重新塞到队尾，让队尾元素排到队头，此时再去弹出元素就是栈的顺序了。

class MyStack {
    Queue<Integer> q;
    int top_elem;

    public MyStack() {
        q = new LinkedList<>();
        top_elem = 0;
    }
    
    /**
     * 添加元素到栈顶
     */
    public void push(int x) {
        // x 是队列的队尾，是栈的栈顶
        q.offer(x);
        top_elem = x;
    }

    /**
     * 删除栈顶的元素并返回
     */
    public int pop() {
        int size = q.size();
        // 留下队尾 2 个元素
        while (size > 2) {
            q.offer(q.poll());
            size--;
        }
        // 记录新的队尾元素
        top_elem = q.peek();
        q.offer(q.poll());
        // 删除之前的队尾元素
        return q.poll();
    }

    /**
     * 返回栈顶元素
     */
    public int top() {
        return top_elem;
    }

    /**
     * 判断栈是否为空
     */
    public boolean empty() {
        return q.isEmpty();
    }
}

20. 有效的括号

题目连接：20. 有效的括号

思路：一次遍历，遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。遍历结束后栈为空，说明匹配成功。

时间复杂度O(n)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> left = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[')
                left.push(c);
            else // 字符 c 是右括号
                if (!left.isEmpty() && leftOf(c) == left.peek())
                    left.pop();
                else
                    // 和最近的左括号不匹配
                    return false;
        }
        // 是否所有的左括号都被匹配了
        return left.isEmpty();
    }

    private char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ']') return '[';
        return '(';
    }
}

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

题目连接：1047. 删除字符串中的所有相邻重复项

思路：为什么会想到用栈？因为和上一题有效括号一样，都是做消除操作。匹配问题是栈的强项。栈为什么适合做这种类似于爱消除的操作，因为栈记录了遍历数组当前元素时，前一个元素是什么。

时间复杂度O(n)

class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当栈中有字符时，
            // 并且当前字符和栈中字符相等，弹出栈顶字符，同时top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

另一种写法，执行用时更短

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder res = new StringBuilder();
        // 转换成字符数组更方便
        char[] ch = s.toCharArray();
        int top = -1;
        for (char c : ch) {
            if(top >= 0 && c == res.charAt(top)) {
                res.deleteCharAt(top);
                top--;
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}