代码随想录刷题第十天

正式开启栈与队列！首先了解了栈和队列的原理与底层实现，第一题是用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/，求助卡哥代码随想录。用了两个栈来模拟队列，一个进一个出。语法不熟悉，还是要对着卡哥代码敲一遍。

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {

    }
    
    void push(int x) {
    stIn.push(x);
    }
    
    int pop() {
        if (stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    int peek() {
    if (stOut.empty()){
        while(!stIn.empty()){
            stOut.push(stIn.top());
            stIn.pop();
        }
    }
    int result = stOut.top();
    return result;
    }
    
    bool empty() {
    return stIn.empty() && stOut.empty();
    }
};

另外学到了函数的复用

int peek(){
         int result = this -> pop();
         stdOut.push(result);
         return result;
}

第二题是用队列模拟栈https://leetcode.cn/problems/implement-stack-using-queues/description/，只想到了用两个队列模拟栈。

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

    void push(int x) { q1.push(x); }

    int pop() {
        int size = q1.size();
        size--;
        while (size--) {
            q2.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        return result;
    }

    int top() { return q1.back(); }

    bool empty() { return q1.empty(); }
};

其实两个队列完全没必要，把一个栈里前面的元素放到back处就行。q2队列纯纯画蛇添足。

class MyStack {
public:
    queue<int> q1;
    MyStack() {}

    void push(int x) { q1.push(x); }

    int pop() {
        int size = q1.size();
        size--;
        while (size--) {
            q1.push(q1.front());
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        return result;
    }

    int top() { return q1.back(); }

    bool empty() { return q1.empty(); }
};

今天的内容较少，主要学习了栈与队列的基础操作，栈的push，pop，取栈顶元素top，队列中push，pop，取队头元素front与队末元素back。了解了栈与队列的实现机制，完成了两者的转化。