Stack and Queue Usage - LeetCode 20、222、225

打卡简单的栈和队列算法

LeetCode 20

20.Valid Parentheses

符号匹配，问题分析'(', ')', '{', '}', '[' and ']'这三类括号匹配以相同类型和正确的顺序括号结束。我知道的解法有2种：

Solution 1

1、使用栈FILO的特性，将左括号放入栈中，遇到右括号从栈中取数据，判断是否匹配：

巧思：map固定住了括号之间的匹配关系;

Time Complexity: O(n)

Space Complexity: O(n)

public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<>();
        for (char m : s.toCharArray()) {
            if (map.containsKey(m)) {
                stack.push(m);
            } else {
                if (stack.empty() || !map.get(stack.pop()).equals(m)) {
                    return false;
                }
            }
        }
        return stack.empty();
}

🤔map中key为左括号执行效率更高，为右括号稍弱，还不理解，原因，代码都是一样的写法。有知道原因的可以联系我！感谢！

Solution 2

2、利用字符串替换，发现匹配的括号消除，如有剩余，则为不符合：

Time Complexity: O($n$2/2)

Space Complexity: O(1)

public static boolean isValid2(String s) {
    int length = 0;
    while (s.length() != length) {
        length = s.length();
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    }
    return s.length() == 0;
}

优点：代码简洁；缺点：当字符串变长时执行效率非常低

Leetcode 232

232. Implement Queue using Stacks

栈转队列(use stacks implement queue): FILO –> FIFO

都是使用两个栈，但有两种思路，官方的solution里面有图助于理解，🔗上方👆自取获得：

Solution 1

思路一(个人推荐)：一个栈负责入，一个栈负责出；所有进入队列的元素进入入栈，需要取的时候从出栈取，规则为：input stack pop出元素依次push到 output stack。如input stack中的数据为3->2->1, 依次push到output stack中则为1->2->3。output stack中有元素时操作Custom Queue取数据先pop output stack，为空后才能从input stack中push数据进来，再执行队列其他操作。

faster than 100%; Memory Usage: 36.8 MB, less than 32.98% of Java online submissions for Implement Queue using Stacks.

Time Complexity: push O(1), pop/peek O(n), empty O(1)

Space Complexity: O(n)

class MyQueue {
    
    private Stack<Integer> iStack;
    private Stack<Integer> oStack;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        this.iStack = new Stack<>();
        this.oStack = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        iStack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!oStack.empty()){
            return oStack.pop();
        }else {
            while (!iStack.empty()) {
                oStack.push(iStack.pop());
            }
            return oStack.pop();
        }
    }
    
    /** Get the front element. */
    public int peek() {
        if (!oStack.empty()){
            return oStack.peek();
        }else {
            while (!iStack.empty()) {
                oStack.push(iStack.pop());
            }
            return oStack.peek();
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return iStack.empty()&& oStack.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Solution 2

思路二：一个栈作为中转站，一个作为最终数据存储区（类似于罗汉塔，小的环只能在大环上面👆）

faster than 100%;Memory Usage: 36.8 MB, less than 76.39% of Java online submissions for Implement Queue using Stacks.

Time Complexity: push O(n), pop/peek O(1), empty O(1)

Space Complexity: O(n)

class MyQueue {

    private Stack<Integer> terminalStack;

    private Stack<Integer> transferStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        this.terminalStack = new Stack<>();
        this.transferStack = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        // temporarily move terminalStack's element to transferStack
        if (terminalStack.empty()) {
            terminalStack.push(x);
        } else {
            while (!terminalStack.empty()) {
                transferStack.push(terminalStack.pop());
            }
            terminalStack.push(x);

        }
        // move back
        while (!transferStack.empty()) {
            terminalStack.push(transferStack.pop());
        }
    }


    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        return terminalStack.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        return terminalStack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return terminalStack.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Leetcode 225

225. Implement Stack using Queues

队列转栈(use queues implement stack): FIFO ->FILO

Solution1

思路：使用两个队列，q1存放普通数据，q2存入临时数据；q1中的数据存的时候不做处理，取的时候将前

(n-1)个数据放入q2中，取出q1的第n个数据后，q1和q2交换引用地址。此时q1存放的又是FIFO规则的数据

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement Stack using Queues.

Memory Usage: 36.6 MB, less than 91.06% of Java online submissions for Implement Stack using Queues.

Time Complexity: push/top/empty O(1), pop O(n)

Space Complexity: O(1)

class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;
    private Integer top;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        q1.add(x);
        top = x;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while(q1.size()>1){
            top = q1.remove();
            q2.add(top);
        }
        Queue<Integer> temp;
        temp = q1;
        q1 = q2;
        q2 = temp;
        return q2.remove();
    }

    /** Get the top element. */
    public int top() {
        return top;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Solution 2

思路：使用两个队列，队列q1存放处理好的老数据，q2负责存放新入数据；将q1中的数据依次存放到q2中，交换引用地址，则q1中的数据是又变成处理好的数据了，如此往复即可。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement Stack using Queues.

Memory Usage: 36.8 MB, less than 69.68% of Java online submissions for Implement Stack using Queues.

Time Complexity: push O(n), peek/empty/top O(1)

Space Complexity: push O(1)

class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        q2.add(x);
        while(!q1.isEmpty()){
           q2.add(q1.remove());
        }
        Queue<Integer> temp;
        temp = q2;
        q2 = q1;
        q1 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return q1.remove();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return q1.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return q1.size() == 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Solution 3

思路：只用一个队列解决，每次新增新元素时将前面的元素pop出来再存入队列，即1<-2 to 2<-1, 2<-1<-3 to 1<-3<-2 to 3<-2<-1.

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement Stack using Queues.

Memory Usage: 36.7 MB, less than 69.68% of Java online submissions for Implement Stack using Queues.

Time complexity: push/empty/top O(1), peek/pop O(n)

class MyStack {

    private Queue<Integer> queue;


    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        this.queue = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        while (size > 1) {
            Integer first = queue.remove();
            queue.add(first);
            size--;
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return queue.remove();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return queue.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue.size() == 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Reference Link

20.Valid Parentheses

232. Implement Queue using Stacks

225. Implement Stack using Queues