Leetcode225 用栈实现队列

大众思路：

用两个栈实现，记为s1，s2

1.元素入栈时，加入s1

2.元素出栈时，对s2进行判断，如果s2为空，则将全部s1元素弹出并压入到s2，然后从s2栈顶弹出一个元素；如果s2不为空，则直接从s2的栈顶弹出一个元素

冷门思路：

这种思路效率比较低

1.元素入栈时，加入s1

2.元素出栈时，对s2进行判断，如果s2为空，则将全部s1元素弹出并压入到s2，然后从s2栈顶弹出一个元素；再将元素倒回s1

这样做的缺点是需要在两个栈之间倒来倒去，效率较低。

如下图所示：

我的思路是第一种，C++实现：

class Queue {

public:

    // Push element x to the back of queue.

    void push(int x) {

        stk1.push(x);

    }

    // Removes the element from in front of queue.

    void pop(void) {

        if (stk2.empty()) {

            while (!stk1.empty()) {

                stk2.push(stk1.top());

                stk1.pop();

            }

        }

        stk2.pop();

    }

    // Get the front element.

    int peek(void) {

        if (stk2.empty()) {

            while (!stk1.empty()) {

                stk2.push(stk1.top());

                stk1.pop();

            }

        }

        return stk2.top();

    }

    // Return whether the queue is empty.

    bool empty(void) {

        return stk1.empty()&&stk2.empty();

    }

    stack<int> stk1;

    stack<int> stk2;

};

我的实现中有一个细节没把握好，就是如果两个栈都为空时，我执行了deque操作，将会导致程序崩溃。实际上在执行pop前需要先对队列是否为空进行一次判断。
修正后的pop函数为

    void pop(void) {

        if (!empty()) {

            if (stk2.empty()) {

                while (!stk1.empty()) {

                    stk2.push(stk1.top());

                    stk1.pop();

                }

            }

            stk2.pop();

        }

    }

上述思路，可行性毋庸置疑。但有一个细节是可以优化一下的。即：在出队时，将s1的元素逐个“倒入”s2时，原在s1栈底的元素，不用“倒入”s2（即只“倒”s1.Count()-1个），可直接弹出作为出队元素返回。这样可以减少一次压栈的操作。

巴特西

Leetcode225 用栈实现队列

最新文章

热门文章