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 == NULL
	return 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 == NULL
	return 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);
    else
        Push(&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);
*/

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

前端echarts图形报表常见的样式配置

前端echarts图形报表常见的样式配置

文章目录 &#x1f412;个人主页&#x1f3c5;Vue项目常用组件模板仓库&#x1f4d6;前言&#xff1a;&#x1f415;1.深色主题&#x1f415;2.改变柱状图颜色&#x1f415;突然发现去问ai&#xff0c;更容易理解&#xff0c;那就不总结了 &#x1f412;个人主页 &#x1f3c5;…
阅读更多...
太阳光模拟器汽车耐老化太阳跟踪聚光户外加速老化试验

太阳光模拟器汽车耐老化太阳跟踪聚光户外加速老化试验

1 范围 1.1 本标准适用于以太阳为光源的菲涅耳反射系统来进行汽车外饰材料的加速老化试验。 1.2 本标准规定的设备和方法可用于确定曝露于日光、热和潮湿下的汽车材料的相对耐老化性&#xff0c; 前提是假设试验期间发生的对材料加速老化速率起决定性作用的物理、化学变化机理…
阅读更多...
缓存高并发问题

缓存高并发问题

Redis 做缓存虽减轻了 DBMS 的压力&#xff0c;减小了 RT&#xff0c;但在高并发情况下也是可能会出现各种问题的。 缓存穿透 当用户访问的数据既不在缓存也不在数据库中时&#xff0c;就会导致每个用户查询都会“穿透”缓存“直抵”数据库。这种情况就称为缓存穿透。当高度发…
阅读更多...
什么是网络？

什么是网络？

你是一台电脑&#xff0c;你的名字叫 A 很久很久之前&#xff0c;你不与任何其他电脑相连接&#xff0c;孤苦伶仃。 直到有一天&#xff0c;你希望与另一台电脑 B 建立通信&#xff0c;于是你们各开了一个网口&#xff0c;用一根网线连接了起来。 用一根网线连接起来怎么就能&…
阅读更多...
Oracle BIEE 示例（一）数据透视表2

Oracle BIEE 示例（一）数据透视表2

1 背景 版本：BIEE 12C 视图：数据透视表 实现内容（顺序与具体内容不一致）： 2 空列显示（方法一） 2.1 问题 列为空时，标题栏不显示信息。 2.2 期望 即使数据为空，也要显示列名。 2.3 官方资料 2.3.1 操作步骤 2.3.1.1 要在分析级别关闭空值隐藏，请执行以下操作…
阅读更多...
不停机迁移，TDengine 在 3D 打印技术中的“焕新”之路

不停机迁移，TDengine 在 3D 打印技术中的“焕新”之路

小T导读&#xff1a;自 2021 年我们正式使用 TDengine 至今已接近三年&#xff0c;现在 TDengine 已经成熟应用于我们多个项目当中&#xff0c;凭借着强大的读写存储能力&#xff0c;为我司多项业务的核心数据保驾护航。近期我们团队刚好完成 TDengine 2.x 到 3.x 的数据迁移&a…
阅读更多...
基于EfficientNet(B0-B7)全系列不同参数量级模型开发构建中草药图像识别分析系统，实验量化对比不同模型性能

基于EfficientNet(B0-B7)全系列不同参数量级模型开发构建中草药图像识别分析系统，实验量化对比不同模型性能

EfficientNet系列的模型在我们前面开发识别类项目或者是检测类项目都是比较少去使用的&#xff0c;一方面是技术本身迭代发展的速度是比较快的&#xff0c;可能新的东西还没学习更新的东西就出来了&#xff0c;另一方面是EfficientNet本身实际业务使用度并不高&#xff0c;可能…
阅读更多...
C++ STL之deque的理解及使用

C++ STL之deque的理解及使用

文章目录 1. 介绍2. 实现原理&#xff08;简单理解&#xff09;3. deque的优缺点4. deque类的使用4.1 deque类对象的构造函数4.2 deque类对象的容量操作4.3 deque类对象的修改操作4.4 deque类对象的访问及遍历操作 1. 介绍 deque(双端队列)&#xff1a;是一种双开口的连续空间的…
阅读更多...
UCAS-AOD遥感旋转目标检测数据集——基于YOLOv8obb，map50已达96.7%

UCAS-AOD遥感旋转目标检测数据集——基于YOLOv8obb，map50已达96.7%

1.UCAS-AOD简介 1.1数据说明 遥感图像&#xff0c;又名高分辨率遥感图像。遥感图像的分类依据是根据成像的介质不同来进行分类的。UCAS-AOD (Zhu et al.&#xff0c;2015)用于飞机和汽车的检测&#xff0c;包含飞机与汽车2类样本以及一定数量的反例样本&#xff08;背景&…
阅读更多...
第4章 面向对象（下）

