leetcode栈和队列的相关题、有效的括号、用队列实现栈、用栈实现队列、设计循环队列等介绍

news/2024/7/20 17:52:24/文章来源:https://blog.csdn.net/Farewell_me/article/details/139245886

文章目录

  • 前言
  • 一、有效的括号
  • 二、用队列实现栈
  • 三、 用栈实现队列
  • 四、设计循环队列
  • 总结


前言

leetcode栈和队列的相关题、有效的括号、用队列实现栈、用栈实现队列、设计循环队列等介绍


一、有效的括号

leetcode有效的括号
在这里插入图片描述



// 动态增长的栈
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化栈
void STInit(ST* ps);// 销毁栈
void STDestroy(ST* ps);// 插入
void STPush(ST* ps, STDataType x);// 出栈
void STPop(ST* ps);// 检查是否为空
bool STEmpty(ST* ps);// 获取栈顶元素
STDataType STTop(ST* ps);//获取有效元素的个数
int STSize(ST* ps);// 初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("STInit malloc");return;}ps->top = 0; // top指的是栈顶元素的下一个位置//ps->top = -1; // top 指的是栈顶元素ps->capacity = 4;
}// 销毁栈
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a == NULL;ps->top = 0;ps->capacity = 0;
}// 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("STPush relloc");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}// 出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}// 检查是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}// 获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}// 获取有效元素的个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}bool isValid(char* s) {ST st;STInit(&st);while(*s){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st, *s);}else{if(STEmpty(&st)){STDestroy(&st);return false;}char top = STTop(&st);STPop(&st);if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){STDestroy(&st);return false;}}s++;}bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

二、用队列实现栈

leetcode用队列实现栈

在这里插入图片描述


typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
} Queue;// 初始化队列
void QInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}// 销毁队列
void QDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}// 入队列
void QPush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QPush()::malloc()");return;}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;
}// 出队列
void QPop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* cur = pq->head;pq->head = cur->next;free(cur);cur = NULL;}pq->size--;}// 获取队列元素个数
int QSize(Queue* pq)
{assert(pq);return pq->size;
}// 判断队列是否为空
bool QEmpty(Queue* pq)
{assert(pq);return (pq->head == NULL && pq->tail == NULL);
}// 找到队列的头元素
QDataType QFront(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return (pq->head->data);
}// 找到队列的尾元素
QDataType QBack(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return (pq->tail->data);
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("myStackCreate malloc");return NULL;}QInit(&pst->q1);QInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QEmpty(&obj->q1)){QPush(&obj->q1, x);}else{QPush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QEmpty(&obj->q1)){empty = &obj->q2;nonempty = &obj->q1;}while(QSize(nonempty) > 1){QPush(empty, QFront(nonempty));QPop(nonempty);}int top = QFront(nonempty);QPop(nonempty);return top;
}int myStackTop(MyStack* obj) {if(!QEmpty(&obj->q1)){return QBack(&obj->q1);}else{return QBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return (QEmpty(&obj->q1) && QEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {QDestroy(&obj->q1);QDestroy(&obj->q2);obj = NULL;
}/*** 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);
*/

三、 用栈实现队列

leetcode用栈实现队列

在这里插入图片描述


// 动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化栈
void STInit(ST* ps);// 销毁栈
void STDestroy(ST* ps);// 插入
void STPush(ST* ps, STDataType x);// 出栈
void STPop(ST* ps);// 检查是否为空
bool STEmpty(ST* ps);// 获取栈顶元素
STDataType STTop(ST* ps);//获取有效元素的个数
int STSize(ST* ps);// 初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("STInit malloc");return;}ps->top = 0; // top指的是栈顶元素的下一个位置//ps->top = -1; // top 指的是栈顶元素ps->capacity = 4;
}// 销毁栈
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a == NULL;ps->top = 0;ps->capacity = 0;
}// 入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("STPush relloc");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}// 出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}// 检查是否为空
bool STEmpty(ST* ps)
{assert(ps);return (ps->top == 0);
}// 获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}// 获取有效元素的个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* tmp = (MyQueue*)malloc(sizeof(MyQueue));if(tmp == NULL){perror("myQueueCreate malloc");return NULL;}STInit(&tmp->pushst);STInit(&tmp->popst);return tmp;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst, x);
}int myQueuePop(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}int front = STTop(&obj->popst);STPop(&obj->popst);return front;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}int front = STTop(&obj->popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return (STEmpty(&obj->pushst) && STEmpty(&obj->popst));
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);obj = NULL;
}/*** 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);
*/

