当前位置: 首页 > news >正文

[数据结构]OJ用队列实现栈

225. 用队列实现栈 - 力扣(LeetCode)

官方题解:https://leetcode.cn/problems/implement-stack-using-queues/solutions/432204/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/

首先我们要知道

栈是一种后进先出的数据结构,元素从顶端入栈,然后从顶端出栈。

队列是一种先进先出的数据结构,元素从后端入队,然后从前端出队。

这题要求:

typedef struct {} MyStack;MyStack* myStackCreate() {}void myStackPush(MyStack* obj, int x) {}int myStackPop(MyStack* obj) {}int myStackTop(MyStack* obj) {}bool myStackEmpty(MyStack* obj) {}void myStackFree(MyStack* obj) {}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

这里我们将用两种方法来完成这个问题:
 

方法一:两个队列

这个思路类似我们前面的用栈实现队列

我们的思路如下:

我们先创建两个队列,命名为queue1和queue2,queue1用于存储栈内的元素,queue2作为入栈操作的辅助队列。

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

假设此时push入队列一个2:

然后我们再push一个3入队列:

这样我们使用队列的pop就能达成和栈的pop一样的效果

接下来是代码演示:

#define LEN 20
typedef struct queue {int *data;int head;int rear;int size;
} Queue;typedef struct {Queue *queue1, *queue2;
} MyStack;Queue *initQueue(int k) {Queue *obj = (Queue *)malloc(sizeof(Queue));obj->data = (int *)malloc(k * sizeof(int));obj->head = -1;obj->rear = -1;obj->size = k;return obj;
}void enQueue(Queue *obj, int e) {if (obj->head == -1) {obj->head = 0;}obj->rear = (obj->rear + 1) % obj->size;obj->data[obj->rear] = e;
}int deQueue(Queue *obj) {int a = obj->data[obj->head];if (obj->head == obj->rear) {obj->rear = -1;obj->head = -1;return a;}obj->head = (obj->head + 1) % obj->size;return a;
}int isEmpty(Queue *obj) {return obj->head == -1;
}MyStack *myStackCreate() {MyStack *obj = (MyStack *)malloc(sizeof(MyStack));obj->queue1 = initQueue(LEN);obj->queue2 = initQueue(LEN);return obj;
}void myStackPush(MyStack *obj, int x) {if (isEmpty(obj->queue1)) {enQueue(obj->queue2, x);} else {enQueue(obj->queue1, x);}
}int myStackPop(MyStack *obj) {if (isEmpty(obj->queue1)) {while (obj->queue2->head != obj->queue2->rear) {enQueue(obj->queue1, deQueue(obj->queue2));}return deQueue(obj->queue2);}while (obj->queue1->head != obj->queue1->rear) {enQueue(obj->queue2, deQueue(obj->queue1));}return deQueue(obj->queue1);
}int myStackTop(MyStack *obj) {if (isEmpty(obj->queue1)) {return obj->queue2->data[obj->queue2->rear];}return obj->queue1->data[obj->queue1->rear];
}bool myStackEmpty(MyStack *obj) {if (obj->queue1->head == -1 && obj->queue2->head == -1) {return true;}return false;
}void myStackFree(MyStack *obj) {free(obj->queue1->data);obj->queue1->data = NULL;free(obj->queue1);obj->queue1 = NULL;free(obj->queue2->data);obj->queue2->data = NULL;free(obj->queue2);obj->queue2 = NULL;free(obj);obj = NULL;
}

方法二、一个队列

这个思路整体和方法一差不多

使用一个队列时,为了满足栈的特性,即最后入栈的元素最先出栈,同样需要满足队列前端的元素是最后入栈的元素。入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。

先push一个2

再push一个3,记录星插入之前的所有数据

pop出之前的数据

把数据从队列后面入队列

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

简单来说就是把队列当成一个环用,每次都把除了队列末端的元素都出队然后依次加到原本末端元素的后端,这样原本最后的元素就被推到了队列最前端,实现了 Last In First Out

代码实现:

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);
}

相关文章:

[数据结构]OJ用队列实现栈

225. 用队列实现栈 - 力扣(LeetCode) 官方题解:https://leetcode.cn/problems/implement-stack-using-queues/solutions/432204/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/ 首先我们要知道 栈是一种后进先出的数据结构&#xff0c…...

「优选算法刷题」:最长回文子串

一、题目 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 输入:s "babad" 输出:"bab" 解释:"aba"…...

Java项目:41 springboot大学生入学审核系统的设计与实现010

作者主页:舒克日记 简介:Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本大学生入学审核系统管理员和学生。 管理员功能有个人中心,学生管理,学籍信息管理,入学办理管理等。 学生功能有…...

【数据结构与算法】常见排序算法(Sorting Algorithm)

文章目录 相关概念1. 冒泡排序(Bubble Sort)2. 直接插入排序(Insertion Sort)3. 希尔排序(Shell Sort)4. 直接选择排序(Selection Sort)5. 堆排序(Heap Sort)…...

Unity3D学习之XLua实践——背包系统

文章目录 1 前言2 新建工程导入必要资源2.1 AB包设置2.2 C# 脚本2.3 VSCode 的环境搭建 3 面板拼凑3.1 主面板拼凑3.2 背包面板拼凑3.3 格子复合组件拼凑3.4 常用类别名准备3.5 数据准备3.5.1 图集准备3.5.2 json3.5.3 打AB包 4 Lua读取json表及准备玩家数据5 主面板逻辑6 背包…...

前端技术研究越深入,越觉得技术不是决定录用唯一条件。

