【数据结构】栈和队列-- OJ

目录

一 用队列实现栈

二 用栈实现队列 

三 设计循环队列 

四 有效的括号


一 用队列实现栈

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

 

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* 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 QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {Que* empty = &obj->q1;Que* nonempty = &obj->q2;if (!QueueEmpty(&obj->q1)){nonempty = &obj->q1;empty = &obj->q2;}while (QueueSize(nonempty) > 1){QueuePush(empty, QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);return top;
}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);
}

 

二 用栈实现队列 

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

 

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = 0;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = (ps->capacity == 0 ? 4 : ((ps->capacity) * 2));STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}typedef struct {ST StackPush;ST StackPop;} MyQueue;MyQueue* myQueueCreate() {MyQueue* pqueue = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pqueue->StackPush);STInit(&pqueue->StackPop);return pqueue;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->StackPush, x);
}int myQueuePeek(MyQueue* obj) {if (STEmpty(&obj->StackPop)){while (!STEmpty(&obj->StackPush)){STPush(&obj->StackPop, STTop(&obj->StackPush));STPop(&obj->StackPush);}}return STTop(&obj->StackPop);}int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->StackPop);return front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->StackPush) && STEmpty(&obj->StackPop);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->StackPush);STDestroy(&obj->StackPop);free(obj);
}

三 设计循环队列 

622. 设计循环队列 - 力扣(LeetCode)

typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间obj->front = obj->rear = 0;obj->k = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->a[obj->rear] = value;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);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}else{return obj->a[obj->front];}}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}else {return obj->a[(obj->rear + obj->k) % (obj->k + 1)];}}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

 

 

四 有效的括号

20. 有效的括号 - 力扣(LeetCode)

typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}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 topval = STTop(&st);STPop(&st);if ((*s == ']' && topval != '[') || (*s == ')' && topval != '(') || (*s == '}' && topval != '{')){STDestroy(&st);return false;}}s++;}bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

 

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

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

相关文章

使用docker搭建nacos单机、集群 + mysql

