代码随想录二刷第九天 | 232.用栈实现队列、225. 用队列实现栈、20. 有效的括号、1047. 删除字符串中的所有相邻重复项

232.用栈实现队列

思路

两个栈，一个用于入队stackIn，一个用于出队stackOut。

push时直接进入stackIn，pop时要讨论，stackOut不为空直接pop，否则将stackIn整体放到stackOut

代码

class MyQueue {
    Stack<Integer> stackIn = new Stack<>();
    Stack<Integer> stackOut = new Stack<>();
    
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        copy();
        return stackOut.pop();
    }
    
    public int peek() {
        copy();
        return stackOut.peek();
    }

    public void copy(){
        if(!stackOut.isEmpty()) return;
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
    
    public boolean empty() {
        return stackOut.isEmpty() && stackIn.isEmpty();
    }
}

225. 用队列实现栈

思路

用一个队列实现，每次出栈时都把需要弹出元素之外的其余元素重新入队。

代码

class MyStack {
    Queue<Integer> queue;
    
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        rePosition();
        return queue.poll();
    }
    
    public int top() {
        rePosition();
        int result = queue.poll();
        queue.add(result);
        return result;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    public void rePosition(){
        int size = queue.size();
        size--;
        while(size-->0)
            queue.add(queue.poll());
    }
}

20. 有效的括号

思路

利用栈的先入后出性质即可解决。

不过要注意栈为空push右括号和最后栈不为空的情况。

代码

时间复杂度：O(n) 空间复杂度：O(n)

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

        return stack.isEmpty();
    }
}

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

思路

利用栈的性质即可解决。

代码

时间复杂度：O(n) 空间复杂度：O(n)

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(stack.isEmpty()){
                stack.push(cur);
            }else{
                if(stack.peek() == cur){
                    stack.pop();
                }else{
                    stack.push(cur);
                }
            }
        }
        String res = "";
        while(!stack.isEmpty()){
            res = stack.pop().toString() + res;
        }
        return res;
    }
}