四、设计循环队列

leetcode设计循环队列

在这里插入图片描述



typedef struct {int* a;int Front;int Rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));tmp->a = (int*)malloc(sizeof(int) * (k+1));tmp->Front = tmp->Rear = 0;tmp->k = k;return tmp;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return (obj->Front == obj->Rear);
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->Front == (obj->Rear + 1) % (obj->k + 1));
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {// 判断是否满了if(myCircularQueueIsFull(obj)){return false;}// 没满obj->a[obj->Rear] = value;obj->Rear++;obj->Rear = obj->Rear % (obj->k + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {// 判断你是否为空if(myCircularQueueIsEmpty(obj)){return false;}obj->Front = obj->Front % (obj->k + 1);obj->Front++;return true;}int myCircularQueueFront(MyCircularQueue* obj) {// 判断队列为空 返回 -1if(myCircularQueueIsEmpty(obj)){return - 1;}return obj->a[obj->Front];
}int myCircularQueueRear(MyCircularQueue* obj) {// 判断队列为空 返回 -1if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->Rear-1 + (obj->k + 1)) % (obj->k + 1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a = NULL;obj->Front = obj->Rear = 0;obj->k = 0;free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

总结

leetcode栈和队列的相关题、有效的括号、用队列实现栈、用栈实现队列、设计循环队列等介绍

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

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

相关文章

第十七届全国大学生信息安全竞赛创新实践能力赛初赛部分复现

Misc 神秘文件 1.根据提示信息,均需要从ppt中提取信息 2.在ppt的属性中发现一串密文和key,解密之后得到第一部分,根据提示Bifid chipher,为双歧密码解密,使用Bifid Cipher Decode解码 3.在第五张幻灯片,…

微服务实践k8sdapr开发部署调用

前置条件 安装docker与dapr: 手把手教你学Dapr - 3. 使用Dapr运行第一个.Net程序安装k8s dapr 自托管模式运行 新建一个webapi无权限项目 launchSettings.json中applicationUrl端口改成5001,如下: "applicationUrl": "http://localhost:5001" //Wea…

K-means聚类算法详细介绍

目录 🍉简介 🍈K-means聚类模型详解 🍈K-means聚类的基本原理 🍈K-means聚类的算法步骤 🍈K-means聚类的优缺点 🍍优点 🍍缺点 🍈K-means聚类的应用场景 🍈K-mea…

mac清理软件推荐免费 mac清理系统数据怎么清理 cleanmymac和腾讯柠檬哪个好

macbook是苹果公司的一款高性能的笔记本电脑,受到了很多用户的喜爱。但是,随着使用时间的增长,macbook的系统也会积累一些垃圾文件,影响其运行速度和空间。那么,macbook系统清理软件推荐有哪些呢?macbook用…

爬虫案例:有道翻译python逆向

pip install pip install requestspip install base64pip install pycrytodome tools 浏览器的开发者工具,重点使用断点,和调用堆栈 工具网站:https://curlconverter.com/ 简便请求发送信息 flow 根据网站信息,preview,respon…

基于 vLLM 搭建 DeepSeek-V2 Chat 服务

直奔主题。 安装vLLM 官方实现的代码还没有 merge 到 vLLM 主分支,所以直接 git clone DeepSeek 的分支。 git clone https://github.com/zwd003/vllm.git cd vllm pip install -e .源码安装大概耗时 10 分钟。 OpenAI 接口规范启动 官方 Github 放的是单条推理…

TS(TypeScript)中Array数组无法调出使用includes方法,显示红色警告

解决方法 打开tsconfig.json文件,添加"lib": ["es7", "dom"]即可。 如下图所示。

php发送短信功能(创蓝短信)

一、以下是创蓝发送短信的功能&#xff0c;可以直接执行&#xff1a; <?php$phone 12312312312;$msg 测试短信功能;echo 发送手机号&#xff1a;.$phone.<br/>;echo 发送内容&#xff1a;.$msg.<br/>;$send sendMessage($phone, $msg);var_dump($send);…

军工单位如何做到安全跨网文件交换与导出的

在现代信息化战争中&#xff0c;军工单位在信息安全方面的需求尤为突出。跨网文件交换与导出作为军工单位日常运营的重要环节&#xff0c;面临着网络带宽限制、数据安全风险、合规性要求和传输稳定性等挑战。下面&#xff0c;我们将从以下几个方面探讨军工单位如何实现安全、高…

2024新数据库入门教程

1.官网下载MySQL 下载Mysql链接: 点击下载mysql 下载完成后解压到某一个文件夹&#xff08;记住这个路径&#xff0c;一会要用到&#xff09; 2.配置初始化文件my.ini 在根目录下创建一个txt文件&#xff0c;名字叫my&#xff0c;文件后缀为ini 以下代码除安装目录和数…

18.分布式监控zabbix-proxy

zabbix proxy 使用场景: 监控远程区域设备监控本地网络不稳定区域当 zabbix 监控上千设备时,使用它来减轻 server 的压力简化分布式监控的维护 环境规划&#xff1a; zabbix-server&#xff1a;外网IP地址192.168.111.66 zabbix-proxy:外网IP地址192.168.111.11 内网IP地址…

【RabbitMQ】使用SpringAMQP的Publish/Subscribe(发布/订阅)

Publish/Subscribe **发布(Publish)、订阅(Subscribe)&#xff1a;**允许将同一个消息发送给多个消费者 **注意&#xff1a;**exchange负责消息路由&#xff0c;而不是存储&#xff0c;路由失败则消息丢失 常见的**X(exchange–交换机)***类型&#xff1a; Fanout 广播Direc…

HNCTF

HNCTF 文章目录 HNCTFBabyPQEZmathez_Classicf(?*?)MatrixRSABabyAESIs this Iso? BabyPQ nc签到题&#xff0c;跟端口连接拿到n和phin n 8336450100232098099043686671148282601664696810002345240872579498695511770993195704402414029892029461830476866385453475141207…

完全背包+背包装满 总结

目录 1.背包恰好装满 &#xff08;1&#xff09;问题是什么 &#xff08;2&#xff09;问题的有效状态和无效状态 &#xff08;3&#xff09;问题的常考形式&#xff0c;以及如何去处理 1.值的大小 2.组合个数 3.排列个数 2.例题 A. Cut Ribbon HDU1114 Piggy-Bank …

冯喜运:5.27黄金短线看震荡,今日黄金原油走势分析

【黄金消息面分析】&#xff1a;黄金作为传统的避险资产&#xff0c;在经济不确定性中扮演着至关重要的角色。近期&#xff0c;国际黄金价格经历了显著的波动。从5月9日的低点2325.19美元/盎司反弹至2340美元/盎司以上&#xff0c;尽管金价曾一度触及2449.89美元/盎司的历史高点…

基于SSM前后端分离版本的论坛系统

目录 前言 一、项目背景 二、相关技术及工具 三、数据库设计 四、软件开发 4.1、搭建环境 4.1.1、创建工程 4.1.2、配置application.yml文件 4.1.3、环境测试 创建测试接口 4.1.4、继续配置 4.2、公共组件 4.2.1、创建工程结构 4.2.2、配置数据源 添加相关依赖 …

如何使用 Re-Ranking 改进大模型 RAG 检索

基于大型语言模型&#xff08;LLMs&#xff09;的聊天机器人可以通过检索增强生成&#xff08;RAG&#xff09;提供外部知识来改进。 这种外部知识可以减少错误答案&#xff08;幻觉&#xff09;&#xff0c;并且使模型能够访问其训练数据中未包含的信息。 通过RAG&#xff0…

科技产业园3D探秘:未来科技之城的奇幻之旅

在数字时代的浪潮中&#xff0c;科技产业园区成为了推动城市经济发展、科技创新的重要引擎。 当我们打开科技产业园的3D可视化模型&#xff0c;仿佛穿越时空&#xff0c;来到了一个充满奇幻色彩的科技世界。在这里&#xff0c;高楼大厦鳞次栉比&#xff0c;绿色植被点缀其间&am…

java图书电子商务网站的设计与实现源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的图书电子商务网站的设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 图书电子商…

堆结构知识点复习——玩转堆结构

前言:堆算是一种相对简单的数据结构&#xff0c; 本篇文章将详细的讲解堆中的知识点&#xff0c; 包括那些我们第一次学习堆的时候容易忽略的内容&#xff0c; 本篇文章会作为重点详细提到。 本篇内容适合已经学完C语言数组和函数部分的友友们观看。 目录 什么是堆 建堆算法…