day10--232.用栈实现队列+ 225. 用队列实现栈+20. 有效的括号+ 1047. 删除字符串中的所有相邻重复项

一、232.用栈实现队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
文章讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1nY4y1w7VC

1.1 初见思路

1.栈先进后出，队列先进先出
2.两个栈，栈A和栈B来模拟队列，入队列操作=入栈A，出队列=出栈B
3.出队列时，先判断栈B是否还有值，如果没有，就把A中的所有都弹出放入栈B，如果B有值，就直接从B中弹出

1.2 具体实现

class MyQueue {
    Stack<Integer> stackA;
    Stack<Integer> stackB;

    public MyQueue() {
        stackA=new Stack<Integer>();
        stackB=new Stack<Integer>();
    }
    
    public void push(int x) {
        stackA.push(x);
    }
    
    public int pop() {
        if(!stackB.isEmpty()){
            return stackB.pop();
        }
        else{
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
            return stackB.pop();
        }
    }
    
    public int peek() {
        if(!stackB.isEmpty()){
            return stackB.peek();
        }
        else{
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
            return stackB.peek();
        }
    }
    
    public boolean empty() {
        return stackA.isEmpty() && stackB.isEmpty();
    }
}

1.3 重难点

• 把思路想好，没有什么难度

二、 225. 用队列实现栈

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/description/
文章讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1Fd4y1K7sm

2.1 初见思路

1.跟用栈实现队列有区别
2.两个队列A和B，让A中的顺序和栈中出栈的顺序保持一致，让B作为辅助队列

2.2 具体实现

class MyStack {

    Queue<Integer> queue1; // 和栈中保持一样元素的队列
    Queue<Integer> queue2; // 辅助队列

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在辅助队列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

2.3 重难点

• 如何实现队列A的顺序和栈的元素顺序一致

三、 20. 有效的括号

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

3.1 初见思路

1.用栈来实现

3.2 具体实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack  = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='(' || c=='{' || c=='['){
                stack.push(c);
            }
            else{
                if(stack.isEmpty()){
                    return false;
                }
                char pc = stack.pop();
                if(pc=='('){
                    if(c==')'){
                        continue;
                    }
                    else{
                        return false;
                    }
                }
                if(pc=='{'){
                    if(c=='}'){
                        continue;
                    }
                    else{
                        return false;
                    }
                    
                }
                if(pc=='['){
                    if(c==']'){
                        continue;
                    }
                    else{
                        return false;
                    }
                    
                }
            }
        }
        return stack.isEmpty();
    }
}

3.3 重难点

• 无

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

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
文章讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
视频讲解：https://www.bilibili.com/video/BV12a411P7mw

4.1 初见思路

1.入栈时先判断栈顶元素是否等于准备入栈的元素，如果相等就不入栈而进行弹出栈顶元素
但是这种实现方法，会存在最终的栈怎么转成字符串?
2.所以应该使用双向队列，即可以从尾部删除元素，有可以从头开始访问元素拼接字符串

4.2 具体实现

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

4.3 重难点

• 考虑到效率后应采用双向队列实现