【算法与数据结构】232、LeetCode用栈实现队列

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】232、LeetCode用栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】232、LeetCode用栈实现队列,算法,算法
【算法与数据结构】232、LeetCode用栈实现队列,算法,算法

二、解法

  思路分析:这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只用一个栈是无法实现,需要两个栈,一个输入栈,一个输出栈。输入栈当中,先进栈的元素在栈底所以后出,此时我们将输入栈的元素push进输出栈,先进的元素就在栈顶,会先输出,这样就实现了先进先出的队列。peek函数复用了pop函数,实现代码缩减。最后empty函数,只要输入栈和输出栈同时为空那么队列就是空的。
  程序如下

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() { // 构造函数

    }

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if (stOut.empty()) {   // 只有当Out栈为空的时候,才将In栈的元素全部导入Out栈
            while (!stIn.empty()) { 
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    int peek() {
        int res = this->pop();  // 直接使用已经写好的pop函数
        stOut.push(res);        // 已经弹出,再添加回去
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

复杂度分析:

  • 时间复杂度: push和empty为 O ( 1 ) O(1) O(1), pop和peek为 O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <stack>
using namespace std;

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() { // 构造函数

    }

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if (stOut.empty()) {   // 只有当Out栈为空的时候,才将In栈的元素全部导入Out栈
            while (!stIn.empty()) { 
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    int peek() {
        int res = this->pop();  // 直接使用已经写好的pop函数
        stOut.push(res);        // 已经弹出,再添加回去
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

int main()
{
    int x = 10;
    MyQueue* obj = new MyQueue();
    obj->push(x);
    obj->push(x);
    int param_2 = obj->pop();
    int param_3 = obj->peek();
    bool param_4 = obj->empty();
	system("pause");
	return 0;
}

end文章来源地址https://www.toymoban.com/news/detail-531235.html

到了这里,关于【算法与数据结构】232、LeetCode用栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【leetcode】232. 用栈实现队列

    1.使用两个栈结构构建队列 我们需要自定义栈及其相关操作 栈结构遵循后入先出的原则,队列结构遵循先入先出的原则 构建具有两个栈结构的队列,栈pushST用于数据的插入,栈popST用于数据的删除 为栈结构动态开辟空间并初始化栈结构 2.入队操作 模拟入队操作,即将所有元

    2024年02月12日
    浏览(42)
  • leetcode 232.用栈实现队列

    🌟 leetcode链接:用栈实现队列 1️⃣ 思路和图解: push: pop: peek: 和 pop 类似。 代码: ✨ 栈和队列相关接口代码(可复制): 【数据结构】栈和队列

    2024年02月13日
    浏览(36)
  • 【创作赢红包】LeetCode:232. 用栈实现队列

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列

    2023年04月12日
    浏览(40)
  • 【用队列实现栈】【用栈实现队列】Leetcode 232 225

    ---------------🎈🎈题目链接 用队列实现栈🎈🎈------------------- ---------------🎈🎈题目链接 用栈实现队列🎈🎈-------------------

    2024年01月20日
    浏览(42)
  • LeetCode 232.用栈实现队列(详解) (๑•̌.•๑)

    创建两个栈,一个用于入数据,一个用于出数据。分别是pushST和popST; 1.如果是入数据就直接入进pushST 2.如果是出数据,先检查popST中有无数据,如果有数据,就直接出。如果没数据,就将pushST中的数据放进popST中,再从popST中出数据。 当pushST中的数据入到popST时,数据是顺序的

    2024年01月24日
    浏览(38)
  • Day10|LeetCode232.用栈实现队列、LeetCode 225. 用队列实现栈

    栈和队列理论基础: 队列是先进先出,栈是先进后出。如图所示: 栈和队列是STL(C++标准库)里面的两个数据结构。 栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。  栈的内部结构,

    2024年02月14日
    浏览(37)
  • 栈和队列OJ题:LeetCode--232.用栈实现队列

    朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--232.用栈实现队列 数 据 结 构 专 栏:数据结构 个    人   主    页 :stackY、 LeetCode 专  栏 :LeetCode刷题训练营 LeetCode--232.用栈实现队列:https://leetcode.cn/problems/implement-queue-using-stacks/ 目录 1.题目介绍 2.实例演示

    2024年02月05日
    浏览(47)
  • Leetcode的AC指南 —— 栈与队列:232.用栈实现队列

    摘要: **Leetcode的AC指南 —— 栈与队列:232.用栈实现队列 **。题目介绍:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int

    2024年01月20日
    浏览(40)
  • 数据结构-用栈实现队列

    前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否

    2023年04月08日
    浏览(88)
  • 【数据结构】用栈实现队列

    前言:本节博客分享了用栈实现队列效果的思路以及代码,有需要借鉴即可。 LINK 如果要用栈实现队列,我们直到栈是先入后出的一个效果,所以我们可以用两个栈,这样逆转两次数不就是入栈之前数组的顺序嘛。下面是一些图辅助理解: 完。

    2024年03月10日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包