【LeetCode刷题日志】225.用队列实现栈

  • 🎈个人主页：库库的里昂
  •  🎐C/C++领域新星创作者
  •  🎉欢迎 👍点赞✍评论⭐收藏
  • ✨收录专栏：LeetCode 刷题日志
  • 🤝希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！🤗

目录

1.题目描述

2.解题思路+代码实现

方法一：两个队列

思路及算法：

代码实现：

方法二：一个队列

思路及算法：

代码实现：

1.题目描述

OJ链接 【leetcode 题号：225.用队列实现栈】【难度：简单】

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

2.解题思路+代码实现

方法一：两个队列
思路及算法：

为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中q1用于存储栈内的元素，q2作为入栈操作的辅助队列。

入栈操作时，首先将元素入队到q2，然后将q1的全部元素依次出队并入队列q2 ，此时q2的前端的元素即为新入栈的元素，再将q1和q2互换，则q1的元素即为栈内的元素，q1的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保q1的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除q1的前端元素并返回即可，获得栈顶元素操作只需要获得q1的前端元素并返回即可（不移除元素）。

由于q1用于存储栈内的元素，判断栈是否为空时，只需要判断q1是否为空即可。

代码实现：
typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;
 
typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;
 
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("mallloc fail\n");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->ptail == NULL) {
        assert(pq->phead == NULL);
        pq->phead = pq->ptail = newnode;
    }
    else {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->size == 0;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->phead->next == NULL) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}
 
//------以下为OJ提供-------
 
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
 
MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL) {
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
 
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    }
    else {
        QueuePush(&obj->q2, x);
    }
}
 
int myStackPop(MyStack* obj) {
    Queue* pEmptyQ = &obj->q1;
    Queue* pNonEmptyQ = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        pEmptyQ = &obj->q2;
        pNonEmptyQ = &obj->q1;
    }
    while (QueueSize(pNonEmptyQ) > 1) {
        QueuePush(pEmptyQ, QueueFront(pNonEmptyQ));
        QueuePop(pNonEmptyQ);
    }
    int top = QueueFront(pNonEmptyQ);
    QueuePop(pNonEmptyQ);
    return top;
}
 
int myStackTop(MyStack* obj) {
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    }
    else {
        return QueueBack(&obj->q2);
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) &&
        QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

复杂度分析

  • 时间复杂度：入栈操作O(n)，其余操作都是O(1)，其中n是栈内的元素个数。 入栈操作需要将q1中的n个元素出队，并入队n+1个元素到q2，共有2n+1次操作，每次出队和入队操作的时间复杂度都是O(1)，因此入栈操作的时间复杂度是 O(n)。 出栈操作对应将q1的前端元素出队，时间复杂度是 O(1)。 获得栈顶元素操作对应获得q1的前端元素，时间复杂度是O(1)。 判断栈是否为空操作只需要判断q1是否为空，时间复杂度是 O(1)。
  • 空间复杂度：O(n)，其中n是栈内的元素个数。需要使用两个队列存储栈内的元素。
方法二：一个队列
思路及算法：

方法一使用了两个队列实现栈的操作，也可以使用一个队列实现栈的操作。

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 nnn，然后将元素入队到队列，再将队列中的前n个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

代码实现：
typedef struct tagListNode {
    struct tagListNode* next;
    int val;
} ListNode;

typedef struct {
    ListNode* top;
} MyStack;

MyStack* myStackCreate() {
    MyStack* stk = calloc(1, sizeof(MyStack));
    return stk;
}

void myStackPush(MyStack* obj, int x) {
    ListNode* node = malloc(sizeof(ListNode));
    node->val = x;
    node->next = obj->top;
    obj->top = node;
}

int myStackPop(MyStack* obj) {
    ListNode* node = obj->top;
    int val = node->val;
    obj->top = node->next;
    free(node);

    return val;
}

int myStackTop(MyStack* obj) {
    return obj->top->val;
}

bool myStackEmpty(MyStack* obj) {
    return (obj->top == NULL);
}

void myStackFree(MyStack* obj) {
    while (obj->top != NULL) {
        ListNode* node = obj->top;
        obj->top = obj->top->next;
        free(node);
    }
    free(obj);
}

