算法训练营Day 10

232. 用栈实现队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/
文章讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

考察点：栈和队列

不需要每次都将stOut放回stIn, 只要判断下out为空的时候在吧in放进去就行。

class MyQueue {
public:
    stack<int> stIn, stOut;
    MyQueue() {
    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        int res = this->peek();
        stOut.pop();
        return res;
    }
    
    int peek() {
        int res;
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        res = stOut.top();
        return res;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

225. 用队列实现栈

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/
文章讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

考察点：栈和队列

只需要一个队列，每次pop出来再放回队尾。

class MyStack {
private:
    queue<int> q1;

public:
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        int size = q1.size();
        for(int i=0; i<q1.size()-1;++i){
            q1.push(q1.front());
            q1.pop();
        }
        int r = q1.front();
        q1.pop();
        return r;
    }
    
    int top() {
        int r = this->pop();
        q1.push(r);
        return r;
    }
    
    bool empty() {
        return q1.empty();
    }
};