您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

栈和队列(二) : 用栈实现队列

leetcode232.用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

使用栈实现队列的下列操作:

push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。

示例:
示例
说明及进阶

思路

使用栈来模式队列的行为,如果仅仅用一个栈,是一定不行的,所以需要两个栈一个输入栈,一个输出栈,这里要注意输入栈和输出栈的关系。

在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。

在代码实现的时候,会发现pop() 和 peek()两个函数功能类似,代码实现上也是类似的,可以思考一下如何把代码抽象一下。

C++代码

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

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        //push将数据放入输入栈
        stIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        //pop先对stOut判空
        if (stOut.empty())
        {
            //为空则将输入栈中所有元素放入输出栈中
            while (!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        //取输出栈栈顶元素
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    
    /** Get the front element. */
    int peek() {
        //因和pop函数功能类似, 直接复用
        int result = this->pop();
        stOut.push(result); //因为pop中移除了元素,所以这里将其重新添加回去
        return result;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

原文:https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.md

公众号: 代码随想录


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进