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

07 队列

目录

1.队列
2.实现
3.OJ题


1. 队列

只允许在一段进行插入数据操作,在另一端进行数据删除操作的特殊线性表,队列具有先进先出FIFO(First In Firtst Out),插入操作的叫队尾,删除操作的叫队头

在这里插入图片描述

2. 实现

队列可以用数组和链表的结构实现,需要从两端出操作数据,所以用链表的结构更优一点

在这里插入图片描述

队列的设计需要两层结构体,一层结构体是节点结构体,另一层是队列结构

头文件

#pragma once
#include <stdbool.h>typedef int DATATYPE;//节点
typedef struct _Node
{DATATYPE data;struct _Node* next;
}Node;//队列
typedef struct _Queue
{struct _Node* head;struct _Node* tail;int size;
}Queue;// 初始化
void Init(Queue* que);
// 入队
void Push(Queue* que, DATATYPE data);
// 出队
void Pop(Queue* que);
// 是否为空
bool Empty(Queue* que);
// 返回队首
DATATYPE Front(Queue* que);
// 返回队尾
DATATYPE Back(Queue* que);
// 队列大小
int Size(Queue* que);
// 销毁
void Destory(Queue* que);

实现文件

#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>void Init(Queue* que)
{assert(que);//置空que->head = que->tail = NULL;que->size = 0;
}void Push(Queue* que, DATATYPE data)
{assert(que);Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->next = NULL;//空队,不为空if (que->head == NULL){//防止一个空,另一个不为空assert(que->tail == NULL);que->head = que->tail = newnode;}else{que->tail->next = newnode;que->tail = newnode;}que->size++;
}void Pop(Queue* que)
{assert(que);assert(!Empty(que));//一个节点,多个节点if (que->head->next == NULL){free(que->head);que->head = que->tail = NULL;}else{//头删Node* del = que->head;que->head = que->head->next;free(del);}que->size--;
}bool Empty(Queue* que)
{assert(que);//que.head == NULL && que.tail == NULLreturn que->size == 0;
}DATATYPE Front(Queue* que)
{assert(que);assert(!Empty(que));return que->head->data;
}DATATYPE Back(Queue* que)
{assert(que);assert(!Empty(que));return que->tail->data;
}int Size(Queue* que)
{assert(que);return que->size;
}void Destory(Queue* que)
{assert(que);Node* cur = que->head;while (cur != NULL){Node* del = cur;cur = cur->next;free(del);}que->head = que->tail = NULL;que->size = 0;
}

主文件

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "Queue.h"int main()
{Queue que;Init(&que);Push(&que, 1);Push(&que, 2);Push(&que, 3);Push(&que, 4);printf("%d ", Front(&que));printf("%d \r\n", Back(&que));Pop(&que);while (!Empty(&que)){printf("%d ", Front(&que));printf("%d \r\n", Back(&que));Pop(&que);}Destory(&que);return 0;
}

3. OJ题

3.1 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/
在这里插入图片描述

思路
利用前面写的队列。用队列实现栈的关键点在于,队列是先进先出,栈是先进后出。这时,可以用两个栈,需要出数据时将一个栈的所有数据捯到另一个栈中,留下最后一个数据,然后出队,这个就是栈的栈顶元素。每次需要出数据反复这样。入数据时,找一个不为空的入,不为空的出数据捯一遍后,刚好剩下刚进入的数据,栈为空也可以这样

在这里插入图片描述

