当前位置: 首页 > news >正文

【数据结构】栈和队列-- 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;
}

 

相关文章:

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

目录 一 用队列实现栈 二 用栈实现队列 三 设计循环队列 四 有效的括号 一 用队列实现栈 225. 用队列实现栈 - 力扣(LeetCode) typedef int QDataType; typedef struct QueueNode {struct QueueNode* next;QDataType data; }QNode;typedef struct …...

访问Apache Tomcat的管理页面

配置访问Tomcat管理页面的用户名、密码、角色 Tomcat安装完成后&#xff0c;包含了一个管理应用&#xff0c;默认安装在 <Tomcat安装目录>/webapps/manager 例如&#xff1a; 要使用管理页面的功能&#xff0c;需要在conf/tomcat-users.xml文件中配置用户、密码及角色…...

企业组织内如何避免山头文化?

1&#xff0c;什么是山头文化 2&#xff0c;山头文化的危害 3&#xff0c;如何避免山头文化 01什么是山头文化 山头文化就是指某一组织中的一部分人员组成一个以共同利益为基础的集体&#xff0c;就如同古代占山头一样&#xff0c;在组织中形成一股无形的力量&#xff0c;其…...

【c#】线程Monitor.Wait和Monitor.Pulse使用

介绍 以一个简易版的数据库连接池的实现来说明一下 连接池的connection以队列来管理 getConnection的时候&#xff0c;如果队列中connection个数小于50&#xff0c;且暂时无可用的connection&#xff08;个数为0或者peek看下头部需要先出那个元素还处于不可用状态&#xff09;…...

GitLab平台安装中经典安装语句含义解析

yum -y install policycoreutils openssh-server openssh-clients postfix 这是一个Linux命令&#xff0c;用于使用YUM包管理器安装指定的软件包。下面是对这个命令各部分的解释&#xff1a; yum&#xff1a;这是一个Linux命令行工具&#xff0c;用于管理RPM&#xff08;Red …...

湘潭大学 2023年下学期《C语言》作业0x03-循环1 XTU OJ 1094,1095,1096,1112,1113

第一题 #include<stdio.h>int main() {int t;int count1;scanf("%d",&t);while(t--){int a,b,c;scanf("%d%d",&a,&b);cab;printf("Case %d: %d\n",count,c);count;}return 0; } 记住多样例输入的模板&#xff0c;熟悉计数器…...

【Linux系统满足产品实时性需求】

一、背景&#xff1a; 应用实时性&#xff1a;应用程序1以固定周期执行实时算法&#xff1b; 应用程序2以固定周期&#xff0c;执行串口收发&#xff1b; 驱动实时性&#xff1a;驱动sdio接口&#xff0c;实现与FPGA数据交互&#xff0c;实现串口数据收发。 二、实时性保证&…...

不用休眠的 Kotlin 并发:深入对比 delay() 和 sleep()

本文翻译自&#xff1a; https://blog.shreyaspatil.dev/sleepless-concurrency-delay-vs-threadsleep 毫无疑问&#xff0c;Kotlin 语言中的协程 Coroutine 极大地帮助了开发者更加容易地处理异步编程。该特性中封装的诸多高效 API&#xff0c;可以确保开发者花费更小的精力去…...

在Ubuntu中批量创建用户

一、背景知识 在Linux操作系统中创建新用户可以使用useradd或adduser命令。 使用useradd命令创建用户时&#xff0c;不会在/home目录下创建用户文件夹&#xff0c;需要用户自己指定主目录和bash目录的位置。同时&#xff0c;创建的用户没有设置密码&#xff0c;无法进行登录&a…...

汽车冲压车间的RFID技术设计解决方案

一、RFID技术的基本原理 RFID技术是一种利用非接触式自动识别的技术&#xff0c;通过将RFID标签放置在被识别物品上&#xff0c;并使用RFID读写器对标签进行扫描和识别&#xff0c;实现对物品的自动识别和追踪。RFID标签分为被动式和主动式两种。被动式标签无内置电源&#xf…...

