【六分钟学算法-剑指offer系列】8.用两个栈实现队列

这是【六分钟学算法】的第一季，剑指offer系列，作者将利用十五天时间C++实现，带你玩转算法，剑指offer，喜欢的话可以点赞关注＋收藏，每日更新中ing。

---

题目8. 用两个栈实现队列

请用栈实现一个队列，支持如下四种操作：

• push(x) – 将元素x插到队尾；
• pop() – 将队首的元素弹出，并返回该元素；
• peek() – 返回队首元素；
• empty() – 返回队列是否为空；

注意：

• 你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
• 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
• 输入数据保证合法，例如，在队列为空时，不会进行 pop或者 peek等操作；

数据范围
每组数据操作命令数量 [0,100]。

样例

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

【题解】-- 栈、队列

用两个栈来做，一个主栈，用来存储数据；一个辅助栈，用来当缓存。

• push(x)，我们直接将x插入主栈中即可。
• pop()，此时我们需要弹出最先进入栈的元素，也就是栈底元素。我们可以先将所有元素从主栈中弹出，压入辅助栈中。则辅助栈的栈顶元素就是我们要弹出的元素，将其弹出即可。然后再将辅助栈中的元素全部弹出，压入主栈中。
• peek()，可以用和 pop()操作类似的方式，得到最先压入栈的元素。
• empty()，直接判断主栈是否为空即可。

复杂度分析：

push()：O(1)；
pop(): 每次需要将主栈元素全部弹出，再压入，所以需要 O(n) 的时间；
peek()：类似于pop()，需要 O(n) 的时间；
empty()：O(1)；

C++代码实现：

class MyQueue {
public:
    
    stack stk, cache;
    MyQueue() {

    }

    
    void push(int x) {
        stk.push(x);
    }

    void copy(stack &a, stack &b) {
        while (a.size()) {
            b.push(a.top());
            a.pop();
        }
    }

    
    int pop() {
        copy(stk, cache);
        int res = cache.top();
        cache.pop();
        copy(cache, stk);
        return res;
    }

    
    int peek() {
        copy(stk, cache);
        int res = cache.top();
        copy(cache, stk);
        return res;
    }

    
    bool empty() {
        return stk.empty();
    }
};