10-用队列实现栈

自己的做法

算法思想

两个队列，相互交替作为数据栈。每次移除栈顶元素或返回栈顶元素时，就将当前队列数据从队列头部依次弹出，并插入到另一个队列尾部，剩下最后一个元素，如果是移除栈顶元素，则直接返回该元素；如果是返回栈顶元素，则先插入到另一个队列尾部，再返回。

算法思想

class MyStack {
private:
    queue<int> queue1;
    queue<int> queue2;

    queue<int> * stack;
    queue<int> * queue;
    
public:

    /** Initialize your data structure here. */
    MyStack() {
        stack = &queue1;
        queue = &queue2;

    }

    /** Push element x onto stack. */
    void push(int x) {
        stack->push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = stack->size();

        std::queue<int> *temp = stack;
        stack = queue;
        queue = temp;

        for(int i = 0; i < size - 1; i++) {
            stack->push(queue->front());
            queue->pop();
        }

        int top = queue->front();
        queue->pop();
        return top;

    }

    /** Get the top element. */
    int top() {
        int size = stack->size();

        std::queue<int> *temp = stack;
        stack = queue;
        queue = temp;

        for(int i = 0; i < size - 1; i++) {
            stack->push(queue->front());
            queue->pop();
        }

        int top = queue->front();
        stack->push(top);
        queue->pop();
        return top;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return stack->empty();
    }
};

性能分析

• push：直接插入到队列尾部，$O(1)$。
• pop：需要把数据挪到另一个队列中，为$O(n)$。
• top：和pop一样，同样要移动数据，也为$O(n)$。
• empty：$O(1)$。

官方做法

算法思想

栈顶元素应在队列头部。

两个队列，一个是主队列，另一个是辅助队列。当入栈时，执行以下操作：

• 将待入栈元素插入到辅助队列中
• 将主队列元素依次移除并插入到辅助队列中
• 再将辅助队列元素依次移除并插入到主队列中

入栈操作完成。

这样就能始终保持队列头部和栈顶元素一致。

算法实现

class MyStack {
private:
    queue<int> main_queue;
    queue<int> queue;


public:

    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        queue.push(x);
        while (!main_queue.empty()) {
            queue.push(main_queue.front());
            main_queue.pop();
        }
        swap(main_queue, queue);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int top = main_queue.front();
        main_queue.pop();
        return top;
    }

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

    /** Returns whether the stack is empty. */
    bool empty() {
        return main_queue.empty();
    }
};

性能分析

push：需要将主队列数据依次插入辅助队列，再重新插入主队列。为$O(n)$。

其他操作都为$O(1)$。