day10栈与队列（一）

day10
代码随想录
2023.12.12
补一篇之前的博客。关于栈与队列基础知识的。

1. 232用栈实现队列
其实就是用两个栈模拟入队和出队，入队好说，那出队顺序要与入队顺序相同，所以需要两个栈，一进一出，两次顺序反转，不就和开始顺序顺序相同了嘛？
所以出队的核心思想就是以出队栈为主，若里面有值，则直接弹出即可。如果为空，则需要将入队栈的元素全部按顺序转移到出队栈中。然后弹出出队栈头元素即可。
队列为空就是入队栈和出队栈都为空。

class MyQueue {
public:
    stack<int> s_In;
    stack<int> s_Out;
    MyQueue() {

    }
    
    void push(int x) {
        s_In.push(x);
    }
    
    int pop() {
        if(s_Out.empty()){
            while(!s_In.empty()){
                s_Out.push(s_In.top());
                s_In.pop();
            }
        }
        int result = s_Out.top();
        s_Out.pop();
        return result;
    }
    
    int peek() {
        int result = this->pop();
        s_Out.push(result);
        return result;
    }
    
    bool empty() {
        if(s_Out.empty() && s_In.empty())
            return true;
        return false;
    }
};

2. 225用队列实现栈
如果继续用两个队列实现栈，想一想，入栈还是一样，一个队列（记作队列1）入队即可，那么出栈呢，按理就是队列1的队尾元素，但队列只允许头出，因此需要将队列1的除队尾值外其余所有值全部弹出，保存在队列2，中，因此队列2就是备份的作用。为了保持两个队列的性质，成功弹出值后，将队列2赋值给队列1，然后队列2清空，这样就恢复原始了。此时栈为空只是队列1为空。
所以两个队列能模拟栈，但我们能用一个队列模拟栈为什么要用两个呢？因此进阶一下，用一个队列模拟栈。思考一下，关键就是弹出队尾值时需要按顺序保存之前的所有值，之前是将所有元素放在另一个队列中，那为什么不可将所有元素重新入队呢？这样原来队尾元素就变成队头元素，直接弹出就好，剩下的不就是我们想要的吗？
因此，思路不就理清了。接下来写代码：

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

    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size = que.size();
        size--;  //保证剩下一个，就是原本的队尾元素
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};