225. 用队列实现栈 - 力扣（LeetCode）

这一题需要我们充分理解队列和栈的特点。

队列：队头出数据，队尾入数据。

栈：栈顶出数据和入数据。

我们可以用两个队列实现栈，在这过程中，我们总要保持其中一个队列为空。如果我们出栈，也就是要将栈顶元素弹出，就相当于对非空队列进行操作，就是要把非空队列的队尾元素弹出队列。但是队列的队尾是不能出数据的，想要让队尾数据出队列，就要让这个数据到达队头，同时我们还要保留其他的数据，就需要用到另一个队列来保存。

所以说，我们要用队列模拟出栈过程，就要把非空队列中的数据不断弹出放到另一个队列中，直到非空队列中的数据个数变成1，保留下这个数据的值，再将这个数据从队列中弹出。

对于取栈顶元素过程，大部分代码可以复用出栈的代码。或者我们可以发现栈顶元素就是非空队列的队尾元素，我们直接取出非空队列的队尾元素即可。

对于入栈过程，对于栈，我们直接将数据放到非空队列的队尾即可。

typedef int Qdatatype;typedef struct QueueNode
{Qdatatype data;struct QueueNode* next;
}QueueNode;//队列的结构定义：
typedef struct Queue
{QueueNode* phead;//队头QueueNode* ptail;//队尾int size;//队列中有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁
void QueueDesTroy(Queue* pq)
{QueueNode* pcur = pq->phead;while (pcur){QueueNode* pnext = pcur->next;free(pcur);pcur = pnext;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
//入队列是在队尾入的，所以入队列相当于链表的尾插
void QueuePush(Queue* pq, Qdatatype x)
{assert(pq);//申请新的节点空间QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->next = NULL;newnode->data = x;//尾插//如果此时队列中一个元素都没有if (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//直接头删{QueueNode* newhead = pq->phead->next;free(pq->phead);pq->phead = newhead;}(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;
}//=========前面为队列的实现===========
//栈的结构
typedef struct 
{Queue q1;Queue q2;
} MyStack;//栈的初始化
MyStack* myStackCreate() {MyStack* stack=(MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));QueueInit(&(stack->q2));return stack;
}
//入栈
void myStackPush(MyStack* obj, int x) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}QueuePush(nonempty,x);
}
//出栈
int myStackPop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)!=1)//让非空队列中的元素不停地出栈直到栈中只有一个元素{//将元素放到原来是空的队列中QueuePush(empty,QueueFront(nonempty));//出队列QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}
//取栈顶元素:两种方法
//方法一：
int myStackTop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)!=1)//让非空队列中的元素不停地出栈直到栈中只有一个元素{//将元素放到原来是空的队列中QueuePush(empty,QueueFront(nonempty));//出队列QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePush(empty,ret);QueuePop(nonempty);return ret;
}
//方法二：
int myStackTop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}return QueueBack(nonempty);
}//判断栈是否为空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}
//销毁
void myStackFree(MyStack* obj) 
{QueueDesTroy(&(obj->q1));QueueDesTroy(&(obj->q2));free(obj);obj=NULL;
}

232. 用栈实现队列 - 力扣（LeetCode）

我们是可以用两个栈实现队列的结构的。具体实现方法如下：

我们定义两个栈，一个栈A是专门用来插入数据的，另一个栈B是专门用来出数据的。当我们要插入数据的时候，直接往A中插入即可，当我们要删除数据的时候，要先检查B是否为空，如果B为空，就讲A中的数据全部放入B中，如果B不为空，就直接对B进行出栈操作。

