代码随想录算法训练营第10天 | 232.用栈实现队列、225. 用队列实现栈

发布于 2022-11-25  455 次阅读


232. 用栈实现队列 - 力扣(LeetCode)

思路:用两个栈来实现队列大体上的思路是一个栈专门用来输入数据,一个栈A专门用来输入,一个栈B专门用来输出,push的时候直接把值输入到栈A就可以了。但是输出数据要麻烦点,因为队列是先进先出的,所以得先把数据从栈A中取出来,然后把数据存到栈B中,接着再取出来,起到一个类似翻转的效果,这样末尾(栈A底)的数据就变成了头部(栈B顶)的数据了。需要注意的是,如果栈B中已经有数据就直接把数据输出,没有数据才需要把栈A中的数据全部转移到栈B,否则会导致顺序错乱

技巧:贴出来的AC代码是看过标准答案以后改进过的,所以整体思路上和标准答案很像,主要改动是在peek()的优化上,起初是我把pop()的代码直接粘过来改改,后来看了标准答案才发现可以直接复用,这样让代码更加简洁明了,bug也比较好改

我的AC代码

class MyQueue {
public:
    MyQueue() {

    }

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

    int pop() {
        int ans;
        if(!_rstack.empty()) {
            ans = _rstack.top();
            _rstack.pop();
        }
        else {
            while(!_lstack.empty()) {
                _rstack.push(_lstack.top());
                _lstack.pop();
            }
            ans = _rstack.top();
            _rstack.pop();
        }
        return ans;
    }

    int peek() {
        int ans = this->pop();
        _rstack.push(ans);
        return ans;
    }

    bool empty() {
        return _lstack.empty() && _rstack.empty();
    }
private:
    stack<int> _lstack;
    stack<int> _rstack;
};

标准答案

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候,再从stIn里导入数据(导入stIn全部数据)
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res,所以再添加回去
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

225. 用队列实现栈 - 力扣(LeetCode)

思路:两个队列实现方法,一个队列A用来操作,一个队列B用来备份数据,还需要设置一个_size参数来存储队列A的长度。push()的时候直接存入队列A,pop()的时候先取出_size - 1个值,然后将这些值暂存入队列B,再读取最后一个值的数据,接下来再删除这个值并且把队列B中暂存的值全部存回队列A。top()直接返回栈A末尾的元素即可,empty()则直接看队列A是不是空的就行了,因为队列B只是用来临时备份,并不参与实际存储。

  • 我是小丑,原来队列自带size这个属性,没必要自己再设置一个,又是画蛇添足的一天
  • 如果想要只用一个队列实现栈,只需要在弹出的时候将弹出数据再重新添加回栈即可

我的AC代码

class MyStack {
public:
    MyStack() {
        _size = 0;
    }

    void push(int x) {
        qcontrol.push(x);
        _size++;
    }

    int pop() {
        int ans;
        int cnt = _size - 1;
        while(cnt--) {
            qstorage.push(qcontrol.front());
            qcontrol.pop();
        }
        ans = qcontrol.front();
        qcontrol.pop();
        while(!qstorage.empty()) {
            qcontrol.push(qstorage.front());
            qstorage.pop();
        }
        if(_size > 0) {
            _size--;
        }
        return ans;
    }

    int top() {
        int ans = qcontrol.back();
        return ans;
    }

    bool empty() {
        return qcontrol.empty();
    }
private:
    queue<int> qcontrol;
    queue<int> qstorage;
    int _size;
};

复刻标准答案只用一个队列的做法

class MyStack {
public:
    MyStack() {
    }

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

    int pop() {
        int ans;
        int cnt = qcontrol.size() - 1;
        while(cnt--) {
            qcontrol.push(qcontrol.front());
            qcontrol.pop();
        }
        ans = qcontrol.front();
        qcontrol.pop();
        return ans;
    }

    int top() {
        int ans = qcontrol.back();
        return ans;
    }

    bool empty() {
        return qcontrol.empty();
    }
private:
    queue<int> qcontrol;
};

标准答案

正常做法(用两个队列)

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列,用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2,但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

空间复杂度直线降低法(只用一个队列)

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {

    }
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    /** Get the top element. */
    int top() {
        return que.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};