【剑指offer系列题解】

【题目地址】

题目描述

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

• 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.push(3);
queue.pop();   // returns 1
queue.empty(); // returns false
1
2
3
4
5
6
7
8

方法一：栈、队列 O(n)

这道题用两个栈来模拟队列，具体思想如下：

• 栈 s1 专门用来插入元素，它的栈顶等于队列的队尾。
• 栈 s2 专门输出或删除元素，它的栈顶等于队列的队头。

四个函数功能如下：

• push(x)： 每次插入前都将 s2 中的所有元素推入 s1 中，然后再往 s1 插入元素。
• pop()/peek()： 每次删除元素前都将 s1 中所有元素推入 s2 中，然后再删除 s2 的栈顶元素。
• empty()： 判断队列是否为空只用判断 s1 和 s2 是否都为空即可。

我们来模拟一下题目中的例子：

第一步： queue.push(1) ，由于 s2 中元素为空，所以直接往 s1 里插入元素即可。

第二步： queue.push(2) ，同理，直接往 s1 里插入元素。

第三步： queue.peek() ，由于 s1 的栈顶表示队列的队尾，所以要将 s1 中的元素倒到 s2 中，这样就能从 s2 的栈顶直接取到队首元素了。

第四步： queue.push(3) ，由于又要插入元素，为了保证能够保证之后查询及删除操作不会出错，我们需要将 s2 的元素倒回 s1 中，这样就能确保队尾元素是正确的。

第五步： queue.pop() ，由于要删除队首元素，所以要将 s1 中的元素再倒到 s2 中去，然后直接删除栈顶即队首元素即可。

第六步： queue.empty() ，直接判断栈 s1 和 s2 是否为空即可，这里 s2 不为空，所以返回 false 。

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

    }

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

    /** Push element x to the back of queue. */
    void push(int x) {
        copy(s2, s1);
        s1.push(x);
    }

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

    /** Get the front element. */
    int peek() {
        copy(s1, s2);
        return s2.top();
    }

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

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

欢迎大家在评论区交流~