//引入队列
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DATATYPE;//节点
typedef struct _Node
{DATATYPE data;struct _Node* next;
}Node;//队列
typedef struct _Queue
{struct _Node* head;struct _Node* tail;int size;
}Queue;void Init(Queue* que)
{assert(que);//置空que->head = que->tail = NULL;que->size = 0;
}void Push(Queue* que, DATATYPE data)
{assert(que);Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->next = NULL;//空队,不为空if (que->head == NULL){//防止一个空,另一个不为空assert(que->tail == NULL);que->head = que->tail = newnode;}else{que->tail->next = newnode;que->tail = newnode;}que->size++;
}bool Empty(Queue* que)
{assert(que);//que.head == NULL && que.tail == NULLreturn que->size == 0;
}
void Pop(Queue* que)
{assert(que);assert(!Empty(que));//一个节点,多个节点if (que->head->next == NULL){free(que->head);que->head = que->tail = NULL;}else{//头删Node* del = que->head;que->head = que->head->next;free(del);}que->size--;
}DATATYPE Front(Queue* que)
{assert(que);assert(!Empty(que));return que->head->data;
}DATATYPE Back(Queue* que)
{assert(que);assert(!Empty(que));return que->tail->data;
}int Size(Queue* que)
{assert(que);return que->size;
}void Destory(Queue* que)
{assert(que);Node* cur = que->head;while (cur != NULL){Node* del = cur;cur = cur->next;free(del);}que->head = que->tail = NULL;que->size = 0;
}//------------------------------------------------------------------------
//实现栈
typedef struct {Queue que1;Queue que2;
} MyStack;MyStack* myStackCreate() {MyStack* stk = (MyStack*)malloc(sizeof(MyStack));Init(&stk->que1);Init(&stk->que2);return stk;
}void myStackPush(MyStack* obj, int x) {//往空队列插入if(Empty(&obj->que1))Push(&obj->que1, x);elsePush(&obj->que2, x);
}int myStackPop(MyStack* obj) {//定义空和非空,如果错误交换Queue* empty = &obj->que1;Queue* noempty = &obj->que2;if(Empty(&obj->que2)){empty = &obj->que2;noempty = &obj->que1;}//非空的大于1个往另一个队列捯while(Size(noempty) > 1){Push(empty, Front(noempty));Pop(noempty);}int x = Front(noempty);Pop(noempty);return x;
}int myStackTop(MyStack* obj) {//定义空和非空,如果错误交换Queue* empty = &obj->que1;Queue* noempty = &obj->que2;if(Empty(&obj->que2)){empty = &obj->que2;noempty = &obj->que1;}return Back(noempty);
}bool myStackEmpty(MyStack* obj) {return Empty(&obj->que1) && Empty(&obj->que2);
}void myStackFree(MyStack* obj) {Destory(&obj->que1);Destory(&obj->que2);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);
*/

3.2 栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

在这里插入图片描述

思路
利用实现的栈。栈实现队列同样需要两个栈,由于栈是先进后出,当我们捯一遍数据后,刚好会把所有数据顺序反过来,所以只需要捯一次。利用这种特性,可以将两个栈分为只仅数据的和出数据的。刚开始出栈为空,需要出数据时,从入栈捯数据过来然后出栈顶元素

在这里插入图片描述

//引用栈结构
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int DATATYPE;typedef struct _Stack
{DATATYPE* ary;int top;        //指向下一个存放数据的位置int capacity;
}Stk;void Init(Stk* stack)
{assert(stack);stack->ary = NULL;stack->top = 0;   //指向栈顶下一个位置stack->capacity = 0;
}void Push(Stk* stack, DATATYPE data)
{assert(stack);//需要扩容if (stack->top == stack->capacity){int newcap = stack->capacity == 0 ? 4 : stack->capacity * 2;DATATYPE* temp = (DATATYPE*)realloc(stack->ary, sizeof(DATATYPE) * newcap);if (temp == NULL){perror("realloc fail");return;}stack->ary = temp;stack->capacity = newcap;  }//存数据stack->ary[stack->top] = data;stack->top++;
}bool Empty(Stk* stack)
{assert(stack);return stack->top == 0;
}void Pop(Stk* stack)
{assert(stack);assert(!Empty(stack));stack->top--;
}DATATYPE Top(Stk* stack)
{assert(stack);assert(!Empty(stack));return stack->ary[stack->top - 1];
}int Size(Stk* stack)
{assert(stack);return stack->top;
}void Destory(Stk* stack)
{assert(stack);free(stack->ary);stack->ary = NULL;stack->capacity = 0;stack->top = 0;
}//------------------------------------------------------------------------
//实现队列
typedef struct {Stk stpush;Stk stpop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));Init(&obj->stpush);Init(&obj->stpop);return obj;
}void myQueuePush(MyQueue* obj, int x) {Push(&obj->stpush, x);
}int myQueuePop(MyQueue* obj) {int ch = myQueuePeek(obj);Pop(&obj->stpop);return ch;
}int myQueuePeek(MyQueue* obj) {if(Empty(&obj->stpop)){while(!Empty(&obj->stpush)){Push(&obj->stpop, Top(&obj->stpush));Pop(&obj->stpush);}}return Top(&obj->stpop);
}bool myQueueEmpty(MyQueue* obj) {return Empty(&obj->stpush) && Empty(&obj->stpop);
}void myQueueFree(MyQueue* obj) {Destory(&obj->stpush);Destory(&obj->stpop);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);
*/

