LeetCode | 225. 用队列实现栈

我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode-cn.com/problems/implement-stack-using-queues/

题解

class MyStack
{
public:
    queue<int> queue1; //主队列
    queue<int> queue2; //辅助队列
    MyStack()
    {
    }

    void push(int x)
    {
        queue2.push(x);
        while (!queue1.empty())
        {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }

    int pop()
    {
        int r = queue1.front();
        queue1.pop();
        return r;
    }

    int top()
    {
        return queue1.front();
    }

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

思路

队列原则——先进先出

• 队列容器允许从一端输入数据，从另一端删除数据；
• 队列中只有队头front()和队尾back()可以被外界使用，因此队列不允许遍历行为；
• 队列中进数据称为入队push()，出数据称为出队pop()。

队列容器的常用函数

• queue.push()——入队，添加数据
• queue.pop()——出队，删除数据
• queue.front()——获取队头数据
• queue.back()——获取队尾数据
• queue.empty()——判断队列是否为空
• queue.size()——获取队列的大小
• queue.emplace()——在队列的末尾添加一个新元素

上手

总的来说，我们要使用一种先进先出的数据结构去达到一种后进先出的效果。

举个例子，我们现在只能按顺序获取到1, 2, 3, 4四个元素，那么我们怎么才能让遍历完后的效果变成4, 3, 2, 1呢？

1. 新建两个队列，其中一个用来暂存
2. 把新push进来的元素放在队列2中
3. 依次把队列1中的元素push进队列2，并在队列1中删除(pop掉)对应元素
4. 将队列1与队列2互换