数据结构·一篇搞定队列！

hello，大家好啊，肖恩又拖更了，你们听我狡辩，前段时间有期中考试，so我就没什么时间写这个，在这给大家道个歉😭😭😭
请添加图片描述
我后面一定尽力不拖更
那么接下来，我们来看队列这个数据结构

引言

队列是另一种常见的数据结构,它遵循"先进先出"(FIFO)的原则。队列通常用于存储等待处理的任务或数据,如任务调度、资源分配等。了解队列的基本概念和实现方式对于掌握算法和数据结构同样很重要。

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
在这里插入图片描述

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。
那我们下面来实现队列的一些操作
因为也不是很难，我直接附上代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//初始化
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq) {
	assert(pq);
	QNode* cur = pq->phead;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail == NULL;
	pq->size = 0;
}

// 队尾插入
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL){
		perror("malloc fail");
	return;
}
	newnode->next = NULL;
	newnode->val = x;
	if (pq->phead == NULL)
		pq->phead = pq->ptail = newnode;
	else
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {
	assert(pq);
	assert(pq->size != 0);
	if (pq->phead->next = NULL) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

// 取队头和队尾的数据
QDataType QueueFront(Queue* pq) {
	assert(pq && pq->phead);
	return pq->phead->val;
}

QDataType QueueBack(Queue* pq) {
	assert(pq && pq->ptail);
	return pq->ptail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq) {
	assert(pq);
	return pq->size;
}
// 检测队列是否为空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->size == 0;
}

简单说两个主要的操作

  1. 队尾插入 (QueuePush):

    • 首先检查传入的队列指针是否为空,如果为空则抛出错误。
    • 分配一个新的节点内存空间。
    • 将新节点的 next 指针设置为 NULL,并将待插入的数据 x 存储到节点的 val 字段。
    • 如果队列为空,则将新节点同时设置为头指针 phead 和尾指针 ptail。
    • 否则,将当前尾节点的 next 指针指向新节点,并更新尾指针 ptail 指向新节点。
    • 最后将队列大小 size 加 1。

  2. 队头删除 (QueuePop):

    • 首先检查传入的队列指针是否为空,如果为空则抛出错误。
    • 检查队列是否为空,如果为空则什么也不做直接返回。
    • 如果队列只有一个节点,则释放该节点并将头尾指针都设置为 NULL。
    • 否则,获取头节点的下一个节点,释放头节点,并将头指针 phead 指向下一个节点。
    • 最后将队列大小 size 减 1。

通过这两个基本操作,我们可以实现一个基于链表的队列数据结构,支持向队列尾部添加元素和从队列头部删除元素的功能。

实际中我们有时还会使用一种队列叫循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
使用循环队列的优点是可以高效地利用数组空间,避免了普通队列在删除元素时,需要移动所有剩余元素的问题。但同时也需要额外维护头尾指针,增加了一定的复杂度。

循环队列在某些场景下,如缓存管理、生产者-消费者模型等,能够发挥出较好的性能表现。
那么下面的一个面试题（也是考研题）就让我们来看看循环队列。

例题

设计循环队列
在这里插入图片描述

使用动态数组很方便
我相信下面详细的注释能让你明白循环队列是怎么回事，不是很理解的话，可以自己画图来便于理解

// 定义循环队列结构体
typedef struct {
    int *a;  // 存储队列元素的动态数组
    int head; // 队头下标
    int tail; // 队尾下标
    int k;    // 队列最大容量
} MyCircularQueue;

// 检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue *obj) {
    return obj->head == obj->tail; // 当 head 和 tail 相等时,队列为空
}

// 检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue *obj) {
    return (obj->tail + 1) % (obj->k + 1) == obj->head; // 当 (tail + 1) % (k + 1) 等于 head 时,队列已满
}

// 创建一个容量为 k 的循环队列
MyCircularQueue *myCircularQueueCreate(int k) {
    MyCircularQueue *p = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); // 分配 MyCircularQueue 结构体的内存
    p->a = (int *)malloc((k + 1) * sizeof(int));    // 分配存储元素的动态数组
    p->k = k;                   // 设置队列最大容量
    p->head = p->tail = 0;  // 初始化 head 和 tail 为 0
    return p;
}

