12-用栈实现队列

自己的做法

算法思想

和 用队列实现栈的思想类似。

两个栈，一个为主栈，一个为辅助栈。

插入数据时，依次执行以下操作：

1. 将主栈所有元素依次弹栈并添加到辅助栈中
2. 将待插入数据添加到辅助栈
3. 将辅助栈元素依次弹栈添加到辅助栈

插入操作完成。

算法实现

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

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        while (!main_stack.empty()) {
            stack.push(main_stack.top());
            main_stack.pop();
        }
        stack.push(x);

        while (!stack.empty()){
            main_stack.push(stack.top());
            stack.pop();
        }


    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int top = main_stack.top();
        main_stack.pop();
        return top;
    }

    /** Get the front element. */
    int peek() {
        return main_stack.top();
    }

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

性能分析

时间复杂度

插入操作为$O(n)$，其余操作都为$O(1)$。

空间复杂度：除了要求的两个栈，没有使用其他空间，$O(1)$。