TCP 和UDP通信流程

TCP 通信流程 根据上图可以看到&#xff0c;TCP 服务器和客户端通信分为 TCP 服务端和客户端&#xff0c;需要先建立服务 端然后再建立客户端与之连接进行数据交互。 服务端编程步骤&#xff1a; 1.使用 socket 创建流式套接字 2.使用 bind 绑定将服务器绑定到 IP 3.listen…...

Swift SwiftUI CoreData 过滤数据 1

Xcode: Version 14.3.1 (14E300c) iOS: 16 预览&#xff1a; Code: import SwiftUI import CoreDatastruct TodosSearch: View {State private var search_title "测试"FetchRequest var todos_search: FetchedResults<Todo>init() {let request: NSFetchReq…...

【uniapp】subnvue组件数据更新视图未更新问题

背景 : 页面中的弹窗使用了subnvue来写, 根据数据依次展示一个一个的弹窗, 点击"关闭"按钮关闭当前弹窗, 显示下一个弹窗 问题 : 当点击关闭时( 使用的splice() ), 数据更新了 , 而视图没有更新, 实际上splice() 是不仅更新数据, 也可以更新视图的 解决 : this.$fo…...

Unity编辑器拓展-Odin

1.相比于原生Unity的优势 Unity不支持泛型类型序列化&#xff0c;例如字典原生Unity不支持序列化&#xff0c;而Odin可以继承序列化的Mono实现功能强大且使用简单&#xff0c;原生Unity想实现一些常见的功能需要额外自己编写Unity扩展的编码&#xff0c;实现功能只需要加一个特…...

小红书婴童产业探索,解析消费者需求!

在消费升级、市场引导的背景下&#xff0c;众多产业都在悄然发生着变化&#xff0c;其中“婴童产业”就是非常有代表性的一个。今天就来深入分析小红书婴童产业探索&#xff0c;解析消费者需求&#xff01; 一、何为婴童产业 事实上&#xff0c;婴童产业&#xff0c;并不仅仅局…...

离线安装mysql客户端

下载路径 oracle网站总是在不断更新&#xff0c;所以下载位置随时可能变动但万变不离其宗&#xff0c;学习也要学会一通百通。 首先直接搜索&#xff0c;就能找找到mysql官网 打开网站&#xff0c;并点击 DOWNLOADS 往下滚动&#xff0c;找到社区版下载按钮。…...

Docker 数据管理

管理 Docker 容器中数据主要有两种方式&#xff1a; 数据卷&#xff08;Data Volumes&#xff09; 数据卷容器&#xff08;DataVolumes Containers&#xff09;。 数据卷 数据卷是一个供容器使用的特殊目录&#xff0c;位于容器中。可将宿主机的目录挂载到数据卷上&#xf…...

数据统计--图形报表--ApacheEcharts技术 --苍穹外卖day10

Apache Echarts 营业额统计 重点:已完成订单金额要排除其他状态的金额 根据时间选择区间 设计vo用于后端向前端传输数据,dto用于后端接收前端发送的数据 GetMapping("/turnoverStatistics")ApiOperation("营业额统计")public Result<TurnoverReportVO…...

【kubernetes的三种网络】

kubernetes的三种网络 一、三种网络service网络&#xff08;service是虚拟IP地址&#xff09;pod网络&#xff08;pod的IP地址 docker容器的IP&#xff09;节点网络&#xff08;网络服务器上的物理网卡IP&#xff09; 二、其他网络flannel一、vxlan(隧道方案)1.定义2.优势3.工作…...

Java中树形菜单的实现方式(超全详解!)

前言 这篇文中&#xff0c;我一共会用两种方式来实现目录树的数据结构&#xff0c;两种写法逻辑是一样的&#xff0c;只是一种适合新手理解&#xff0c;一种看着简单明了但是对于小白不是很好理解。在这里我会很详细的讲解每一步代码&#xff0c;主要是方便新人看懂&#xff0…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...