【代码随想录37期】Day10 用栈实现队列、用队列实现栈

用栈实现队列

代码随想录

232. 用栈实现队列 - 力扣（LeetCode）

v1.0:30分钟写出来的，主要是api不是很了解，重点是pop的逻辑，
要检查输出栈的内容，避免插队
class MyQueue {
public:
        stack<int, deque<int>> s1;
        stack<int, deque<int>> s2;
    MyQueue() {
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        int num;

        if(!s2.empty())
        {
            num = s2.top();
            s2.pop();
        }
        else
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            num = s2.top();
            s2.pop();
        }
        return num;
    }
    
    int peek() {
        if(!s2.empty())
        {
            return s2.top();
        }
        else
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
            return s2.top();
        }
    }
    
    bool empty() {
        return s2.empty()&&s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

代码随想录

初版代码：根据自己思路实现的，确保pop时一个队列为空，然后将另一个队列的元素都移动到该队列，只留下最后一个元素

v1.0
class MyStack {
public:
    queue<int, deque<int>> q1;
    queue<int, deque<int>> q2;

    MyStack() {

    }
    
    void push(int x) {
        if(q1.empty())
        {
            q2.push(x);
        }
        else
        {
            q1.push(x);
        }
    }
    int q2q(queue<int> &q1, queue<int> &q2){
        int ret, size = q1.size()-1;
        //将q1的元素移到q2，仅剩队尾元素留在q1,返回队尾元素的值
        while(size--)
            {
                q2.push(q1.front());
                q1.pop();
            }
            ret = q1.front();
        return ret;
    }
    
    int pop() {
        int num;
        if(q1.empty())
        {
            num = q2q(q2, q1);
            q2.pop();
            return num;
        }
        else
        {
            num = q2q(q1, q2);
            q1.pop();
            return num;
        }
    }
    
    int top() {
        int num = this->pop();
        this->push(num);
        return num;
    }
    
    bool empty() {
        return q1.empty()&&q2.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

v2.0：

第二版代码，使用了q1 = q2；再清空q2的做法，避免了很多q1和q2来回交换的做法，明确了q1和q2的职责

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

class MyStack {
public:
    queue<int, deque<int>> q1;
    queue<int, deque<int>> q2;//辅助队列

    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() 
    {
        int num, size = q1.size()-1;
        //将q1的元素移到q2，仅剩队尾元素留在q1,返回队尾元素的值
        while(size--)
        {
            q2.push(q1.front());
            q1.pop();
        }
        num = q1.front();
        q1.pop();
        q1 = q2;
        while(!q2.empty()){
            q2.pop();
        }
        return num;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

v3.0:第三版代码，去掉了队列2的使用，将队列除了尾部元素之外重新入队，即可将原本的队尾元素移动到队首，从而去掉该元素。

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

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() 
    {
        int num = q1.back(), size = q1.size()-1;
        //将q1的元素移到q1尾部，仅剩原本的队尾元素留在q1头部,再pop
        while(size--)
        {
            q1.push(q1.front());
            q1.pop();
        }
        q1.pop();
        return num;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */