02 栈和队列

232 用栈实现队列 (opens new window)

尝试使用栈（stack）来实现队列（queue）。

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false

解析：

​ 本题可以使用两个方向相反的栈实现一个队列如下图所示，其中箭头表示元素 pop 方向

​ 使用两个栈的目的是：为了达到先入先出的效果，需要有一个栈用来翻转输入到栈中数组元素的顺序。这个翻转过程既可以在插入时完成，也可以在取值时完成。

​ 在输入时进行反转：当所有元素都压栈进入 in 栈之后，将所有元素先入后出地压入 out 栈翻转数组。

​ 在取值时进行反转：每次取值时，如果out非空则直接取栈顶；如果 out 栈为空，先将 in 栈中的元素全部先入后出压入 out 栈中，再从 out 栈中出栈元素。

class MyQueue {

private:
    // < out | in <
    stack<int> out;
    stack<int> in;

public:
    MyQueue() {}
    
    void push(int x) {
        in.push(x);
    }

    void connectOutIn(){
        if(out.empty()){
            while(!in.empty()){
                int tail = in.top();
                in.pop();
                out.push(tail);
            }
        }
    }
    
    int pop() {
        connectOutIn();
        int tail = out.top();
        out.pop();
        return tail;
    }
    
    int peek() {
        connectOutIn();
        return out.top();
    }
    
    bool empty() {
        return out.empty()&&in.empty(); 
    }
};

225 用队列实现栈 (opens new window)

尝试使用队列（queue）来实现栈（stack）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

解析：

​ 本题可以使用两个队列，主队列 q1 和辅助队列 q2，q1 保存当前所有元素，q2 用来在压入新元素时将该元素 q1 中已存在的元素之前。核心思想就是将新元素放到就元素之前形成先入后出。

​ 主要考虑压入新元素的过程：

• 有新元素要入栈，现将该元素压入辅助队列 q2
• 将 q1 中的所有元素依次压入已经压入新元素的 q2 中，翻转出队列顺序
• 将 q2 中的所有元素按次序压入到 q1 中，这一过程也可以直接使用 swap 交换
• 完成新元素压入操作

class MyStack {

private:
    queue<int> q1;
    queue<int> q2;
public:
    MyStack() {

    }
    
    void push(int x) {
        q2.push(x);
        while(!q1.empty()){
            q2.push(q1.front());
            q1.pop();
        }
        // swap(q1,q2);
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
    }
    
    int pop() {
        int val = q1.front();
        q1.pop();
        return val;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};

155 最小栈 (opens new window)

设计一个最小栈，除了需要支持常规栈的操作外，还需要支持在 O(1) 时间内查询栈内最小值的功能。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

解析：

​ 一种简单的思路是建立一个记录栈内当前最小值的辅助栈：每次插入原栈时，都向辅助栈插入一次原栈里当前所有值的最小值，即为辅助栈栈顶和待插入值中较小的那一个；每次从原栈里取出数字时，同样取出新栈的栈顶。

class MinStack {

private:
    stack<int> s, min_s;

public:
    MinStack() {
        min_s.push(INT_MAX);
    }
    
    void push(int val) {
        min_s.push(min(min_s.top(),val));
        s.push(val);
    }
    
    void pop() {
        min_s.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return min_s.top();
    }
};

​ 采用上述策略简化了判断，但是每次都要插入和取出，提高了时间复杂度。可以增加判断条件，减少辅助栈插入取出的操作：每当在原栈里插入一个数字时，若该数字小于等于辅助栈栈顶，则表示这个数字在原栈里是最小值，我们将其同时插入辅助栈内。每当从原栈里取出一个数字时，若该数字等于辅助栈栈顶，则表示这个数是原栈里的最小值之一，同时取出辅助栈栈顶的值。

20 有效的括号 (opens new window)

给定一个只由左右原括号、花括号和方括号组成的字符串，求这个字符串是否合法。合法的定义是每一个类型的左括号都有一个右括号一一对应，且括号内的字符串也满足此要求。

输入是一个字符串，输出是一个布尔值，表示字符串是否合法。

输入：s = "()[]{}"
输出：true

解析：

​ 括号匹配是典型的使用栈来解决的问题。从左往右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符串不合法。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(const auto c: s){
            if(c=='(' || c=='[' || c=='{'){
                st.push(c);
            }else{
                if(st.empty()){
                    return false;
                }
                if(c==')' && st.top()=='('){
                    st.pop();
                }else if(c==']' && st.top()=='['){
                    st.pop();
                }else if(c=='}' && st.top()=='{'){
                    st.pop();
                }else{
                    return false;
                }
            }
        }
        return st.empty();
    }
};