leetcode 255 用队列实现栈

迷南。 2022-09-11 00:03 89阅读 0赞

## 前言 ##

题目：[225. 用队列实现栈][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();
        }
    };

[225.]: https://leetcode-cn.com/problems/implement-stack-using-queues/
[-]: https://leetcode-cn.com/problems/implement-stack-using-queues/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-zhan-7wqr/