复杂度分析

  • 时间复杂度：入栈操作O(n)，其余操作都是O(1)，其中n是栈内的元素个数。 入栈操作需要将队列中的n个元素出队，并入队n+1个元素到队列，共有2n+1次操作，每次出队和入队操作的时间复杂度都是O(1)，因此入栈操作的时间复杂度是O(n)。 出栈操作对应将队列的前端元素出队，时间复杂度是O(1)。获得栈顶元素操作对应获得队列的前端元素，时间复杂度是O(1)。 判断栈是否为空操作只需要判断队列是否为空，时间复杂度是O(1)。
  • 空间复杂度：O(n)，其中n是栈内的元素个数。需要使用一个队列存储栈内的元素。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/162558.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MFC 对话框

MFC 对话框

目录 一、对话款基本认识 二、对话框项目创建 三、控件操作 四、对话框创建和显示 模态对话框 非模态对话框 五、动态创建按钮 六、访问控件 控件添加控制变量 访问对话框 操作对话框 SendMessage() 七、对话框伸缩功能实现 八、对话框小项目-逃跑按钮 九、小项…
阅读更多...
文章分类列表进行查询（实体类日期格式设置）

文章分类列表进行查询（实体类日期格式设置）

categoryController GetMappingpublic Result<List<Category>> list(){List<Category> cs categoryService.list();return Result.success(cs);} categoryService //列表查询List<Category> list(); categoryServiceImpl Overridepublic List<Cat…
阅读更多...
科研学习|科研软件——面板数据、截面数据、时间序列数据的区别是什么?

科研学习|科研软件——面板数据、截面数据、时间序列数据的区别是什么?

一、数据采集方式不同 面板数据是通过在多个时间点上对同一组体进行观测而获得的数据。面板数据可以是横向面板数据&#xff0c;即对同一时间点上不同个体的观测&#xff0c;也可以是纵向面板数据&#xff0c;即对同一个体在不同时间点上的观测。采集面板数据需要跟踪相同的个体…
阅读更多...
Idea安装完成配置

Idea安装完成配置

目录&#xff1a; 环境配置Java配置Maven配置Git配置 基础设置编码级设置File Header自动生成序列化编号配置 插件安装MyBtisPlusRestfulTooklkit-fix 环境配置 Java配置 Idea右上方&#xff0c;找到Project Settings. 有些版本直接有&#xff0c;有些是在设置下的二级菜单下…
阅读更多...
哈希

哈希

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;那个传说中的man的主页 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;题目大解析&#xff08;3&#xff09; 目录 &#x1f449;&#x1f3fb;unordered系列关联式容器un…
阅读更多...
Java学习 10.Java-类和对象

Java学习 10.Java-类和对象

一、面向对象的初步认知 1.1 什么是面向对象 面向对象是解决问题的一种思想&#xff0c;主要依靠对象之间的交互完成一件事情&#xff0c;用面向对象的思想来设计程序&#xff0c;更符合人们对事物的认知&#xff0c;对于大型程序的设计、拓展以及维护都非常友好 1.2 面向对…
阅读更多...
Redisson 分布式锁实战应用解析

Redisson 分布式锁实战应用解析

文章目录 前言一、Redisson介绍二、Redisson的使用1.1 引入依赖1.2 编写配置1.3 示例测试_011.4 示例测试_02 三、Redisson源码分析2.1 加锁源码2.2 看门狗机制 前言 分布式锁主要是解决分布式系统下数据一致性的问题。在单机的环境下&#xff0c;应用是在同一进程下的&#x…
阅读更多...
2023年【陕西省安全员B证】考试报名及陕西省安全员B证模拟试题

2023年【陕西省安全员B证】考试报名及陕西省安全员B证模拟试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年陕西省安全员B证考试报名为正在备考陕西省安全员B证操作证的学员准备的理论考试专题&#xff0c;每个月更新的陕西省安全员B证模拟试题祝您顺利通过陕西省安全员B证考试。 1、【多选题】《陕西省建设工程质量和…
阅读更多...
运行ps软件提示由于找不到vcruntime140.dll无法继续执行代码怎么修复

运行ps软件提示由于找不到vcruntime140.dll无法继续执行代码怎么修复

今天我在打开ps时候突然电脑出现找不到vcruntime140.dll无法继续执行代码&#xff0c;我很困扰不知道什么原因&#xff0c;于是我花了一天时间在网上找了5个可以解决这个问题的方案分享给大家&#xff0c;同时我自己也解决了问题。分享给大家就是为了大家以后遇到这个问题不用像…
阅读更多...
为什么Transformer模型中使用Layer Normalization（Layer Norm）而不是Batch Normalization（BN）

