【数据结构】栈和队列-- 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安装完成后,包含了一个管理应用,默认安装在 <Tomcat安装目录>/webapps/manager 例如: 要使用管理页面的功能,需要在conf/tomcat-users.xml文件中配置用户、密码及角色…...
企业组织内如何避免山头文化?
1,什么是山头文化 2,山头文化的危害 3,如何避免山头文化 01什么是山头文化 山头文化就是指某一组织中的一部分人员组成一个以共同利益为基础的集体,就如同古代占山头一样,在组织中形成一股无形的力量,其…...
【c#】线程Monitor.Wait和Monitor.Pulse使用
介绍 以一个简易版的数据库连接池的实现来说明一下 连接池的connection以队列来管理 getConnection的时候,如果队列中connection个数小于50,且暂时无可用的connection(个数为0或者peek看下头部需要先出那个元素还处于不可用状态)…...

GitLab平台安装中经典安装语句含义解析
yum -y install policycoreutils openssh-server openssh-clients postfix 这是一个Linux命令,用于使用YUM包管理器安装指定的软件包。下面是对这个命令各部分的解释: yum:这是一个Linux命令行工具,用于管理RPM(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; } 记住多样例输入的模板,熟悉计数器…...
【Linux系统满足产品实时性需求】
一、背景: 应用实时性:应用程序1以固定周期执行实时算法; 应用程序2以固定周期,执行串口收发; 驱动实时性:驱动sdio接口,实现与FPGA数据交互,实现串口数据收发。 二、实时性保证&…...

不用休眠的 Kotlin 并发:深入对比 delay() 和 sleep()
本文翻译自: https://blog.shreyaspatil.dev/sleepless-concurrency-delay-vs-threadsleep 毫无疑问,Kotlin 语言中的协程 Coroutine 极大地帮助了开发者更加容易地处理异步编程。该特性中封装的诸多高效 API,可以确保开发者花费更小的精力去…...

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

汽车冲压车间的RFID技术设计解决方案
一、RFID技术的基本原理 RFID技术是一种利用非接触式自动识别的技术,通过将RFID标签放置在被识别物品上,并使用RFID读写器对标签进行扫描和识别,实现对物品的自动识别和追踪。RFID标签分为被动式和主动式两种。被动式标签无内置电源…...

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

Swift SwiftUI CoreData 过滤数据 1
Xcode: Version 14.3.1 (14E300c) iOS: 16 预览: 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不支持泛型类型序列化,例如字典原生Unity不支持序列化,而Odin可以继承序列化的Mono实现功能强大且使用简单,原生Unity想实现一些常见的功能需要额外自己编写Unity扩展的编码,实现功能只需要加一个特…...

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

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

Docker 数据管理
管理 Docker 容器中数据主要有两种方式: 数据卷(Data Volumes) 数据卷容器(DataVolumes Containers)。 数据卷 数据卷是一个供容器使用的特殊目录,位于容器中。可将宿主机的目录挂载到数据卷上…...

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

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

Java中树形菜单的实现方式(超全详解!)
前言 这篇文中,我一共会用两种方式来实现目录树的数据结构,两种写法逻辑是一样的,只是一种适合新手理解,一种看着简单明了但是对于小白不是很好理解。在这里我会很详细的讲解每一步代码,主要是方便新人看懂࿰…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...