算法面试通关40讲 - 栈

20. 有效的括号

std::stack<T>的几个方法：

1. top：相当于back
2. pop：相当于pop_back
3. push: 相当于push_back

class Solution {
public:
    static char leftOf(char c) {
        switch (c) {
            case ')':
                return '(';
            case '}':
                return '{';
            case ']':
                return '[';
            default:
                break;
        }
        return '*';
    }
    bool isValid(string s) {
        stack<char> braces;
        for (char c: s) {
            switch (c) {
                case '(':
                case '[':
                case '{':
                    braces.push(c);
                    break;
                case ')':
                case ']':
                case '}':
                    if (braces.empty() || braces.top() != leftOf(c)) {
                        return false;
                    } else {
                        braces.pop();
                    }
                default:
                    break;
            }
        }
        return braces.empty();
    }
};

232. 用栈实现队列

颠倒栈元素顺序（类似将链表首节点后面的所有节点做一遍头插，参考：25 K 个一组翻转链表）

class MyQueue {
public:
    MyQueue() {}
    void push(int x) {
        in.push(x);
    }
    int pop() {
            dumpInToOut();
        int value = out.top();
        out.pop();
        return value;
    }
    int peek() {
            dumpInToOut();
        return out.top();
    }
    bool empty() {
        dumpInToOut();
        return out.empty();
    }
private:
    void dumpInToOut() {
        if (out.empty()) {
        while (!in.empty()) {
            out.push(in.top());
            in.pop();
        }}
    }
    stack<int> in;
    stack<int> out;
};