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. 队列 只允许在一段进行插入数据操作,在另一端进行数据删除操作的特殊线性表,队列具有先进先出FIFO(First In Firtst Out),插入操作的叫队尾,删除操作的叫队头 2. 实现 队列…...
产品面试题2
39.产品经理在与 开发团队合作时,以下哪个角色负责将产品需求转化为可执行的任务? a) 技术经理 b) 交互设计师 c) 项目经理 d) 开发工程师 答案:c 40.以下哪个方法适用于评估产品的用户满意度和体验? a) 用户访谈 b) 用户调研问卷…...
[NSSCTF]-Web:[SWPUCTF 2021 新生赛]easy_md5解析
先看网页 大致就是输入name和password的值,只要他俩的值不一样,然后经过md5函数之后一样就能出flag。 解法一(利用php的科学计数法): 在php中,假设a,b为数字,那科学计数法可以用ae…...
嵌入式解惑——串口通信中的流控制有什么作用?
在串口通信中,流控制(Flow Control)是一个非常重要的概念。它主要是用来协调发送端和接收端的数据传输速率,以防止接收端流量过大导致的数据丢失问题。 串口通信的特点是数据是以串行方式,一位一位的进行传输。如果…...
Kubernetes-Taint (污点)和 Toleration(容忍)
目录 一、Taint(污点) 1.污点的组成 2.污点的设置、查看和去除 3.污点实验: 二、Toleration(容忍) 1.容忍设置的方案 2.容忍实验: Taint 和 toleration 相互配合,可以用来避免 pod 被分配…...
python三数之和
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例 1…...
uniapp 用css animation做的鲤鱼跃龙门小游戏
第一次做这种小游戏,刚开始任务下来我心里是没底的,因为我就一个‘拍黄片’的,我那会玩前端的动画啊,后面尝试写了半天,当即我就给我领导说,你把我工资加上去,我一个星期给你做出来,…...
JeecgBoot 3.6.1实现Modal对话框,以为审核数据为例
JeecgBoot 3.6.1实现Modal对话框 vue使用的是3.0版本 文章目录 JeecgBoot 3.6.1实现Modal对话框前言一、列表页面关键代码示例二、textAuditModal.vue代码示例三、test.api.ts总结 前言 在工作中,有一个需求,要求,在数据列表页,…...
Spring基于dynamic-datasource实现MySQL多数据源
目录 多数据源实现 引入依赖 yml配置文件 业务代码 案例演示 多数据源实现 引入依赖 <dependency><groupId>com.baomidou</groupId><artifactId>dynamicdatasourcespringbootstarter</artifactId><version>3.5.0</version> &…...
JS高频面试题(下)
11. 线程和进程的区别 进程是资源分配的最小单元,线程是代码执行的最小单元。 一个应用程序可能会开启多个进程,进程之间数据不共享,一个进程内部可以开启多个线程,线程之间的数据可以共享的,所以多线程的情况下&…...
单点登陆(SSO)基于CAS实现前后端分离的SSO系统开发「IDP发起」
关于其他前端常见登录实现单点登录方案,请见「前端常见登录实现方案 单点登录方案 」 前沿 单点登录(SSO),英文全称为 Single Sign On。 SSO 是指在多个应用系统中,用户只需要登录一次,就可以访问所有相互…...
二叉树
目录 1翻转二叉树 2对称二叉树 3二叉树的深度 最大深度 最小深度 4二叉树的结点数量 完全二叉树的结点数量 5平衡二叉树 6 中序 后序求前序 二叉树结构体如下: struct freenode {int data;struct freenode *lchild, *rchild;//左孩子 右孩子 }T; 1翻转二…...
边缘计算:挑战与机遇的平衡艺术
前言 边缘计算作为云计算的补充,通过在数据源近处进行数据处理,已经成为实现物联网(IoT)、自动驾驶、智慧城市等应用的重要技术。然而,边缘计算的发展和普及也面临不少挑战,同时也带来了巨大的机遇。 方向…...
Windows11 Copilot助手开启教程(免费GPT-4)
Windows11上开启Copilot助手教程踩坑指南 Copilot介绍Copilot开启步骤1、更新系统2、更改语言和区域3、下载 ViVeTool 工具4、开启Copilot 使用 Copilot介绍 Windows Copilot 是 Windows 11 中的一个新功能,它可以让你与一个智能助理进行对话,获取信息&…...
【Golang入门教程】如何使用Goland创建并运行项目
自然语言处理的发展 文章目录 自然语言处理的发展**前言**创建新项目编辑运行/调试配置编写并运行代码总结强烈推荐专栏集锦写在最后 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站: 人工…...
鸿蒙开发实战-手写文心一言AI对话APP
运行环境 (后面附有API9版本,可修改后在HarmonyOS4设备上运行) DAYU200:4.0.10.16 SDK:4.0.10.15 IDE:4.0.600 在DAYU200:4.0.10.16上运行 一、创建应用 1.点击File->new File->Create Progect 2.选择模版…...
鸿蒙常用UI效果及一些处理方式总结
前言: DevEco Studio版本: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的升级版本,目前绝大多数数据库工具都没法连接这个数据库 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(general purpose intput output) 是通用输入输出端口的简称, 可以通过软件来控制…...
ubuntu20.04 格式化 硬盘 扩展硬盘
如何在 Ubuntu 22.04 LTS 上安装分区编辑器 GParted?_gparted安装-CSDN博客 sudo apt install gparted 步骤5:启动GParted 安装完成后,您可以在应用程序菜单中找到GParted。点击它以启动分区编辑器。 通过以上步骤,您可以在Ubun…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
node.js的初步学习
那什么是node.js呢? 和JavaScript又是什么关系呢? node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说, 需要在node.js的环境上进行当JavaScript作为前端开发语言来说,需要在浏览器的环境上进行 Node.js 可…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
