(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓ 剑指 Offer 09. 用两个栈实现队列

难度:简单

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”]
[[],[3],[],[],[]]
输出:[null,null,3,-1,-1]

示例 2:

输入:
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

提示

  • 1 < = v a l u e s < = 10000 1 <= values <= 10000 1<=values<=10000
  • 最多会对 appendTaildeleteHead 进行 10000 次调用

💡思路:

用两个栈来实现一个队列,完成队列的 appendTail deleteHead 操作。

  • in 栈用来处理入栈(push)操作,out 栈用来处理出栈(pop)操作;
  • 一个元素进入 in 栈之后,出栈的顺序被反转。当元素要出栈时,需要先进入 out 栈,此时元素出栈顺序再一次被反转,因此出栈顺序就和最开始入栈顺序是相同的,先进入的元素先退出,这就是队列的顺序。
    (栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】,LeetCode,leetcode,算法,职场和发展

🍁代码:(C++、Java)

C++

class CQueue {
private:
    stack<int> in, out;

    void in2out(){
        while(!in.empty()){
            out.push(in.top());
            in.pop();
        }
    }

public:
    CQueue() { }
    
    void appendTail(int value) {
        in.push(value);
    }
    
    int deleteHead() {
        if(out.empty()){
            if(in.empty()) return -1;
            in2out();
        }
        int ans = out.top();
        out.pop();
        return ans;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

Java

class CQueue {
    private Stack<Integer> in = new Stack<Integer>();
    private Stack<Integer> out = new Stack<Integer>();

    private void in2out(){
        while(!in.isEmpty()){
            out.push(in.pop());
        }
    }

    public CQueue() { }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if(out.isEmpty()){
            if(in.isEmpty()) return -1;
            in2out();
        }
        return out.pop();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */
🚀 运行结果:

(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】,LeetCode,leetcode,算法,职场和发展

🕔 复杂度分析:
  • 时间复杂度appendTail O ( 1 ) O(1) O(1)deleteHead 为均摊 O ( 1 ) O(1) O(1)。对于每个元素,至多入栈和出栈各两次,故均摊复杂度为 O ( 1 ) O(1) O(1)

  • 空间复杂度 O ( n ) O(n) O(n),其中 n 是操作总数。对于有 nappendTail 操作的情况,队列中会有 nnn 个元素,故空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-583863.html

注: 如有不足,欢迎指正!

到了这里,关于(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (链表) 剑指 Offer 52. 两个链表的第一个公共节点 ——【Leetcode每日一题】

    难度:简单 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则

    2024年02月15日
    浏览(52)
  • Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】

    实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3: 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -10

    2024年02月13日
    浏览(38)
  • Leetcode-每日一题【剑指 Offer 29. 顺时针打印矩阵】

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] 限制: 0 = matrix.length = 100 0 = matrix[i].length = 100 1.题目要求

    2024年02月13日
    浏览(57)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • (字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

    难度:简单 请实现一个函数,把字符串 s 中的每个 空格 替换成 “ %20 ”。 示例 1: 输入:s = “We are happy.” 输出:“We%20are%20happy.” 限制 : 0 = s 的长度 = 10000 💡思路:双指针法 如果想把这道题目做到 极致 ,就不要只用额外的辅助空间了! 首先扩充数组到每个空格替换

    2024年02月08日
    浏览(62)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • Leetcode-每日一题【剑指 Offer 26. 树的子结构】

    输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A:      3     /    4   5   /  1   2 给定的树 B:    4    /  1 返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点

    2024年02月13日
    浏览(55)
  • Leetcode-每日一题【剑指 Offer 06. 从尾到头打印链表】

    输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 输入: head = [1,3,2] 输出: [2,3,1] 限制: 0 = 链表长度 = 10000 1.题目要求我们从尾到头反过来返回每个节点的值,这道题我们可以用栈去解决,但是我们还可以采用另一种方法。就是我们可以

    2024年02月13日
    浏览(34)
  • Leetcode-每日一题【剑指 Offer 27. 二叉树的镜像】

    请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入:      4    /     2     7  /   / 1   3 6   9 镜像输出:      4    /     7     2  /   / 9   6 3   1 示例 1: 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 限制: 0 = 节点个数 = 1000 1.题目要求我们设

    2024年02月13日
    浏览(41)
  • Leetcode-每日一题【剑指 Offer 13. 机器人的运动范围】

    地上有一个m行n列的方格,从坐标  [0,0]  到坐标  [m-1,n-1]  。一个机器人从坐标  [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为

    2024年02月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包