相关文章:

07 队列

目录 1.队列 2.实现 3.OJ题 1. 队列 只允许在一段进行插入数据操作&#xff0c;在另一端进行数据删除操作的特殊线性表&#xff0c;队列具有先进先出FIFO&#xff08;First In Firtst Out&#xff09;&#xff0c;插入操作的叫队尾&#xff0c;删除操作的叫队头 2. 实现 队列…...

产品面试题2

39.产品经理在与 开发团队合作时&#xff0c;以下哪个角色负责将产品需求转化为可执行的任务&#xff1f; a) 技术经理 b) 交互设计师 c) 项目经理 d) 开发工程师 答案&#xff1a;c 40.以下哪个方法适用于评估产品的用户满意度和体验&#xff1f; a) 用户访谈 b) 用户调研问卷…...

[NSSCTF]-Web:[SWPUCTF 2021 新生赛]easy_md5解析

先看网页 大致就是输入name和password的值&#xff0c;只要他俩的值不一样&#xff0c;然后经过md5函数之后一样就能出flag。 解法一&#xff08;利用php的科学计数法&#xff09;&#xff1a; 在php中&#xff0c;假设a&#xff0c;b为数字&#xff0c;那科学计数法可以用ae…...

嵌入式解惑——串口通信中的流控制有什么作用?

在串口通信中&#xff0c;流控制&#xff08;Flow Control&#xff09;是一个非常重要的概念。它主要是用来协调发送端和接收端的数据传输速率&#xff0c;以防止接收端流量过大导致的数据丢失问题。   串口通信的特点是数据是以串行方式&#xff0c;一位一位的进行传输。如果…...

Kubernetes-Taint (污点)和 Toleration(容忍)

目录 一、Taint&#xff08;污点&#xff09; 1.污点的组成 2.污点的设置、查看和去除 3.污点实验&#xff1a; 二、Toleration&#xff08;容忍&#xff09; 1.容忍设置的方案 2.容忍实验&#xff1a; Taint 和 toleration 相互配合&#xff0c;可以用来避免 pod 被分配…...

python三数之和

给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。 示例 1…...

uniapp 用css animation做的鲤鱼跃龙门小游戏

第一次做这种小游戏&#xff0c;刚开始任务下来我心里是没底的&#xff0c;因为我就一个‘拍黄片’的&#xff0c;我那会玩前端的动画啊&#xff0c;后面尝试写了半天&#xff0c;当即我就给我领导说&#xff0c;你把我工资加上去&#xff0c;我一个星期给你做出来&#xff0c;…...

JeecgBoot 3.6.1实现Modal对话框,以为审核数据为例

JeecgBoot 3.6.1实现Modal对话框 vue使用的是3.0版本 文章目录 JeecgBoot 3.6.1实现Modal对话框前言一、列表页面关键代码示例二、textAuditModal.vue代码示例三、test.api.ts总结 前言 在工作中&#xff0c;有一个需求&#xff0c;要求&#xff0c;在数据列表页&#xff0c;…...

Spring基于dynamic-datasource实现MySQL多数据源

目录 多数据源实现 引入依赖 yml配置文件 业务代码 案例演示 多数据源实现 引入依赖 <dependency><groupId>com.baomidou</groupId><artifactId>dynamicdatasourcespringbootstarter</artifactId><version>3.5.0</version> &…...

JS高频面试题(下)

11. 线程和进程的区别 进程是资源分配的最小单元&#xff0c;线程是代码执行的最小单元。 一个应用程序可能会开启多个进程&#xff0c;进程之间数据不共享&#xff0c;一个进程内部可以开启多个线程&#xff0c;线程之间的数据可以共享的&#xff0c;所以多线程的情况下&…...