typedef int stdatatype;//定义栈的结构：
typedef struct Stack
{stdatatype* arr;int top;//指向栈顶的后一个位置，也可以表示有效数据个数int capacity;//栈中的最大容量
}ST;
//初始化
void STInit(ST* ps)
{assert(ps);//防止后续空指针解引用ps->arr = NULL;ps->top = 0;//如果使top=0，那么top指向栈顶元素的后一个位置，//如果想让top指向栈顶元素,就要让top初始化为-1ps->capacity = 0;
}//销毁
void STDesTroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈——栈顶
void STPush(ST* ps, stdatatype x)
{assert(ps);//先判断是否需要扩容if (ps->top == ps->capacity){//需要扩容int newcapacity = ps->capacity > 0 ? 2 * ps->capacity : 4;stdatatype*tmp = (stdatatype*)realloc(ps->arr, newcapacity * sizeof(stdatatype));ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[(ps->top)++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈———栈顶
void STPop(ST* ps)
{assert(ps);//出栈之前先判空assert(ps->top);ps->top--;
}//取栈顶元素
stdatatype STTop(ST* ps)
{assert(ps);//去栈顶元素之前先判空assert(ps->top);return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}//================以上全是栈的实现=============
typedef struct 
{ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&(obj->pushst));STInit(&(obj->popst));return obj;
}
void myQueuePush(MyQueue* obj, int x) 
{STPush(&(obj->pushst),x);
}int myQueuePop(MyQueue* obj) 
{if(!STEmpty(&(obj->popst))){int ret=STTop(&(obj->popst));STPop(&(obj->popst));return ret;}else{while(!STEmpty(&(obj->pushst))){STPush(&(obj->popst),STTop(&(obj->pushst)));STPop(&(obj->pushst));}int ret=STTop(&(obj->popst));STPop(&(obj->popst));return ret;}
}int myQueuePeek(MyQueue* obj) 
{if(!STEmpty(&(obj->popst))){int ret=STTop(&(obj->popst));return ret;}else{while(!STEmpty(&(obj->pushst))){STPush(&(obj->popst),STTop(&(obj->pushst)));STPop(&(obj->pushst));}int ret=STTop(&(obj->popst));return ret;}}bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&(obj->pushst)) && STEmpty(&(obj->popst));
}void myQueueFree(MyQueue* obj) 
{STDesTroy(&(obj->pushst));STDesTroy(&(obj->popst));free(obj);
}

622. 设计循环队列 - 力扣（LeetCode）