一、拒绝抬杠 我说技能不是唯一条件,不是说技能不重要,招聘前端条件是1X,其中1是技能,X是其他条件。 如果X条件很优秀,1这个条件可以降格为0.8、0.5,甚至更低。 有人就抬杠,那为啥不招聘清洁工来干前端&…...

vue组件的重新渲染的问题

目录 1.方式1 2.方式2 1.方式1 修改组件上的key属性 Vue是通过diffing算法比较虚拟DOM和真实DOM,来判断新旧 DOM 的变化。key是虚拟DOM对象的标识,在更新显示时key表示着DOM的唯一性。 DOM是否变化的核心是通过判断新旧DOM的key值是否变化&#xff0c…...

opengl 学习(二)-----你好,三角形

你好&#xff0c;三角形 分类demo效果解析 分类 opengl c demo #include "glad/glad.h" #include "glfw3.h" #include <iostream> #include <cmath> #include <vector>using namespace std;/** * 在学习此节之前&#xff0c;建议将这…...

mongodb4.2升级到5.0版本,升级到6.0版本, 升级到7.0版本案例

今天一客户想把自己当前使用的mongodb数据库4.2版本升级到7.0版本。难道mongodb能直接跳跃升级吗? 经过几经查找资料&#xff0c;貌似真不行呀。确定升级流程如下: 还得从mongo4.2升级到5.0。其次再从5.0升级到6.0。最后再从6.0升级到7.0。 开始升级之前将数据进行备份 这一步…...

CPU处理器模式与异常

ARM架构中的Exception Level&#xff08;EL&#xff09; 在ARM架构中&#xff0c;Exception Level&#xff08;EL&#xff09;是一个关键概念&#xff0c;它表示了处理器当前处理异常或中断的层次。ARMv8-A架构定义了四个Exception Levels&#xff1a;EL0、EL1、EL2和EL3&…...

Day 53 |● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和

1143.最长公共子序列 class Solution { public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()1,vector<int>(text2.size()1,0));int res 0;for(int i 1; i < text1.size(); i){for(int j 1; j <…...

ant-desgin charts双轴图DualAxes,柱状图无法立即显示,并且只有在调整页面大小(放大或缩小)后才开始显示

摘要 双轴图表中&#xff0c;柱状图无法立即显示&#xff0c;并且只有在调整页面大小&#xff08;放大或缩小&#xff09;后才开始显示 官方示例代码 在直接复制&#xff0c;替换为个人数据时&#xff0c;出现柱状图无法显示问题 const config {data: [data, data],xFiel…...

获取别人店铺的所有商品API接口

使用淘宝淘口令接口的步骤通常包括&#xff1a; 注册成为淘宝开放平台的开发者&#xff1a;在淘宝开放平台网站上注册账号并完成认证。 创建应用以获取API密钥&#xff1a;在您的开发者控制台中创建一个应用&#xff0c;并获取用于API调用的密钥&#xff0c;如Client ID和Clie…...

成都正信:亲戚借了钱一直不还怎么委婉的说

在中国传统文化中&#xff0c;亲情关系往往被视为最为重要和敏感的部分。当亲戚间发生借贷时&#xff0c;若出现拖欠不还的情形&#xff0c;处理起来尤为棘手。面对这样的尴尬局面&#xff0c;采取委婉而有效的沟通方式至关重要。 张华最近就遇到了这样的困扰。他的表弟去年因急…...

Truenas入门级教程

Truenas入门教程 前言&#xff1a;系统相关配置 采用I3 4160&#xff0c;采用了2块500G的硬盘&#xff0c;内存为8G&#xff0c;两个网卡只用了其中一个&#xff0c;系统安装的是core版本 硬件采用DELL3020MT机箱&#xff0c;自带3个SATA网口&#xff0c;后期网口不够&#…...

窗口函数dense() over(条件)

力扣题目连接 https://leetcode.cn/problems/rank-scores/ 在 SQL 中&#xff0c;DENSE_RANK() 是一个窗口函数&#xff0c;用于计算结果集中每行的稠密排名&#xff08;dense rank&#xff09;。DENSE_RANK() 函数会为具有相同排序字段值的行分配相同的排名&#xff0c;但不会…...

蓝牙APP开发实现汽车遥控钥匙解锁汽车智能时代

在现代社会&#xff0c;随着科技的不断发展&#xff0c;汽车已经不再是简单的交通工具&#xff0c;而是与智能科技紧密相连的载体。其中&#xff0c;通过开发APP蓝牙程序实现汽车遥控钥匙成为了一种趋势&#xff0c;为车主带来了便捷与安全的体验。虎克技术公司作为行业领先者&…...

第三天 Kubernetes进阶实践

第三天 Kubernetes进阶实践 本章介绍Kubernetes的进阶内容&#xff0c;包含Kubernetes集群调度、CNI插件、认证授权安全体系、分布式存储的对接、Helm的使用等&#xff0c;让学员可以更加深入的学习Kubernetes的核心内容。 ETCD数据的访问 kube-scheduler调度策略实践 预选与…...

redis小结

1.mysql是数据库,redis是数据库&#xff0c;那么什么时候使用应该使用哪种数据库? redis做缓存是为了缓解mysql的压力&#xff0c;在数据库表数据量上千万&#xff0c;并且访问频繁时&#xff0c;mysql压力增大&#xff0c;在有索引的情况下依旧效果不佳&#xff0c;需要使用…...

PHP伪协议详解

PHP伪协议详解 一、前言1.什么是PHP伪协议&#xff1f;2.什么时候用PHP伪协议? 二、常见的php伪协议php://inputphp://filterzip://与bzip2://与zlib://协议data://phar:// 一、前言 1.什么是PHP伪协议&#xff1f; PHP伪协议是PHP自己支持的一种协议与封装协议&#xff0c;…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...