[数据结构与算法]leetcode 255 用队列实现栈

前言

题目：225. 用队列实现栈

参考题解：用队列实现栈-代码随想录

提交代码

用队列来模拟栈。模拟分为两种：一种是内涵模拟，即内部结构相似，外部接口相同；另一种是接口模拟，只有接口相同，内部逻辑可以千差万别。

这里，仅仅使用队列来模拟栈的接口。难度在于，队列是先入先出，如何操作最后一个进入的元素，以达到模拟栈的效果。

核心思路很简单，将非最后一个元素全部弹出再进入队列，则满足最后一个元素在最前方。

下面的代码可以优化。优化方向是仅使用一个队列。

#include <queue>
#include <cassert>

using namespace std;

class MyStack {
private:
    queue<int> qOne;
    queue<int> qTwo;
public:
    void moveKeepOne(queue<int>& src,queue<int>& des){
        // assert(des.empty());
        int n = src.size();
        for(int i=0; i<n-1; i++){
            des.push(src.front());
            src.pop();
        }
    }

    /** Initialize your data structure here. */
    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {
        qOne.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        assert(!this->empty());
        int result;
        if(qOne.empty()){ // 此时元素已全部在Q2中；Q2保留最后一个元素，其他全部转移到Q1中
            moveKeepOne(qTwo,qOne);
            result = qTwo.front();
            qTwo.pop();
        }else if(qOne.size()==1){ // 此时Q1中只有一个元素，它是最后一个push入的元素
            result = qOne.front();
            qOne.pop();
        }else{ // 多于一个元素的时候，非最后一个元素移入Q2中
            moveKeepOne(qOne,qTwo);
            result = qOne.front();
            qOne.pop();
        }

        return result;
    }
    
    /** Get the top element. */
    int top() {
        assert(!this->empty());
        int result = this->pop();
        this->push(result);
        return result;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return qOne.empty() && qTwo.empty();
    }
};