2 个跟栈、队列相关的题。

20. Valid Parentheses

Analysis

经典的括号匹配问题。

Code

class Solution {
public:
    bool isValid(string s) {
        if(s.length() % 2) return false;
        stack<char> st;
        bool flag = true;
        for(char ch: s) {
            if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
            else if(!st.empty()) {
                char tmp = st.top();
                if(ch == ')' && tmp == '(') st.pop();
                else if(ch == ']' && tmp == '[') st.pop();
                else if(ch == '}' && tmp == '{') st.pop();
                else flag = false;
            } else flag = false;
        }
        if(st.empty() && flag) return true;
        else return false;
    }
};

注意如果字符串长度为奇数，那么一定不符合条件。

232. Implement Queue using Stacks

Analysis

这也是个经典的问题：用栈实现队列。

Code

method 1

class MyQueue {
public:
    stack<int> st1, st2;
    MyQueue() {

    }
    
    void push(int x) {
        while(!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
        st2.push(x);
        while(!st2.empty()) {
            st1.push(st2.top());
            st2.pop();
        }
    }
    
    int pop() {
        if(st1.empty()) return false;
        int front = st1.top();
        st1.pop();
        return front;
    }
    
    int peek() {
        if(st1.empty()) return false;
        else return st1.top();
    }
    
    bool empty() {
        return st1.empty();
    }
};

重点考虑 push 操作，始终将元素按照队列出队的顺序放在第一个栈中，这样可以简化其他操作。按照这样的思路，除了新元素外，其他元素都需要入栈 2 次，出栈 2 次，总共的操作次数就是 $4n + 2$，其中 $n$ 是队列的大小。

method 2

实际上，也可以不用每次都将元素倒换到第一个栈内。设置一个 front 变量，始终保存最后一个入栈的元素。每次出队，就将第一个栈中的元素全部倒入到第二个栈中，同时弹出第二个栈的栈顶元素，这样就不用来回的倒换元素了，但要稍微修改下 peek 操作和 empty 操作。另外，这样做的实际操作次数是远小于第一种方法的。

class MyQueue {
public:
    int front;
    stack<int> st1, st2;
    MyQueue() {

    }
    
    void push(int x) {
        if(st1.empty()) front = x;
        st1.push(x);
    }
    
    int pop() {
        if(st2.empty()) {
            while(!st1.empty()) {
                st2.push(st1.top());
                st1.pop();
            }
        }
        int tmp = st2.top();
        st2.pop();
        return tmp;
    }
    
    int peek() {
        if(!st2.empty()) return st2.top();
        return front;
    }
    
    bool empty() {
        return st1.empty() && st2.empty();
    }
};

Summary

栈与队列都是简单的线性表结构，不难理解，但是在处理一些问题的时候，也要灵活使用。一般而言，面对对象的程序语言都会封装好类似的容器，所以要熟悉掌握这些容器的使用。与栈相关的经典题型，还有表达式求值问题，与队列相关的问题，还有循环队列等。不过，都是万变不离其宗。