// 向队列中添加一个元素
bool myCircularQueueEnQueue(MyCircularQueue *obj, int value) {
    if (myCircularQueueIsFull(obj))  // 如果队列已满,返回 false
        return false;
    
    obj->a[obj->tail] = value;  // 将元素添加到队尾
    obj->tail = (obj->tail + 1) % (obj->k + 1); // 更新 tail 下标,实现循环
    return true;
    
}

// 从队列中删除一个元素
bool myCircularQueueDeQueue(MyCircularQueue *obj) {
    if (myCircularQueueIsEmpty(obj)) { // 如果队列为空,返回 false
        return false;
    } else {
        obj->head = (obj->head + 1) % (obj->k + 1); // 更新 head 下标,实现删除队头元素
        return true;
    }
}

// 获取队头元素
int myCircularQueueFront(MyCircularQueue *obj) {
    if (obj->tail == obj->head) { // 如果队列为空,返回 -1
        return -1;
    } else {
        return obj->a[obj->head]; // 返回队头元素
    }
}

// 获取队尾元素
int myCircularQueueRear(MyCircularQueue *obj) {
    if (obj->tail == obj->head) { // 如果队列为空,返回 -1
        return -1;
    } else {
        return obj->a[(obj->tail + obj->k) % (obj->k + 1)]; // 返回队尾元素
    }
}

// 释放循环队列占用的内存空间
void myCircularQueueFree(MyCircularQueue *obj) {
    free(obj->a); // 释放存储元素的动态数组
    free(obj);     // 释放 MyCircularQueue 结构体
}

循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作
后， front=rear=99 ，则循环队列中的元素个数为（ ）
A. 1
B. 2
C. 99
D. 0或者100

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设
队头不存放数据)
A. (rear - front + N) % N + 1
B. (rear - front + N) % N
C. (rear - front) % (N + 1)
D. (rear - front + N) % (N - 1)

解析：
在循环队列中，队头指针 front 指向队首元素的下一个位置（如果队头不存放数据），而队尾指针 rear 指向队尾元素的下一个位置。这意味着当队列为空时，front 和 rear 通常指向同一个位置（或者在某些实现中，rear 可能在 front 的下一个位置，具体取决于如何定义“空”状态）。

队列的有效长度（即队列中元素的数量）可以通过计算 rear 和 front 之间的差值来得到，但是需要注意这是一个循环结构，所以差值需要用模运算 % N 来处理。

假设 front 和 rear 的初始值都是 0（队列为空），并且每次入队操作 rear 会递增，每次出队操作 front 会递增，那么队列的有效长度可以用以下公式计算：

(rear - front + N) % N
这里加 N 是为了确保在 rear 小于 front 的情况下（即队列绕了一圈之后），差值仍然是正数。然后取模 N 来得到一个 0 到 N-1 之间的值，这个值就是队列的有效长度。

注意：这个公式假设 front 和 rear 的初始值都是 0，并且每次操作后都会递增。如果初始值不是 0，或者有其他特殊的入队/出队逻辑，那么可能需要调整这个公式。
那么到这里，基本上队列的东西都讲完啦
在这里插入图片描述
下一篇讲队列和栈的相互实现~~~
待会儿见
请添加图片描述

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

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

相关文章

数字化转型必备：营销策划流程图，打造你的数字市场地图

数字化转型必备：营销策划流程图，打造你的数字市场地图

制作营销策划流程图是一个系统化的过程&#xff0c;它可以帮助你清晰地规划和展示营销活动的各个阶段。 以下是制作营销策划流程图的步骤&#xff1a; 1.确定营销目标&#xff1a; 明确你的营销活动旨在实现的具体目标&#xff0c;比如提升品牌知名度、增加销售额、吸引新客…
阅读更多...
【CCIE | 网络模拟器】部署 EVE-NG

【CCIE | 网络模拟器】部署 EVE-NG