第4章 面向对象（下）

4.1 继承 4.1.1 继承的概念 在现实生活中&#xff0c;继承一般指的是子女继承父辈的财产。在程序中&#xff0c;继承描述的是事物之间的所属关系&#xff0c;通过继承可以使多种事物之间形成一种关系体系。例如&#xff0c;猫和狗都属于动物&#xff0c;程序中便可以描述为猫…
阅读更多...
2017年认证杯SPSSPRO杯数学建模C题(第二阶段)移动端考研产品的春天真的到来了吗全过程文档及程序

2017年认证杯SPSSPRO杯数学建模C题(第二阶段)移动端考研产品的春天真的到来了吗全过程文档及程序

2017年认证杯SPSSPRO杯数学建模 C题 移动端考研产品的春天真的到来了吗 原题再现&#xff1a; 2017 年的全国硕士研究生招生考试共有 201 万人报名参加&#xff0c;比去年增加了 24 万名考生&#xff0c;增加 13.56%。看起来新一轮的考研热潮即将到来&#xff0c;而考研教学和…
阅读更多...
JAVA工程中引用本地jar的3种常用方式，你用过哪种?

JAVA工程中引用本地jar的3种常用方式，你用过哪种?

文章目录 前言1. 第1种方式2. 第2种方式3. 第3种方式 前言 实际项目过程中咱们经常会碰到需要本地引用jar包到java工程中的场景&#xff0c;本文就介绍一下遇到此场景时如何在IDEA中导入本地jar包到工程中的3种方式&#xff0c;简单却很常用。 1. 第1种方式 IDEA -> File …
阅读更多...
MySQL函数—流程函数

MySQL函数—流程函数

MySQL函数—流程函数&#xff1a;用于实现条件筛选&#xff0c;从而题搞语句的效率。 MySQL函数—流程函数 函数功能IF(value,t,f)如果value为true&#xff0c;则返回t&#xff0c;否则返回fIFNULL(value1,value2)如果value1不为空&#xff0c;返回value1&#xff0c;否则返回v…
阅读更多...
单点登陆（SSO）基于CAS实现前后端分离的SSO系统开发「IDP发起」

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

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

分布变化下的Test-Time adaption 综述

论文 https://arxiv.org/abs/2303.15361 代码 https://github.com/tim-learn/awesome-test-time-adaptation &#xff08;其实这是相关领域代码和论文合集之类的东西&#xff09; Abstract 机器学习方法努力在训练过程中获得一个鲁棒模型&#xff0c;即使在分布变化的情况下…
阅读更多...
RDMA vs InfiniBand 网卡接口如何区分？

RDMA vs InfiniBand 网卡接口如何区分？

(该架构图来源于参考文献) 高性能计算网络&#xff0c;RoCE vs. InfiniBand该怎么选&#xff1f; 新 RoCEv2 标准可实现 RDMA 路由在第三层以太网网络中的传输。RoCEv2 规范将用以太网链路层上的 IP 报头和 UDP 报头替代 InfiniBand 网络层。这样&#xff0c;就可以在基于 IP…
阅读更多...
向日葵远程控制Mac版权限设置教程解决远程无法控制问题

向日葵远程控制Mac版权限设置教程解决远程无法控制问题

很多Mac新手安装向日葵远程控制Mac版后&#xff0c;根据提示设置了权限后发现无法远程控制&#xff0c;其实主要是你只勾选了中文的“向日葵权限选项“&#xff0c;而忘记了勾选了向日葵另外一个英文选项权限。 判断是否完全开启控制权限 打开向日葵访问权限设置面板&#xf…
阅读更多...
gitlab runner 安装、注册、配置、使用

gitlab runner 安装、注册、配置、使用

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…
阅读更多...
Unity Mask合批情况验证

Unity Mask合批情况验证

1.首先是两个Mask完全重合的情况下 每张图片使用的image都来自同一个图集 发现彼此之间是没有合批的&#xff0c;但是每个Mask内部是实现了合批的 经过计算此种情况的visiableList&#xff1a;mask1&#xff0c;IM1&#xff0c;IM2&#xff0c;mask2&#xff0c;IM3&#xf…
阅读更多...
实时渲染 -- 光追（Ray Tracing)

实时渲染 -- 光追（Ray Tracing)

光栅化 Or 光线追踪 传统的光栅化方式主要是将每个物体进行光栅化后形成若干个像素&#xff0c;然后每个像素需要计算光源直接照射到自己并反射回眼睛而形成的颜色。这种算法方式是极快的&#xff0c;但是只能表示直接光照&#xff0c;图像质量较低。 Bling-Phong 模型是一个常…
阅读更多...
最新文章

Copyright @ 2022~2023