leetcode栈和队列三剑客

在这里插入图片描述
用队列实现栈

在这里插入图片描述
队列是先进先出的，而栈是只能在栈顶进行出栈和入栈，那我们这道题要用队列来实现栈的话，这里给的思路是两个队列，因为两个队列的话就可以相互导数据，比如我们来实现这个题目的push函数，我们的栈是只能在栈顶进行操作，那其实插入就也可以在队列的尾部进行插入，但是我们是两个队列，我们不能在空的队列进行插入，这样顺序就会乱，所以我们这里需要做的就是在不是空的队列进行插入操作。

在这里插入图片描述
那如果我们的栈要实现出栈该怎么做呢，我们先来看一下下面的这个图。

在这里插入图片描述
我们这里的出栈不是出第一个元素1，而是想办法把我们这里第一个队列的4出去，那因为队列只能在头上进行pop那我们这里可以先把第一个队列的前三个数据导入到第二个队列中，然会在pop第一个队列就可以了。代码实现就是下面这个图

在这里插入图片描述
我们的队列是始终保持一个是有数据的，一个是为空的，比如我们如果是取栈顶的元素，这里我们是确保取出不为空的队列数据的front，所以这个函数来实现也是特别的简单。

在这里插入图片描述
这道题的整个代码思路就是下面（我们这里用的是C语言，所以要自己实现一个队列）


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->data = data;if (q->head == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(q->size >= 0);assert(q->head != NULL);QNode* del = q->head;q->head = q->head->next;free(del);del = NULL;if (q->head == NULL)q->tail = NULL;q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(q->head);return q->tail->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* q = (MyStack*)malloc(sizeof(MyStack));QueueInit(&q->q1);QueueInit(&q->q2);return q;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(QueueEmpty(nonempty)){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) {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);}/*** 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);
*/

用栈实现队列

在这里插入图片描述
有了前面的思路，我们知道栈的实现是要有两个队列才可以实现的，那同样我们如果要用栈实现队列的话，也得用两个栈来实现，这里我们的两个栈就有主要的区别，我们一个栈可以来当pop栈，还有一个栈可以当成push栈，这样的话，我们就有了分工的作用，后续在插入的时候我们只要在pop栈进行插入就可以了。

那我们先来实现一下我们该怎么初始化，初始化我们直接给两个栈

在这里插入图片描述
这里记住我们去初始化这俩个栈的时候我们是不知道该去怎么初始化，我们直接调用他们的函数就可以了，就不用去记住他们是怎么的一个样子。

在这里插入图片描述
那我们push就需要在push栈中push就可以了

在这里插入图片描述
这里的pop需要注意一些东西
如果popST为空，则将pushST的数据倒过来，就符合先进先出的顺序，如果不为空直接在栈顶进行pop就ok，但是我们这里如果一开始pop为空的，我们需要先把数据倒过来之后才可以进行下一部，我们前面就说过只有pop栈是pop的，push只是push，那我们就要进行判断，然会进行导数据这个操作。

在这里插入图片描述
下一个取出队列的元素，这个就很简单，就是复用上面的代码就可以，只是我们是取出来，不需要进行pop

