题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

初始代码

class Solution
{
public:
    void push(int node) {

    }

    int pop() {

    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

解法1

使用栈来实现队列, 如果说是用C语言来写的话, 会比较麻烦一些. 因为C的栈(自己实现)不像c++ STL中封装好的stack是可以自动扩展栈空间的, 它需要考虑栈满的问题.
观察本题的初始代码, 发现它提供的是C++ STL中的栈, 因而我们在使用的时候也无需担心一直往栈里push数据会不会导致栈满.
所以很自然的一个想法便是:

• 把stack1用来真正存储元素, 在push入队的时候, 直接将元素压入stack1中;
• 当需要出队的时候, 由于队首元素在stack1的栈底, 因此这时候需要借助stack2来倒腾一遍stack1中的元素: 将stack1的元素依次出栈, 并压入stack2中, 直到stack1仅剩一个元素----这个元素就是队首元素. 该元素无需压入stack2, 而是从stack1中出栈后保存在ret返回值中.
• 上一步是出队的第一阶段工作. 完成之后, 要将stack2中的元素再倒回到stack1中. 以照应我们一开始的策略: 仅用stack1来保存元素, stack2只是在出队时需要利用到的一个打工仔.

下面是代码实现:

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int ret;
        // if(stack1.empty()) return 0;
        while(stack1.size() > 1) {
            stack2.push(stack1.top());
            stack1.pop();
        }
        ret = stack1.top();
        stack1.pop();

        while(!stack2.empty()) {
            stack1.push(stack2.top());
            stack2.pop();
        }
        return ret;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

虽然这个实现让心里有点不舒服, 但毕竟是自己的真实水平, 也不好抱怨. 接着继续搜寻题解寻找更优的解题方法, 果不其然, 是有的.

解法2

在解法1的基础上, 进一步考虑如何能够更充分地利用stack2, 而不仅仅把它当个需要时才亲近一下的备胎.
如果让stack1和stack2同时来保存元素可不可行呢?
是可行的.
下面是操作方法:

• 入队时, 仍然是直接将元素压入stack1

• 出队时,

• [1] 如果stack2是空的, 那么和解法1一样, 首先将stack1中的元素依次倒入stack2中, 直到stack1中仅剩一个元素, 然后该元素不倒入stack2, 而是在保存到返回值ret中同时从stack1出栈;

  上面的操作过后, stack2中的元素从栈顶到栈底遍历, 依次就是更新后的队列的队首元素及其之后的元素. 因此, 后续如果还要执行出队操作, 直接从stack2弹出栈顶元素返回即可.

• [2] 如果stack2非空, 说明它之前经历过[1]中的情况, 因此, stack2的栈顶元素对应队列的队首元素, 直接弹出stack2栈顶元素并返回它即可.

解法2在解法1的基础上, 避免了每次出栈时都要来回在stack1和stack2之间折腾, 优化了代码的时间复杂度.

一点点改进: 上面的步骤[1]中, 其实没必要特地给stack1留出最后一个元素, 直接全部元素倒入stack2中, 然后再从stack2中取栈顶元素也是可以的. 这样一来, 就可以把[1][2]两种情况的"弹出stack2栈顶元素并返回它"这一步操作统一了.

下面是代码实现:

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }

        int ret = stack2.top();
        stack2.pop();
        return ret;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};