题解 | 用两个栈实现队列

class Solution
{
public:
    void push(int node) {
        while (!stack2.empty()) {
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack1.push(node);
    }

    int pop() {
        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }
        int data = stack2.top();
        stack2.pop();
        return data;
    }

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

题干信息解读:

本题题目信息其实十分明确,通过两个栈实现类似队列的先入先出机制.对外暴露两个接口即push进队与pop出队(需要返回队头元素值)

个人实现方案:

C++ STL库中已经为我们写好了栈容器,并为我们提供了push压栈方案,我们不妨直接使用.但我们需要实现的是队列,因此还需要进行改进.对于栈而言,先压入的元素在栈最底部,如果我们需要实现队列,就得在下一次调用pop时取到最底部的元素.好在我们刚好还有一个栈(栈2),将前一个栈(栈1)中所有元素依次出栈并压入另一个栈(栈2),此时另一个栈(栈2)最顶部便是原栈(栈1)中的底部元素,这时直接pop出栈即可弹出最先入队的元素.与此同时,如果又需要调用push入队,将栈2中的元素依次弹出压入栈1然后压入新入队的元素即可.于是我们便使用两个栈实现了类似队列的数据结构.

实现代码见上.

注意:

其实题目真实的要求是:

要求：存储n个元素的空间复杂度为  ，插入与删除的时间复杂度都是 

个人的实现方案仅做到了理想状态下(连续多次进行插入删除操作,从第二次操作开始)时间复杂度为O(1),实际运行时如果插入删除操作多次交替执行会导致时间复杂度上升为O(n),因此本解决方案并非完美.

读者若有更好的解决方案,欢迎留言讨论.