那这道题就完成了，下面的就口函数我就直接给代码了（这里还是要自己实现一下栈）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>静态实现（固定数组的长度）
//struct Stack
//{
//	int a[N];
//	int top; //栈顶的位置
//};typedef int  STDataType;
//动态实现（固定数组的长度）
typedef struct Stack
{STDataType* a;   //传递数组地址，可以动态的进行扩容int top;   //栈顶的位置int capacity;   //容量
}ST;//初始化
void StackInit(ST* ps);//销毁
void StackDestory(ST* ps);//压栈
void StackPush(ST* ps, STDataType x);//出栈
void StackPop(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);//计算栈的大小
int StackSize(ST* ps);//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;  //初始化top为0，则相当于从栈顶的下一个位置开始，则先赋值，再进行++操作
}//销毁
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//压栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//如果当前的空间不够就需要进行扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (ps->a == NULL){printf("realloc fail\n");exit(-1);}//当前的空间等于新的空间的大小ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;  //判断它的顶部是否为0}//计算栈的大小
int StackSize(ST* ps)
{assert(ps);return ps->top;   //返回栈顶就是元素的个数
}//获取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];   //top是栈顶的下一个元素，想找栈顶元素则进行减一的操作
}//获取栈顶元素
STDataType StackTop(ST* ps);
typedef struct {ST pushST;ST popST;} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));assert(obj);StackInit(&obj->pushST);StackInit(&obj->popST);return obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);StackPush(&obj->pushST,x);}int myQueuePop(MyQueue* obj) {assert(obj);//如果popST为空，则将pushST的数据倒过来，就符合先进先出的顺序if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int front =  StackTop(&obj->popST);StackPop(&obj->popST);return front;}int myQueuePeek(MyQueue* obj) {assert(obj);//如果popST为空，则将pushST的数据倒过来，就符合先进先出的顺序if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}return  StackTop(&obj->popST);;}bool myQueueEmpty(MyQueue* obj) {assert(obj);return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);}void myQueueFree(MyQueue* obj) {assert(obj);StackDestory(&obj->pushST);StackDestory(&obj->popST);free(obj);}
/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*//*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

后面这个题比前面两道简单一点，是关于栈的。。

有效的括号

在这里插入图片描述
这个题我们用栈来实现，为什么用栈是因为这样时间复杂度就是O（N）我们只要遍历一遍就可以了，但是我们这个题目要知道考什么，一个我们必须数量进行匹配，另一个是顺序匹配，比如左括号（ 得和右）进行匹配，所以我们这里需要做的就是左括号这些入栈，然后右括号进行匹配，如果匹配成功的化原来里的括号要进行出栈，然会字符s往后继续++，但是如果有一个括号比右括号不是和我们的左括号匹配的话，我们需要进行的操作就是直接返回false就可以了，如果匹配成功的话出循环就是空栈，所以我们这里就可以直接返回true，但是还是有一个问题就是，在循环里面的时候，会出现越界访问

在这里插入图片描述
越界访问出现的情况就是有右括号，然后没有一个左括号在栈里面，我们这个取top的时候就可以直接返回。

下面是这个题的代码。


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef char STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;void Init(ST* ps);void Push(ST* ps, STDateType x);void Pop(ST* ps);STDateType Top(ST* ps);void Dstory(ST* ps);bool Empty(ST* ps);int Size(ST* ps);void Init(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = -1;
}void Push(ST* ps, STDateType x)
{assert(ps);if (ps->top + 1 == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp =(STDateType*) realloc(ps->a, sizeof(STDateType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->top++;ps->a[ps->top] = x;}void Pop(ST* ps)
{assert(ps);assert(ps->top >= 0);ps->top--;
}void Dstory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->capacity = 0;
}STDateType Top(ST* ps)
{assert(ps);assert(ps->top>=0);return ps->a[ps->top];
}bool Empty(ST* ps)
{assert(ps);return ps->top == -1;
}int Size(ST* ps)
{assert(ps);return ps->top + 1;
}bool isValid(char* s) {ST st;Init(&st);while(*s){if(*s == '(' || *s == '[' || *s == '{'){Push(&st, *s);s++;}else{if(Empty(&st)){return false;}char top = Top(&st);Pop(&st);if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){return false;}s++;}}if(Empty(&st))return true;return false;
}

那今天三剑客就分享到这里，我们下次再见。

在这里插入图片描述

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

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

相关文章

PostgreSQL技术大讲堂 - 第34讲：调优工具pgBagder部署

PostgreSQL技术大讲堂 - 第34讲：调优工具pgBagder部署

PostgreSQL从小白到专家&#xff0c;是从入门逐渐能力提升的一个系列教程&#xff0c;内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容&#xff0c;希望对热爱PG、学习PG的同学们有帮助&#xff0c;欢迎持续关注CUUG PG技术大讲堂。 第34讲&#…
阅读更多...
Niushop单商户及多商户v5商城系统第三方商业插件cps联盟视频购物及多包装库存转换的安装

Niushop单商户及多商户v5商城系统第三方商业插件cps联盟视频购物及多包装库存转换的安装

一、后端安装 把video文件夹直接上传到addon目录下即可登录后台&#xff0c;设置->系统维护->插件管理->未安装插件&#xff0c;找到插件直接安装即可 3.在营销->营销中心->营销活动&#xff0c;找到视频列表这个插件&#xff0c;点击进去配置视频即可 4.装…
阅读更多...
Vue h5页面手指滑动图片

Vue h5页面手指滑动图片

场景&#xff1a; 四张图&#xff0c;要求随着手指滑动而滑动 代码&#xff1a; imgs是父盒子 poster-item是每个图片 .imgs {white-space: nowrap;overflow: hidden;overflow-x: auto;margin-bottom: 17px;.poster-item {display: inline-block;vertical-align: middle;wid…
阅读更多...
Pytorch数据集读出到transform全过程

Pytorch数据集读出到transform全过程

最近写代码又遇见了这个问题&#xff0c;又忘记了&#xff0c;于是写一篇博客记录一下。 一般我们使用pytorch获取CIFAR10数据集&#xff0c;一般这样写&#xff1a; mean [0.4914, 0.4822, 0.4465] std [0.2023, 0.1994, 0.2010] transform transforms.Compose([transform…
阅读更多...
HBase中的数据表是如何用CHAT进行分区的？

HBase中的数据表是如何用CHAT进行分区的？

问CHA&#xff1a;HBase中的数据表是如何进行分区的&#xff1f; CHAT回复&#xff1a; 在HBase中&#xff0c;数据表是水平分区的。每一个分区被称为一个region。当一个region达到给定的大小限制时&#xff0c;它会被分裂成两个新的region。 因此&#xff0c;随着数据量的增…
阅读更多...
探索arkui（2）--- 布局（列表）--- 2（支持分组/实现响应滚动位置）

探索arkui（2）--- 布局（列表）--- 2（支持分组/实现响应滚动位置）

前端开发布局是指前端开发人员宣布他们开发的新网站或应用程序正式上线的活动。在前端开发布局中&#xff0c;开发人员通常会展示新网站或应用程序的设计、功能和用户体验&#xff0c;并向公众宣传新产品的特点和优势。前端开发布局通常是前端开发领域的重要事件&#xff0c;吸…
阅读更多...
Unity中Shader矩阵的转置矩阵

Unity中Shader矩阵的转置矩阵

文章目录 前言一、转置的表示二、转置矩阵三、转置矩阵的总结1、(A^T^)^T^ A2、(A B)^T^ A^T^ B^T^3、(kA)^T^ kA^T^ (k为实数)4、(AB)^T^ B^T^A^T^5、如果 A A^T^ 则称A为对称矩阵6、如果 AA^T^ I(单位矩阵)&#xff0c;则称 A 为正交矩阵&#xff0c;同时 A^T^ A^-1…
阅读更多...
Python与ArcGIS系列（八）通过python执行地理处理工具

Python与ArcGIS系列（八）通过python执行地理处理工具

目录 0 简述1 脚本执行地理处理工具2 在地理处理工具间建立联系0 简述 arcgis包含数百种可以通过python脚本执行的地理处理工具，这样就通过python可以处理复杂的工作和批处理。本篇将介绍如何利用arcpy实现执行地理处理工具以及在地理处理工具间建立联系。 1 脚本执行地理处理…
阅读更多...
【Vue配置项】 computed计算属性 | watch侦听属性

【Vue配置项】 computed计算属性 | watch侦听属性

目录 前言 computed计算属性 什么是计算属性&#xff1f; Vue的原有属性是什么&#xff1f; 得到的全新的属性是什么&#xff1f; 计算属性怎么用&#xff1f; 计算属性的作用是什么&#xff1f; 为什么说代码执行率高了&#xff1f; computed计算属性中的this指向 co…
阅读更多...
CCNA课程实验-14-Final_Lab

CCNA课程实验-14-Final_Lab

目录 实验条件网络拓朴需求 配置实现1. 配置PC1~3, DHCP_Server的vlan2. VLAN10、20的网关为MSW1对应的SVI&#xff0c;VLAN30、40的网关为MSW2对应的SVI&#xff1b;3. 配置5台交换机之间线路均为Trunk4. 配置5台交换机均启用Rapid-PVST(RSTP)5. 配置DHCP Server&#xff0c;创…
阅读更多...
Django模板层

Django模板层

模板之变量 所有的数据类型都可以在模板中使用 render(request, index.html, context{}) render(request, index.html, contextlocals()) """在模板中使用变量的时候&#xff0c;用的是字典的key值&#xff0c;key值value值一般保持一致"""详细…
阅读更多...
Redis：详解5大数据类型及其常用命令

Redis：详解5大数据类型及其常用命令

目录 Redis键&#xff08;key&#xff09;字符串&#xff08;String&#xff09;简介常用命令数据结构简介常用命令 列表&#xff08;List&#xff09;简介常用命令数据结构 集合&#xff08;Set&#xff09;简介常用命令数据结构 哈希&#xff08;Hash&#xff09;简介常用命令…
阅读更多...
计算机网络五层协议的体系结构

计算机网络五层协议的体系结构

计算机网络中两个端系统之间的通信太复杂&#xff0c;因此把需要问题分而治之&#xff0c;通过把一次通信过程中涉及的所有问题分层归类来进行研究和处理 体系结构是抽象的&#xff0c;实现是真正在运行的软件和硬件 1.实体、协议、服务和服务访问点 协议必须把所有不利条件和…
阅读更多...
vue3+vite+ts 发布自定义组件到npm

vue3+vite+ts 发布自定义组件到npm

vue3vite 发布自定义组件到npm 初始化项目编写组件配置打包组件上传到npm测试组件库 初始化项目 // 创建项目 pnpm create vite vue-test-app --template vue-ts// 运行项目 cd vite vue-test-app pnpm install pnpm run dev编写组件 1、根目录下创建packages目录作为组件的开…
阅读更多...
talbay---贝叶斯网络分析工具产品介绍

talbay---贝叶斯网络分析工具产品介绍

一 简介 talbay是拥有独立知识产权的国产软件&#xff0c;主要功能是贝叶斯网络建模、决策网络建模、概率计算、决策支持、敏感性分析、网络模型验证、机器学习等。talbay以用户为中心&#xff0c;简单易用, 计算准确高效&#xff0c;分析全面多样&#xff0c;在应用成熟理论及…
阅读更多...
Linux系统中如何开启和配置OpenGauss数据库的远程连接(1)

Linux系统中如何开启和配置OpenGauss数据库的远程连接(1)

文章目录 前言1. Linux 安装 openGauss2. Linux 安装cpolar3. 创建openGauss主节点端口号公网地址4. 远程连接openGauss5. 固定连接TCP公网地址6. 固定地址连接测试 前言 openGauss是一款开源关系型数据库管理系统&#xff0c;采用木兰宽松许可证v2发行。openGauss内核深度融合…
阅读更多...
Mars3d-vue最简项目模板集成使用Mars3d的UI控件样板

Mars3d-vue最简项目模板集成使用Mars3d的UI控件样板

备注说明&#xff1a; 1.小白可看步骤一二&#xff0c;进阶小白可直接看步骤三 步骤一&#xff1a;新建文件夹<uitest>&#xff0c;在mars3d仓库拉一份最简项目模板&#xff1a; git clone mars3d-vue-template: Vue3.x 技术栈下的Mars3D项目模板 步骤二&#xff1a;运…
阅读更多...
kubernetes部署jenkins

kubernetes部署jenkins

参考&#xff1a;kubernetes 部署 Jenkins jenkins kubernetes pipeline_mob64ca14116c53的技术博客_51CTO博客 第七篇&#xff1a;kubernetes部署jenkins-CSDN博客 1、当前kubernetes集群已部署nfs服务 showmount -e 创建jenkins目录 2、添加jenkins的pvc kubectl create …
阅读更多...
IP-guard flexpaper远程命令执行漏洞复现 [附POC]

IP-guard flexpaper远程命令执行漏洞复现 [附POC]

文章目录 IP-guard flexpaper RCE漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 0x06 修复建议 IP-guard flexpaper RCE漏洞复现 [附POC] 0x01 前言 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测…
阅读更多...
快速使用vscode写python

快速使用vscode写python

1.打开vscode&#xff0c;打开扩展&#xff0c;输入python&#xff0c;点击安装。 2.下载python。官网下载太慢&#xff0c;通过镜像下载。 http://npm.taobao.org/mirrors/python/3.9.0/ 下载python-3.9.0-amd64.exe 3.下载好后安装python&#xff0c;下方的add python to p…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023