为什么Transformer模型中使用Layer Normalization（Layer Norm）而不是Batch Normalization（BN）

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️ &#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…
阅读更多...
Vue3-自定义hook函数

Vue3-自定义hook函数

Vue3-自定义hook函数 功能&#xff1a;可以将组合式API封装成一个函数&#xff0c;用于解决代码复用的问题。注意&#xff1a;需要在src文件夹下创建一个文件夹hooks&#xff0c;在里面放js文件&#xff0c;命名随意&#xff0c;主要是将setup函数中的代码放入js文件中。 // s…
阅读更多...
基于token的鉴权机制-JWT

基于token的鉴权机制-JWT

在实际开发项目中&#xff0c;由于Http是一种无状态的协议&#xff0c;我们想要记录用户的登录状态&#xff0c;或者为用户创建身份认证的凭证&#xff0c;可以使用Session认证机制或者JWT认证机制。 什么是JWT? 网络应用环境间传递声明执行的一种基于JSON的开放标准。适用于…
阅读更多...
基于Adapter用CLIP进行Few-shot Image Classification

基于Adapter用CLIP进行Few-shot Image Classification

文章目录 【ECCV 2022】《Tip-Adapter: Training-free Adaption of CLIP for Few-shot Classification》【NeuIPS 2023】《Meta-Adapter: An Online Few-shot Learner for Vision-Language Model》 【ECCV 2022】《Tip-Adapter: Training-free Adaption of CLIP for Few-shot C…
阅读更多...
第一次组会汇报（2023/11/18）

第一次组会汇报（2023/11/18）

目录 一&#xff0c;浅谈学习规划 二&#xff0c; 两个比较典型的注意力机制 ㈠SEnet ⒈结构图 ⒉机制流程讲解 ⒊源码&#xff08;pytorch框架实现&#xff09;及逐行解释 ⒋测试结果 ㈡CBAM ⒈结构图 ⒉机制流程讲解 ⒊源码&#xff08;pytorch框架实现&#xff09;…
阅读更多...
Docker命令

Docker命令

1. 基础命令 # 启动docker systemctl start docker # 关闭docker systemctl stop docker # 开机自启动docker systemctl enable docker 2. 镜像 ● 拉取centos镜像 docker pull 镜像名[:tag] 示例&#xff1a;docker pull centos:centos7 ● 查看本地主机所有镜像 docker i…
阅读更多...
【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

前言 随机链表的复制涉及到复制一个链表&#xff0c;该链表不仅包含普通的next指针&#xff0c;还包含random指针&#xff0c;该指针指向链表中的任意节点或空节点。 文章目录 原地修改链表 题目链接&#xff1a; LeetCode 138. 随机链表的复制 原地修改链表 题目介绍&#xf…
阅读更多...
OpenAI的多函数调用（Multiple Function Calling)简介

OpenAI的多函数调用（Multiple Function Calling)简介

我在六月份写了一篇关于GPT 函数调用&#xff08;Function calling) 的博客https://blog.csdn.net/xindoo/article/details/131262670&#xff0c;其中介绍了函数调用的方法&#xff0c;但之前的函数调用&#xff0c;在一轮对话中只能调用一个函数。就在上周&#xff0c;OpenAI…
阅读更多...
Java中的集合内容总结——Collection接口

Java中的集合内容总结——Collection接口

集合概述 Java 集合可分为 Collection 和 Map 两大体系&#xff1a; Collection接口&#xff1a;用于存储一个一个的数据。 List子接口&#xff1a;用来存储有序的、可以重复的数据&#xff08;主要用来替换数组&#xff0c;"动态"数组&#xff09; 实现类&#xf…
阅读更多...
python的文件目录操作 1

python的文件目录操作 1

我们在实际开发中&#xff0c;经常需要对文件进行读取、遍历、修改等操作&#xff0c;通过 python 的标准内置os模块&#xff0c;能够以简洁高效的方式完成这些操作。常见的操作整理如下&#xff1a; 文件夹操作&#xff1a;包括文件夹的创建、修改&#xff08;改名/移动&…
阅读更多...
JS进阶——深入面向对象

JS进阶——深入面向对象

1、编程思想 1.1 面向过程编程 面向过程就是分析出解决问题所需要的步骤&#xff0c;然后用函数把这些步骤一步一步实现&#xff0c;使用的时候再一个一个的一次调用就可以了。 1.2 面向对象编程&#xff08;oop&#xff09; 面向对象是把事务分解成为一个个对象&#xff0c;然…
阅读更多...
最新文章

Copyright @ 2022~2023