单机搭建 1 拉取mysql镜像 docker pull mysql:5.7.40 2 启动mysql容器 docker run -d --namemysql-server -p 3306:3306 -v mysql-data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD123456 mysql:5.7.40 3 执行nacos的数据库脚本 /* * Copyright 1999-2018 Alibaba Group Holding L…

ctfshow web入门 php特性 web136-web140

1.web136 还有一种写文件的命令时tee命令 payload&#xff1a; : ls /|tee 1 访问1下载查看文件1发现根目录下有flag cat /f149_15_h3r3|tee 2 访问下载查看文件22.web137 call_user_func <?php class myclass {static function say_hello(){echo "He…

Graphviz 作图工具

选择 Graphviz 作为作图工具&#xff0c;主要是想通过代码创建图标&#xff0c;按照 Graphviz 的代码规范就可以生成 svg 的图片。当然&#xff0c;这样的工具也有很多&#xff0c;有些 markdown 编辑器也做了集成&#xff0c;比如&#xff1a; flowchart.jsMermaid 了解 Gra…

打印字节流和字符流

打印字节流和字符流 printStream/ printWriter的构造器和方法都是一样的 package printfile;import java.io.FileOutputStream; import java.io.OutputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.nio.charset.Charset;public class Prin…

Postgresql中的C/C++混编(JIT)

1 Postgresql编译JIT 整体上看使用了GCC、G编译文件&#xff0c;最后用G汇总&#xff1a; GCC编译的三个.o文件llvmjit、llvmjit_deform、llvmjit_expr llvmjit.c -> llvmjit.o gcc -Wall -Wmissing-prototypes -Wpointer-arith -Wdeclaration-after-statement -…

深入探索地理空间查询:如何优雅地在MySQL、PostgreSQL及Redis中实现精准的地理数据存储与检索技巧

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

基于Springboot实现房屋租赁租房平台系统项目【项目源码+论文说明】分享

基于Springboot实现房屋租赁租房平台系统演示 摘要 在网络高速发展的时代&#xff0c;众多的软件被开发出来&#xff0c;给用户带来了很大的选择余地&#xff0c;而且人们越来越追求更个性的需求。在这种时代背景下&#xff0c;房东只能以用户为导向&#xff0c;所以开发租房网…

实现协议互通:探索钡铼BL124EC的EtherCAT转Ethernet/IP功能

钡铼BL124EC是一种用于工业网络通信的网关设备&#xff0c;专门用于将EtherCAT协议转换成Ethernet/IP协议。它充当一个桥梁&#xff0c;连接了使用不同协议的设备&#xff0c;使它们能够无缝地进行通信和互操作。 具体来说&#xff0c;BL124EC通过支持EtherCAT&#xff08;以太…

docker安装运行环境相关的容器

docker安装常用软件步骤 docker安装Tomcat:latest 2023-10-09 1&#xff09;搜索镜像 以Tomcat为例子&#xff0c;先去官网仓库搜索https://hub.docker.com/search?qtomcat 或者直接命令查询 docker search tomcat2&#xff09;拉取镜像 docker pull tomcat3&#xff09…

CamoDroid 与 Frida Android动态分析工具搭建流程(linux)

CamoDroid 与 Frida Android动态分析工具搭建流程&#xff08;linux&#xff09; 写在前面 这个东西配置起来比较复杂&#xff0c;其实最主要就是配置frida&#xff0c;如果你之前就使用过frida框架的话问题就不是很大 介绍camodroid CamoDroid 是一个开源和开放架构的 And…

力扣第 365 场周赛虚拟参赛

有序三元组中的最大值 I class Solution { public:long long maximumTripletValue(vector<int>& nums) {vector<long long> num;for (auto &item:nums) {num.push_back(item*1ll);}long long z 0,f 1000000;long long ans 0;long long maxx num[0],mi…

基于指数趋近律的机器人滑模轨迹跟踪控制算法及MATLAB仿真

机械手是工业制造领域中应用最广泛的自动化机械设备&#xff0c;广泛应用于工业制造、医疗、军工、半导体制造、太空探索等领域。它们虽然形式不同&#xff0c;但都有一个共同的特点&#xff0c;即能够接受指令&#xff0c;并能准确定位到三维(或二维)空间的某一点进行工作。由…

NoSQL之Redis 主从复制配置详解及哨兵模式

目录 1 Redis 主从复制 1.1 主从复制的作用 1.2 主从复制流程 2 搭建Redis 主从复制 2.1 安装 Redis 2.2 修改 Redis 配置文件&#xff08;Master节点操作&#xff09; 2.3 修改 Redis 配置文件&#xff08;Slave节点操作&#xff09; 2.4 验证主从效果 3 Redis 哨兵模…

PHP 伪协议:使用 php://filter 为数据流应用过滤器

文章目录 参考环境PHP 伪协议概念为什么需要 PHP 伪协议&#xff1f; php://filter概念格式 基本使用普通读写file_get_contents 与 file_put_contentsinclude 过滤器的基本使用base64 的编码与解码rot13 加解密rot13 算法string.rot13 过滤器列表多个过滤器的使用注意事项 处理…

TensorFlow案例学习:对服装图像进行分类

前言 官方为我们提供了一个 对服装图像进行分类 的案例&#xff0c;方便我们快速学习 学习 预处理数据 案例中有下面这段代码 # 预处理数据&#xff0c;检查训练集中的第一个图像可以看到像素值处于0~255之间 plt.figure() # 创建图像窗口 plt.imshow(train_images[0]) # …

【RabbitMQ】初识消息队列 MQ,基于 Docker 部署 RabbitMQ,探索 RabbitMQ 基本使用,了解常见的消息类型

文章目录 前言一、初识消息队列 MQ1.1 同步通信1.2 异步通信1.3 MQ 常见框架及其对比 二、初识 RabbitMQ2.1 什么是 RabbitMQ2.2 RabbitMQ 的结构 三、基于 Docker 部署 RabbitMQ四、常见的消息类型五、示例&#xff1a;在 Java 代码中通过 RabbitMQ 发送消息5.1 消息发布者5.2…

软件测试「转行」答疑(未完更新中)

⭐ 专栏简介 软件测试行业「转行」答疑&#xff1a; 如果你对于互联网的职业了解一知半解&#xff01;不知道行业的前景如何&#xff1f;对于众说纷纭的引流博主说法不知所措&#xff01;不确定这个行业到底适不适合自己&#xff1f; 那么这一篇文章可以告诉你所有真实答案&a…

【网络安全】关于CTF那些事儿你都知道吗?

关于CTF那些事儿你都知道吗&#xff1f; 前言CTF那些事儿内容简介读者对象专家推荐 本文福利 前言 CTF比赛是快速提升网络安全实战技能的重要途径&#xff0c;已成为各个行业选拔网络安全人才的通用方法。但是&#xff0c;本书作者在从事CTF培训的过程中&#xff0c;发现存在几…

<el-input> textarea文本域显示滚动条(超过高度就自动显示)+ <el-input >不能正常输入,输入了也不能删除的问题

需求&#xff1a;首先是给定高度&#xff0c;输入文本框要自适应这个高度。文本超出高度就会显示滚动条否则不显示。 <el-row class"textarea-row"><el-col :span"3" class"first-row-title">天气</el-col><el-col :span&…