//我们用数组的结构设计循环队列
//这一题要善于运用模除的运算从而达到利用旧空间的效果
typedef struct {int front;int rear;int*arr;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->rear==obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->rear+1)%(obj->capacity)==obj->front;
}MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue*cirque=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cirque -> front=0;//指向 队头元素（即下一个要出队的元素）。cirque -> rear= 0;//rear指向的是队尾元素的下一个位置cirque -> arr=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间以区分队列满和空的状态cirque->capacity=k+1;return cirque;
}
//尾插
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(!myCircularQueueIsFull(obj)){obj->arr[(obj->rear)++]=value;obj->rear=(obj->rear)%(obj->capacity);return true;}return false;
}
//头删
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return false;}obj->front= ( obj->front+1)%(obj->capacity);return true;
}int myCircularQueueFront(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[(obj->rear-1+obj->capacity)%(obj->capacity)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}

解析：图中我们解释了如何插入和删除元素

设计循环双端队列

双端队列（Deque，Double-Ended Queue）是一种支持 队头（front）和队尾（rear）两端高效插入和删除 的数据结构。

上一题我们实现了循环队列的实现，有了上一题的基础，我们就能利用循环队列来实现双端队列：

//双端队列中：
//front 直接指向当前队头元素（即下一个从队头出队的元素）。
//rear 指向队尾的下一个空位（即下一个插入队尾的位置）。
//在队头插入数据时，要先改变front指向；同理，在队尾插入元素以后，要改变rear的指向
//然而，插入元素后不能同时让front和rear同时递增或同时递减
//我们就使在队头插入数据后，front--，队尾插入数据后rear++typedef struct {int front;int rear;int capacity;int*arr;
} MyCircularDeque;MyCircularDeque* myCircularDequeCreate(int k) 
{MyCircularDeque* obj=(MyCircularDeque*)malloc(sizeof(MyCircularDeque));obj->front=obj->rear=0;obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->capacity=k+1;return obj;
}bool myCircularDequeIsEmpty(MyCircularDeque* obj) 
{return obj->rear==obj->front;
}bool myCircularDequeIsFull(MyCircularDeque* obj) 
{return (obj->rear+1)%(obj->capacity)==obj->front;
}
//头插
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) 
{if(myCircularDequeIsFull(obj)){return false;}//front指向的是队头元素，所以我们再进行头插时，需要先改变队头指向obj->front=(obj->front-1+obj->capacity)%(obj->capacity);obj->arr[obj->front]=value;return true;
}bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) 
{if(myCircularDequeIsFull(obj)){return false;}obj->arr[obj->rear]=value;//改变rear指向obj->rear=(obj->rear+1)%(obj->capacity);return true;
}bool myCircularDequeDeleteFront(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return false;}//插入元素是让front--，那么删除元素就要让front++obj->front=(obj->front+1)%(obj->capacity);return true;
}bool myCircularDequeDeleteLast(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return false;}obj->rear=(obj->rear-1+obj->capacity)%(obj->capacity);return true;
}int myCircularDequeGetFront(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}int myCircularDequeGetRear(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return -1;}return obj->arr[(obj->rear-1+obj->capacity)%(obj->capacity)];
}void myCircularDequeFree(MyCircularDeque* obj) 
{free(obj->arr);obj->arr=NULL;obj->front=obj->rear=obj->capacity=0;free(obj);obj=NULL;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/pingmian/93650.shtml
繁体地址，请注明出处：http://hk.pswp.cn/pingmian/93650.shtml
英文地址，请注明出处：http://en.pswp.cn/pingmian/93650.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Java基础 8.19

Java基础 8.19

目录 1.局部内部类的使用 总结 1.局部内部类的使用 说明：局部内部类是定义在外部类的局部位置，比如方法中，并且有类名可以直接访问外部类的所有成员，包含私有的不能添加访问修饰符，因为它的地位就是一个局部变量。局…
阅读更多...
从父类到子类：C++ 继承的奇妙旅程（2）

从父类到子类：C++ 继承的奇妙旅程（2）

前言：各位代码航海家，欢迎回到C继承宇宙！上回我们解锁了继承的「基础装备包」，成功驯服了public、protected和花式成员隐藏术。但——⚠️前方高能预警： 继承世界的暗流涌动远不止于此！今天我们将勇闯三大神…
阅读更多...
【图像算法 - 16】庖丁解牛：基于YOLO12与OpenCV的车辆部件级实例分割实战（附完整代码）

【图像算法 - 16】庖丁解牛：基于YOLO12与OpenCV的车辆部件级实例分割实战（附完整代码）

庖丁解牛：基于YOLO12与OpenCV的车辆部件级实例分割实战（附完整代码） 摘要： 告别“只见整车不见细节”！本文将带您深入实战，利用YOLO12-seg训练实例分割模型，结合OpenCV的强大图像处理能力&…
阅读更多...
ubuntu22.04配置远程桌面

ubuntu22.04配置远程桌面

文章目录前言检查桌面类型xorg远程桌面(xrdp)安装xrdpxrdp添加到ssl-certwayland远程桌面(gnome-remote-desktop)检查安装开启开启状况检查自动登录奇技淫巧前言 在windows上使用远程桌面服务，连接ubuntu主机的远程桌面 检查桌面类型 查看桌面类型、协议 echo $…
阅读更多...
SQL Server 中子查询、临时表与 CTE 的选择与对比

SQL Server 中子查询、临时表与 CTE 的选择与对比

在 SQL Server 的实际开发过程中，我们常常需要将复杂的查询逻辑分解为多个阶段进行处理。实现这一目标的常见手段有 子查询 (Subquery)、临时表 (Temporary Table) 和 CTE (Common Table Expression)。这三者在语法、执行效率以及可维护性方面各有优势与局限。如何选…
阅读更多...
肖臻《区块链技术与应用》第20-22讲 - 以太坊难度调整、权益证明和智能合约

肖臻《区块链技术与应用》第20-22讲 - 以太坊难度调整、权益证明和智能合约

以太坊的“冰河时代”：详解难度调整算法与“难度炸弹” 摘要： 为了实现远快于比特币的十几秒出块速度，以太坊必须设计一套更为灵敏和复杂的挖矿难度调整算法。本文基于北京大学肖臻老师的公开课内容，深入剖析了以太坊独特的逐块难度调整机制。文章首先解释了其维持15秒平均…
阅读更多...
C++中内存池（Memory Pool）详解和完整示例

C++中内存池（Memory Pool）详解和完整示例

1. 什么是内存池？ 内存池（Memory Pool / Pool Allocator） 是一种内存管理机制，提前向系统申请一大块内存，再在这块内存里切分、分配和回收。 它相当于在用户空间建立了一层 “小型堆管理器”，避免频繁调用系…
阅读更多...
测试 Next.js 应用：工具与策略

测试 Next.js 应用：工具与策略

1. 引言 Next.js 作为一个基于 React 的全栈框架，在构建复杂 Web 应用时，测试是确保代码质量、功能稳定性和用户体验的关键步骤。测试可以分为单元测试、集成测试和端到端测试三种类型，每种类型针对不同的层面：单元测试验证单个组…
阅读更多...
IP 分片和组装的具体过程

IP 分片和组装的具体过程

IP 分片和组装的具体过程 在这里插入图片描述 • 16 位标识(id): 唯一的标识主机发送的报文. 如果 IP 报文在数据链路层被分片了, 那么每一个片里面的这个 id 都是相同的. • 3 位标志字段: 第一位保留(保留的意思是现在不用, 但是还没想好说不定以后要用到). 第二位置为 1 表示…
阅读更多...
数据仓库OLTPOLAP维度讲解

数据仓库OLTPOLAP维度讲解

✨博客主页： https://blog.csdn.net/m0_63815035?typeblog 💗《博客内容》：大数据、Java、测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 📢博客专栏： https://blog.csdn.net/m0_63815035/…
阅读更多...
OpenHarmony之编译配置白名单机制深度解析：构建系统的安全防线

OpenHarmony之编译配置白名单机制深度解析：构建系统的安全防线

一、白名单机制概述 在OpenHarmony的构建系统中，compile_standard_whitelist.json是一个关键的安全验证机制，它作为编译过程中的"守门人"，确保只有经过验证的组件和依赖关系才能被纳入最终构建产物。这个机制是OpenHarmony构建系统…
阅读更多...
backward怎么计算的是torch.tensor(2.0, requires_grad=True)变量的梯度

backward怎么计算的是torch.tensor(2.0, requires_grad=True)变量的梯度

import torch import torch.nn as nn import torch.optim as optim# 一个参数 w 2 w torch.tensor(2.0, requires_gradTrue) # 预测值 y_pred w * 3 # 6 # 真实值 y_true torch.tensor(10.0) # 损失 (预测 - 真实)^2 loss (y_pred - y_true) ** 2 # (6-10)^2 16loss.b…
阅读更多...
戴永红×数图：重构零售空间价值，让陈列创造效益！

戴永红×数图：重构零售空间价值，让陈列创造效益！

风雨同舟，智赢未来。近日，湖南戴永红商业连锁有限公司（以下简称“戴永红”）正式携手数图信息科技有限公司，全面启动“可视化品类空间管理”项目。以数图可视化陈列系统为引擎，双方将共同推进企业零售管理的…
阅读更多...
排查Redis数据倾斜引发的性能瓶颈

排查Redis数据倾斜引发的性能瓶颈

以下是针对 Redis 数据倾斜问题的完整排查与优化方案，结合实战案例说明如何提升吞吐量和响应速度：一、问题现象定位1. ​性能监控异常​# Redis集群节点负载差异 $ redis-cli -c cluster nodes | grep master e1d7b... 10.0.0.1:637916379 master - 0 16…
阅读更多...
元宇宙的硬件设备：从 VR 头显到脑机接口

元宇宙的硬件设备：从 VR 头显到脑机接口

1 元宇宙的主流硬件设备1.1 VR 头显：沉浸式体验的核心入口VR 头显是当前进入元宇宙最主要的硬件设备，通过封闭的显示系统为用户营造沉浸式虚拟环境。主流 VR 头显采用双屏 LCD 或 OLED 显示技术，单眼分辨率已从早期的 1080P 提升至 4K 级别&a…
阅读更多...
具身智能2硬件架构（人形机器人）摘自Openloong社区

具身智能2硬件架构（人形机器人）摘自Openloong社区

青龙人形机器人： 硬件 身体全身自由度43，手部自由度6*2，电池续航3h，运动控制算法（zmp/slip/mpc/深度学习）MPC+WBC+强化学习，54Tops（FP16），具有路径建图和自主导航能力，感官系统深度视觉传感器*3全景环视*1，具备语音识别与声源定位，可扩展嗅觉传感器 OpenLoong通…
阅读更多...
JavaScript 性能优化：new Map vs Array.find() 查找速度深度对比

JavaScript 性能优化：new Map vs Array.find() 查找速度深度对比

前言在前端开发中，我们经常需要从数据集合中查找特定元素。对于小规模数据，使用 Array.find()方法简单直接，但当数据量增大时，性能问题就会显现。本文将深入对比 Map和 Array.find()在数据查找方面的性能差异，并通过实…
阅读更多...
栈与队列leetcode题型总结

栈与队列leetcode题型总结

1. 常用表格总结数据结构常见应用场景时间复杂度（入/出/查）LeetCode 高频题栈（Stack）括号匹配、单调栈、DFS入栈 O(1) / 出栈 O(1) / 查顶 O(1)20 有效的括号, 155 最小栈, 739 每日温度队列（Queue）层序遍历…
阅读更多...
云原生俱乐部-RH124知识点总结（3）

云原生俱乐部-RH124知识点总结（3）

写到这RH124的内容已经过半了，虽然内容不多，但是还是不太好写。因为简单的命令不想写，至于理解上也没什么难度，不过还是要保证整体内容的都要讲到。这篇文章就把RH124剩下的内容都完结吧，主要还剩下配置和保护SSH、管理…
阅读更多...
安装DDNS-go

安装DDNS-go

wget https://github.com/jeessy2/ddns-go/releases/download/v6.12.2/ddns-go_6.12.2_linux_x86_64.tar.gz tar zxvf ddns-go_6.12.2_linux_x86_64.tar.gz sudo ./ddns-go -s install
阅读更多...
最新文章

Copyright @ 2022~2023