当前位置: 首页 > 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;…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...