用两个栈实现队列

三月 17, 2019

Interview

题目描述

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

主要思路：

最初思路

因为栈和队列最明显的区别就是，栈是先进后出，而队列是先进先出。所以为了满足这个要求，我最初的思路是用stack1来做入队操作，用stack2来做出队操作。

入队，将元素压入stack1
出队，将stack1倒入stack2，弹出栈顶元素，然后再重新倒入stack1

优化思路

最初思路完全只是为了解决这个问题的思路，丝毫没有考虑优化方面。那么仔细思考一下，发现是不是有可以优化的地方呢。首先，最初思路有个小细节可以优化一下，那就是在出队时，stack1的栈底元素可以不用压入stack2（只倒入stack1.size( )-1个元素），可直接弹出作为出队元素返回，这样就可以少做一次压栈操作。

如果是入队操作，判断stack1是否为空，如果不为空，那么就直接压栈；如果为空，就把stack2倒入stack1中，然后再压栈。
如果是出队操作，判断stack2是否为空，如果不为空，那么就直接出栈；如果为空，就把stack1的元素逐个倒入stack2，把最后一个元素弹出并出队。

最后解决方案

上边的思路都有一个问题，那就是stack1和stack2之间频繁的倒来倒去，效率就显得不是那么好。所以再换一种更好的思路，我们始终用stack1做入队操作，用stack2做出队操作。

入队，将元素压入stack1
出队，先判断stack2是否为空，如果不为空，那么弹出stack2的栈顶元素，如果为空，将stack1元素逐个倒入stack2，把最后一个元素弹出并出队。

这个思路避免了反复“倒”栈，仅在需要时才“倒”一次。

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

    int pop() {
        
        int node = -1;
        //两个栈都为空时，队列为空
        if(stack1.empty() == true && stack2.empty() == true){
            cout << "queue is null" << endl;
            return node;
        }else{
            if(stack2.empty() == true){
                //stack2为空 需要把stack1倒入stack2 
                //然后直接把stack1的最后一个元素弹出 可以减少一次压栈操作
                int size1 = stack1.size();
                int length = 0;
                while(stack1.empty() != true && length < size1 - 1){
                    node = stack1.top();
                    stack1.pop();
                    stack2.push(node);
                    cout << "push " << node << " in stack2" << endl;
                    length ++;
                }
                node = stack1.top();
                stack1.pop();
            }else{
                node = stack2.top();
                stack2.pop();
            }
        }
        return node;
    }

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

查看评论

1. 题目描述
2. 主要思路：