目录 1. 环境准备2. 下载 EVE-NG 镜像3. 安装 EVE-NG 虚拟机3.1 创建 eve-ng 虚拟机3.2 选择存储3.3 定义虚拟机计算资源&#xff08;1&#xff09;开启CPU虚拟化功能&#xff08;2&#xff09;精简置备磁盘 3.4 检查虚拟机设置 4. 安装系统4.1 选择系统语言4.2 选择系统键盘类…
阅读更多...
2024.05.25 第 131 场双周赛

2024.05.25 第 131 场双周赛

Leetcode 第 131 场双周赛 求出出现两次数字的 XOR 值 [Leetcode 求出出现两次数字的 XOR 值](https://leetcode.cn/problems/find-the-xor-of-numbers-which-appear-twice/description/] 给你一个数组 nums &#xff0c;数组中的数字 要么 出现一次&#xff0c;要么 出现两次…
阅读更多...
自从有了可观测性，传统运维如何进行提升？

自从有了可观测性，传统运维如何进行提升？

在 201x 年&#xff0c;随着容器技术的出现&#xff0c;容器的部署方式逐渐被各大互联网公司采用&#xff0c;相比物理机/虚拟机&#xff0c;容器的好处是环境隔离、轻量、快速。 但是管理容器是一件复杂的事情&#xff0c;后来出现了 Kubernetes&#xff0c;成为了事实上的容…
阅读更多...
数据结构（五）树与二叉树

数据结构（五）树与二叉树

2024年5月26日一稿（王道P142） 基本概念 术语 性质 二叉树 5.2.2 二叉树存储结构
阅读更多...
MySQL｜主从复制配置

MySQL｜主从复制配置

我使用的是两个云服务器&#xff0c;如果读者使用的是虚拟机和本机&#xff0c;配置会简单很多。 关于云服务器安全组设置、防火墙端口等问题请参考文章&#xff1a; 使用华为云服务器进行项目部署&#xff08;云服务器、防火墙配置&#xff09; 条件&#xff1a;master 和 s…
阅读更多...
网络安全之安全协议浅谈

网络安全之安全协议浅谈

安全协议 安全协议概述安全协议分类IPSecIPSec安全协议IPSec架构IPSec封装模式AH协议ESP协议SET协议SET协议电子交易模型SET协议安全目标认证中心CA 安全协议概述 安全协议是信息交换安全的核心&#xff0c;它在网络不同层次上、针对不同应用&#xff0c;通过对各种密码学技术…
阅读更多...
006、API_单线程

006、API_单线程

Redis使用了单线程架构和I/O多路复用模型来实现高性能的内存数据库 服务&#xff0c;本节首先通过多个客户端命令调用的例子说明Redis单线程命令处理 机制&#xff0c;接着分析Redis单线程模型为什么性能如此之高&#xff0c;最终给出为什么理 解单线程模型是使用和运维Redis的…
阅读更多...
面向对象------多态

面向对象------多态

1.多态的定义 通俗来说&#xff0c;当同一种行为或者事情发生在不同的对象上&#xff0c;这些行为或者事情最终得到的结果不同。 注意&#xff1a;多态要发生在继承的基础上。 例如&#xff1a;彩色打印机和黑白打印机。 彩色打印机和黑白打印机是不同的对象&#xff0c;但…
阅读更多...
微信小程序源码-基于Java后端的小区租拼车管理信息系统毕业设计(附源码+演示录像+LW)

微信小程序源码-基于Java后端的小区租拼车管理信息系统毕业设计(附源码+演示录像+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设…
阅读更多...
跟TED演讲学英文：How to escape education‘s death valley by Sir Ken Robinson

跟TED演讲学英文：How to escape education‘s death valley by Sir Ken Robinson

How to escape education’s death valley Link: https://www.ted.com/talks/sir_ken_robinson_how_to_escape_education_s_death_valley Speaker: Sir Ken Robinson Date: April 2013 文章目录 How to escape educations death valleyIntroductionVocabularySummaryTranscri…
阅读更多...
使用残差网络识别手写数字及MNIST 数据集介绍

使用残差网络识别手写数字及MNIST 数据集介绍

MNIST 数据集已经是一个几乎每个初学者都会接触的数据集, 很多实验、很多模型都会以MNIST 数据集作为训练对象, 不过有些人可能对它还不是很了解, 那么今天我们一起来学习一下MNIST 数据集。 1.MNIST 介绍 MNIST 数据集来自美国国家标准与技术研究所, National Institute of S…
阅读更多...
Spring MVC+mybatis项目入门：旅游网（四）用户注册——mybatis的配置与使用以及Spring MVC重定向

Spring MVC+mybatis项目入门：旅游网（四）用户注册——mybatis的配置与使用以及Spring MVC重定向

个人博客&#xff1a;Spring MVCmybatis项目入门:旅游网&#xff08;四&#xff09;用户注册2-持久化 | iwtss blog 先看这个&#xff01; 这是18年的文章&#xff0c;回收站里恢复的&#xff0c;现阶段看基本是没有参考意义的&#xff0c;技术老旧脱离时代&#xff08;2024年…
阅读更多...
MiniMax 悄咪咪上线的这款 AI 产品，好用到爆炸！

MiniMax 悄咪咪上线的这款 AI 产品，好用到爆炸！

大模型太卷了&#xff01;上周国外某款多模态大模型的出现&#xff0c;立刻掀起了 AI 领域对话式多模态交互的热潮。不管是文字、语音&#xff0c;还是图片&#xff0c;都能与你进行实时交互。随后&#xff0c;谷歌也推出了类似的 Astra。 然而&#xff0c;国外的交互式大模型…
阅读更多...
线性回归模型之套索回归

线性回归模型之套索回归

概述 本案例是基于之前的岭回归的案例的。之前案例的完整代码如下&#xff1a; import numpy as np import matplotlib.pyplot as plt from sklearn.linear_model import Ridge, LinearRegression from sklearn.datasets import make_regression from sklearn.model_selectio…
阅读更多...
2024年弘连网络FIC大会竞赛题线下决赛题

2024年弘连网络FIC大会竞赛题线下决赛题

总结&#xff1a; FIC决赛的时候&#xff0c;很多小问题没发现&#xff0c;在pve平台做题确实很方便。 这套题目复盘完&#xff0c;服务器这块的知识确实收获了很多&#xff0c;对pve集群平台和网络拓扑也有了一定的认识&#xff0c;感谢各位大佬悉心指导。 接下来&#xff0…
阅读更多...
【数据结构】哈希表的原理及其实现

【数据结构】哈希表的原理及其实现

文章目录 哈希表的概念哈希函数的设计常见的哈希函数 哈希冲突1. 闭散列代码实现 2. 开散列拉链法的优点 针对开散列哈希的扩展基于开散列拉链法封装哈希表MyHash.h 基于哈希表实现unordered_map类Myunordered_map.h 基于哈希表实现unordered_set类Myunordered_map.h 哈希表的概…
阅读更多...
ROCm上运行Transformer

ROCm上运行Transformer

10.7. Transformer — 动手学深度学习 2.0.0 documentation (d2l.ai) 代码 import math import pandas as pd import torch from torch import nn from d2l import torch as d2l#save class PositionWiseFFN(nn.Module):"""基于位置的前馈网络""&qu…
阅读更多...
解决Error: error:0308010C:digital envelope routines::unsupported的四种解决方案

解决Error: error:0308010C:digital envelope routines::unsupported的四种解决方案

问题描述&#xff1a; 报错&#xff1a;Error: error:0308010C:digital envelope routines::unsupported 报错原因&#xff1a; 主要是因为 nodeJs V17 版本发布了 OpenSSL3.0 对算法和秘钥大小增加了更为严格的限制&#xff0c;nodeJs v17 之前版本没影响&am…
阅读更多...
Rust后台管理系统Salvo-admin源码编译

Rust后台管理系统Salvo-admin源码编译

1.克隆salvo-admin后台管理系统源码: https://github.com/lyqgit/salvo-admin.git 2.编译 编译成功 3.创建mysql数据库与执行sql脚本 输入名称ry-vue 执行sql脚本 全部执行上面3个sql 修改数据库用户名与密码: 清理及重新编译 cargo clean cargo build 4.运行并测试 cargo…
阅读更多...
最新文章

Copyright @ 2022~2023