题目内容

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

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

注意：

• 你只能使用栈的标准操作：$push\enspace to\enspace top$，$peek/pop\enspace from\enspace top$, $size$ 和 $is\enspace 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

思路：

很显然，这是一道模拟题，所以我会对四个操作一一展开讲解。
在讲解前，要先定义两个栈$s1,s2$。

stack <int> s1, s2;

其中，$s1$是主栈，$s2$是过渡栈。

1. $push(x)$

就是主栈$push$进去$x$

s1.push(x)

2. $pop()$

这就稍微有点麻烦了，首先我们要先把主栈里的值压到过渡栈里，像下图一样：

然后我们会发现，$s2$的栈顶就是我们的队头。所以就理所应当的把$s2$的栈顶给抬走，整个$pop$操作就完成了。
哦，对了，可别忘记把$s2$中的数据归还回主栈。

//把主栈的数据压进过渡栈
while (! s1.empty())
{
    int a = s1.top();
    s2.push(a);
    s1.pop();
}
//取出队首元素
int s = s2.top();
//删除队首元素
s2.pop();
//归还
while (!s2.empty())
{
    int a = s2.top();
    s1.push(a);
    s2.pop();
}
//返回被删除的数
return s;

3. $peek()$

$peek$操作其实类似于$pop$操作，只不过不用弹出栈顶元素而已。

while (! s1.empty())
{
    int a = s1.top();
    s2.push(a);
    s1.pop();
}
int s = s2.top();
while (! s2.empty())
{
    int a = s2.top();
    s1.push(a);
    s2.pop();
}
return s;

4. $empty()$

这里用到$C++ \enspace stack$里的函数$empty$，可以用来判断栈是否为空。

return s1.empty();

完整代码：

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

    }

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

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (! s1.empty())
        {
            int a = s1.top();
            s2.push(a);
            s1.pop();
        }
        int s = s2.top();
        s2.pop();
        while (!s2.empty())
        {
            int a = s2.top();
            s1.push(a);
            s2.pop();
        }
        return s;
    }

    /** Get the front element. */
    int peek() {
        while (! s1.empty())
        {
            int a = s1.top();
            s2.push(a);
            s1.pop();
        }
        int s = s2.top();
        while (! s2.empty())
        {
            int a = s2.top();
            s1.push(a);
            s2.pop();
        }
        return s;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.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();
 */

谢谢你能看到这里，祝你$2022RP++$。那我们……

下次再见！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$