单点登陆(SSO)基于CAS实现前后端分离的SSO系统开发「IDP发起」

关于其他前端常见登录实现单点登录方案&#xff0c;请见「前端常见登录实现方案 单点登录方案 」 前沿 单点登录&#xff08;SSO&#xff09;&#xff0c;英文全称为 Single Sign On。 SSO 是指在多个应用系统中&#xff0c;用户只需要登录一次&#xff0c;就可以访问所有相互…...

二叉树

目录 1翻转二叉树 2对称二叉树 3二叉树的深度 最大深度 最小深度 4二叉树的结点数量 完全二叉树的结点数量 5平衡二叉树 6 中序 后序求前序 二叉树结构体如下&#xff1a; struct freenode {int data;struct freenode *lchild, *rchild;//左孩子 右孩子 }T; 1翻转二…...

边缘计算:挑战与机遇的平衡艺术

前言 边缘计算作为云计算的补充&#xff0c;通过在数据源近处进行数据处理&#xff0c;已经成为实现物联网&#xff08;IoT&#xff09;、自动驾驶、智慧城市等应用的重要技术。然而&#xff0c;边缘计算的发展和普及也面临不少挑战&#xff0c;同时也带来了巨大的机遇。 方向…...

Windows11 Copilot助手开启教程(免费GPT-4)

Windows11上开启Copilot助手教程踩坑指南 Copilot介绍Copilot开启步骤1、更新系统2、更改语言和区域3、下载 ViVeTool 工具4、开启Copilot 使用 Copilot介绍 Windows Copilot 是 Windows 11 中的一个新功能&#xff0c;它可以让你与一个智能助理进行对话&#xff0c;获取信息&…...

【Golang入门教程】如何使用Goland创建并运行项目

自然语言处理的发展 文章目录 自然语言处理的发展**前言**创建新项目编辑运行/调试配置编写并运行代码总结强烈推荐专栏集锦写在最后 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站: 人工…...

鸿蒙开发实战-手写文心一言AI对话APP

运行环境 &#xff08;后面附有API9版本&#xff0c;可修改后在HarmonyOS4设备上运行&#xff09; DAYU200:4.0.10.16 SDK&#xff1a;4.0.10.15 IDE&#xff1a;4.0.600 在DAYU200:4.0.10.16上运行 一、创建应用 1.点击File->new File->Create Progect 2.选择模版…...

鸿蒙常用UI效果及一些处理方式总结

前言&#xff1a; DevEco Studio版本&#xff1a;4.0.0.600 详细使用介绍 1、Text的一些常用设置 Text(this.message).fontSize(50)//字体大小.fontColor(Color.White)//字体颜色.fontWeight(FontWeight.Bold)//字体加粗.backgroundColor(Color.Black)//背景颜色.fontStyle(…...

dataGrip连接数据库mysql和intersystems的iris

intersystems公司的产品iris是cache的升级版本&#xff0c;目前绝大多数数据库工具都没法连接这个数据库 datagrip下载地址 https://download-cdn.jetbrains.com.cn/datagrip/datagrip-2023.3.3.exe 选择对应的数据库产品类型 新建数据库资源连接 填上对应的数据库连接和账…...

【51单片机】点亮第一个LED灯

目录 点亮第一个LED灯单片机 GPIO 介绍GPIO 概念GPIO 结构 LED简介软件设计点亮D1指示灯LED流水灯 橙色 点亮第一个LED灯 单片机 GPIO 介绍 GPIO 概念 GPIO&#xff08;general purpose intput output&#xff09; 是通用输入输出端口的简称&#xff0c; 可以通过软件来控制…...

ubuntu20.04 格式化 硬盘 扩展硬盘

如何在 Ubuntu 22.04 LTS 上安装分区编辑器 GParted&#xff1f;_gparted安装-CSDN博客 sudo apt install gparted 步骤5&#xff1a;启动GParted 安装完成后&#xff0c;您可以在应用程序菜单中找到GParted。点击它以启动分区编辑器。 通过以上步骤&#xff0c;您可以在Ubun…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...