【数据结构】线性表(十)队列:循环队列及其基本操作(初始化、判空、判满、入队、出队、存取队首元素)

文章目录

  • 队列
    • 1. 定义
    • 2. 基本操作
  • 顺序队列
  • 循环队列
    • 1. 头文件和常量
    • 2. 队列结构体
    • 3. 队列的初始化
    • 4. 判断队列是否为空
    • 5. 判断队列是否已满
    • 6. 入队
    • 7. 出队
    • 8. 存取队首元素
    • 9. 获取队列中元素个数
    • 10. 打印队列中的元素
    • 9. 主函数
    • 10. 代码整合

  堆栈Stack 和 队列Queue是两种非常重要的数据结构,两者都是特殊的线性表:

  • 对于堆栈,所有的插入和删除(以至几乎所有的存取)都是在表的同一端进行;
  • 对于队列,所有的插入都是在表的一端进行,所有的删除(以至几乎所有的存取)都是在表的另一端进行。

队列

1. 定义

  队列是一种操作受限的线性表,对于它的所有插入都在表的一端进行,所有的删除(以至几乎所有的存取)都在表的另一端进行,且这些操作又都是按照先进先出(FIFO)的原则进行的。进行删除的一端称为队头(front),进行插入的一端称为队尾(rear)。没有元素的队列称为空队列(简称空队)。

在这里插入图片描述
  队列就像生活中排队购物,新来的人只能加入队尾(假设不允许插队),购物结束后先离开的总是队头(假设无人中途离队)。也就是说,先加入队列的成员总是先离开队列,因此队列被称为先进先出(First In First Out)的线性表,简称为FIFO表。如图,在空队列中依次加入元素a1,a2,a3,a4,a5,出队次序仍然是a1,a2,a3,a4,a5 .

2. 基本操作

  • 队列是受限的线性表,其基本操作包括

    • IsEmpty() : 判断队列是否为空;
    • isFull():判断队列是否为满;
    • enqueue() :向队尾添加元素(入队);
    • dequeue() :删除队首元素(出队);
    • peek():获取队首的元素值(存取);
  • 同普通线性表一样,队列也可以用顺序存储和链接存储两种方式来实现:

顺序队列

  参考前文:线性表(八)队列:顺序队列及其基本操作(初始化、判空、判满、入队、出队、存取队首元素)

  关于顺序队列,删除队头元素有两种方式:

  • ⑴ 不要求队头元素必须存放在数组的第一个位置。每次删除队头元素,只需修改队头指针front所指的位置(即队头元素在数组中的下标),令front=front+1 . 该方式的优点是无须改变诸队列元素的地址,缺点是front值随着队头元素的删除而不断增加,整个队列向数组的后端位置移动,随着队尾元素的不断加入,必然出现数组后端没有可用空间的情况,而数组前端的大量空间却被闲置。
  • ⑵ 要求队头元素必须存放在数组的第一个位置。每次删除队头元素,令所有元素都向前移动一个位置。该方式的优点是不浪费空间,缺点是所有元素的地址都必须改变,效率低下。

循环队列

  为了克服上述缺点,可以假定数组是循环的,即采用环状模型来实现顺序队列。这种模型将队列在逻辑上置于一个圆环上,如图3.17所示,用整型变量front存放队头位置,每删除一个队头元素,就将front顺时针移动一个位置;整型变量rear存放新元素要插入的位置(下标),每插入一个元素,rear将顺时针移动一个位置;整型变量count存放队列中元素的个数,当count等于数组规模Size时,说明队列已满,当count等于0时,说明队列为空。
在这里插入图片描述

1. 头文件和常量

#include <stdio.h>
#define MAX_SIZE 100
  • 头文件stdio.h用于输入输出操作

  • 通过#define指令定义了一个常量MAX_SIZE,它表示顺序队列中数组的最大容量为100

2. 队列结构体

typedef struct {int data[MAX_SIZE]; // 存储队列元素的数组int front;          // 队头指针int rear;           // 队尾指针int count;          // 队列规模
} CircularQueue;
  • 整型数组 data,用于存储队列元素;
  • frontrear 分别表示队头指针和队尾指针;
  • count:队列中元素的个数。

3. 队列的初始化

void initQueue(CircularQueue *queue) {queue->front = 0;queue->rear = 0;queue->count = 0;
}

   initQueue 函数:初始化队列,它将队头、队尾和元素个数都设置为0,表示队列为空。

4. 判断队列是否为空

bool isEmpty(CircularQueue *queue) {
//    return queue->front == 0;return queue->count == 0;
}

   通过检查队列中元素的个数来判断队列是否为空。

5. 判断队列是否已满

bool isFull(CircularQueue *queue) {return queue->count == MAX_SIZE;
}

  通过比较队列中元素的个数和最大容量 MAX_SIZE 来判断队列是否已满。

6. 入队

void enqueue(CircularQueue *queue, int item) {if (isFull(queue)) {printf("Queue is full. Cannot enqueue.\n");return;}queue->data[queue->rear] = item;queue->rear = (queue->rear + 1) % MAX_SIZE;queue->count++;
}
  • 判断队列是否已满
    • 如果已满则打印错误信息并返回;
    • 否则,将元素添加到队尾,并更新队尾指针和元素个数。

7. 出队

int dequeue(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty. Cannot dequeue.\n");return -1;}int item = queue->data[queue->front];queue->front = (queue->front + 1) % MAX_SIZE;queue->count--;return item;
}
  • 判断队列是否为空
    • 如果为空则打印错误信息并返回 -1;
    • 否则,将队头元素返回,并更新队头指针和元素个数。

8. 存取队首元素

int peek(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty. Cannot peek.\n");return -1;}return queue->data[queue->front];
}

   peek 函数用于查看队头元素,但不移除它。如果队列为空,则打印提示信息并返回 -1。

9. 获取队列中元素个数

int size(CircularQueue *queue) {return queue->count;
}

10. 打印队列中的元素

void display(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty.\n");return;}printf("Queue elements: ");int i = queue->front;int count = 0;while (count < queue->count) {printf("%d ", queue->data[i]);i = (i + 1) % MAX_SIZE;count++;}printf("\n");
}
  • 如果队列为空,则打印提示信息;
  • 否则,使用循环遍历队列中的元素并逐个打印。

9. 主函数

int main() {CircularQueue queue;initQueue(&queue);enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));dequeue(&queue);printf("Dequeued element.\n");display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));return 0;
}

在这里插入图片描述

10. 代码整合

#include <stdio.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 存储队列元素的数组int front;          // 队头指针int rear;           // 队尾指针int count;          // 队列规模
} CircularQueue;void initQueue(CircularQueue *queue) {queue->front = 0;queue->rear = 0;queue->count = 0;
}bool isEmpty(CircularQueue *queue) {
//    return queue->front == 0;return queue->count == 0;
}bool isFull(CircularQueue *queue) {return queue->count == MAX_SIZE;
}void enqueue(CircularQueue *queue, int item) {if (isFull(queue)) {printf("Queue is full. Cannot enqueue.\n");return;}queue->data[queue->rear] = item;queue->rear = (queue->rear + 1) % MAX_SIZE;queue->count++;
}int dequeue(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty. Cannot dequeue.\n");return -1;}int item = queue->data[queue->front];queue->front = (queue->front + 1) % MAX_SIZE;queue->count--;return item;
}int peek(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty. Cannot peek.\n");return -1;}return queue->data[queue->front];
}int size(CircularQueue *queue) {return queue->count;
}void display(CircularQueue *queue) {if (isEmpty(queue)) {printf("Queue is empty.\n");return;}printf("Queue elements: ");int i = queue->front;int count = 0;while (count < queue->count) {printf("%d ", queue->data[i]);i = (i + 1) % MAX_SIZE;count++;}printf("\n");
}int main() {CircularQueue queue;initQueue(&queue);enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));dequeue(&queue);printf("Dequeued element.\n");display(&queue);printf("Queue size: %d\n", size(&queue));printf("Front element: %d\n", peek(&queue));return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于springboot实现基于Java的超市进销存系统项目【项目源码+论文说明】

基于springboot实现基于Java的超市进销存系统演示 摘要 随着信息化时代的到来&#xff0c;管理系统都趋向于智能化、系统化&#xff0c;超市进销存系统也不例外&#xff0c;但目前国内仍都使用人工管理&#xff0c;市场规模越来越大&#xff0c;同时信息量也越来越庞大&#x…

Unity使用c#开发apk项目(十九)(Failed to find entry-points:System.Exception: )

文章目录 前言解决方案:1.报警信息如下2.选择3d urp3.引入Fusion之后选择包管理,点击Burst中的Advanced Project Settings4.勾选两个预设选项5.引入官网unity.burst6.更新后报警消失前言 制作局域网游戏,出现未找到进入点报警 Failed to find entry-points 解决方案: 1.报…

【MySql】8- 实践篇(六)

文章目录 1. MySql保证主备一致1.1 MySQL 主备的基本原理1.2 binlog 的三种格式对比1.3 循环复制问题 2. MySql保证高可用2.1 主备延迟2.2 主备延迟的来源2.3 可靠性优先策略2.4 可用性优先策略 3. 备库为何会延迟很久-备库并行复制能力3.1 MySQL 5.6 版本的并行复制策略3.2 Ma…

CRM系统如何提高客户保留率?提高CRM客户关系

提高企业的客户保留率与CRM客户关系管理密切相关。CRM客户管理系统是企业用来进一步培养与客户关系的技术和技巧的结合。要与您的客户建立并保持这种联系&#xff0c;您可以参考正文的几个策略。下面来说说&#xff0c;CRM系统如何提高客户保留率&#xff1f; 提高客户保留率的…

推荐-25个开源软件

今天&#xff0c;我想让您对下一个 25 个出色的开源软件。您可以安装它&#xff0c;并且几乎开箱即用&#xff01; ⚠️使用软件前请检查是否安全️️ 1. Portmaster (Go) — 隐私保护者 Portmaster 由 Safing 开发&#xff0c;是一款开源软件&#xff0c;可帮助您保护在线活…

U2-Net论文解读

原文《U 2 -Net: Going Deeper with Nested U-Structure for Salient Object Detection》 目录 一、综述 二、EnCode编码器 三、DeCode解码器 四、特征图融合与目标函数 五、补充-空洞卷积 一、综述 U2-Net&#xff1a;基于堆叠U型结构的来加深网络&#xff0c;用于SOD&…

秋季期中考复现xj

flow analysis 1 What is the backdoor file name that comes with the server?( Including file suffix) 服务器自带的后门文件是什么&#xff1f;&#xff08;含文件后缀&#xff09; 题目还要求最后把那个文件名MD5一下&#xff0c;再去提交 开始的前三题是流量分析的&…

2.6.C++项目:网络版五子棋对战之数据管理模块-游戏房间管理模块的设计

文章目录 一、意义二、功能三、作用四、游戏房间类基本框架五、游戏房间管理类基本框架七、游戏房间类代码八、游戏房间管理类代码 一、意义 对匹配成功的玩家创建房间&#xff0c;建立起一个小范围的玩家之间的关联关系&#xff01; 房间里一个玩家产生的动作将会广播给房间里…

Dynamics 365 使用ILMerge 合并CRM开发后的DLL

很久以前写过一篇博文&#xff0c;关于用ILMerge 命令合并DLL,当时时纯敲命令行的&#xff0c;现在有了更简单的方式&#xff0c;只需要在NuGet下载如下两个包 另外插件引用第三方dll的新方案Preview来了&#xff0c;不久的将来就不需要使用ILMerge了

外汇天眼:过度交易是大忌,交易不是越多越好!

过度交易是交易中的大忌&#xff0c;因为交易并不是越多越好。为什么我们倾向于将交易失败归因于心态呢&#xff1f;这可能是因为我们认为一笔交易成功和失败的概率都是50%&#xff0c;从而让人们误以为他们具备盈利的能力。然而&#xff0c;如果我们具备盈利的能力&#xff0c…

提升APP的用户体验的方法

提高APP的用户体验&#xff08;User Experience&#xff0c;简称UX&#xff09;对于吸引用户、提高用户满意度和应用的成功至关重要。以下是一些方法&#xff0c;可以帮助改善APP的用户体验&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包…

【vue3】踩坑日记,vite与node版本对应(mac环境)

创建vue3vitets项目时&#xff0c;报错The requested module ‘vue’ does not provide an export named ‘computed’&#xff1b; node版本问题&#xff0c; Vite 需要 Node.js 版本 14.18&#xff0c;16&#xff1b; 升级node版本步骤&#xff1a; 先查看node的版本&#…

Elasticsearch集群搭建与相关知识点整理

前言&#xff1a;大家好&#xff0c;我是小威&#xff0c;24届毕业生&#xff0c;在一家满意的公司实习。本篇文章参考网上的课程&#xff0c;介绍Elasticsearch集群的搭建&#xff0c;以及Elasticsearch集群相关知识点整理。 如果文章有什么需要改进的地方还请大佬不吝赐教&am…

自动驾驶的商业应用和市场前景

自动驾驶技术已经成为了交通运输领域的一项重要创新。它不仅在改善交通安全性和效率方面具有巨大潜力&#xff0c;还为各种商业应用提供了新的机会。本文将探讨自动驾驶在交通运输中的潜力&#xff0c;自动驾驶汽车的制造商和技术公司&#xff0c;以及自动驾驶的商业模式和市场…

云栖大会?全部免费!!抢先一步看!

2023云栖大会定档10月31日&#xff01; 点击链接免费预约云栖门票&#xff1a; 2023云栖大会-领票页面 2023 云栖大会将于 10.31-11.2 在杭州云栖小镇举办&#xff0c;深度拥抱大数据AI 核心技术&#xff0c;见证阿里云大数据AI产品年度重磅发布及创新。开放融合的科技展示平…

Mysql数据库指定某数据库或某表赋予增删改查操作权限各类划分权限的方法总结实战

一、mysql创建用户只赋予指定数据库的增删改查操作权限 在日常生产运维工作中&#xff0c;我们经常需要给其他厂商或者合作伙伴提供数据库的账号&#xff0c;并且需要指定某个用户只能查询指定的数据库&#xff0c;并且赋予增删改查的指定权限。 &#xff08;1&#xff09;创…

执行 SQL 响应比较慢,你有哪些排查思路?

排查思路 如果执行 SQL 响应比较慢&#xff0c;我觉得可能有以下 4 个原因&#xff1a; 第 1 个原因&#xff1a;没有索引或者导致索引失效。 第 2 个原因&#xff1a;单表数据量数据过多&#xff0c;导致查询瓶颈第 3 个原因&#xff1a;网络原因或者机器负载过高。 第 4 个原…

Spring Cloud 之 GateWay简介及简单DEMO的搭建

&#xff08;1&#xff09;Filter&#xff08;过滤器&#xff09;&#xff1a; 和Zuul的过滤器在概念上类似&#xff0c;可以使用它拦截和修改请求&#xff0c;并且对上游的响应&#xff0c;进行二次处理。过滤器为org.springframework.cloud.gateway.filter.GatewayFilter类的…

【Java小知识点】类加载器的区别

&#x1f384;欢迎来到边境矢梦的csdn博文&#x1f384; &#x1f384;本文主要梳理Java类加载器的区别&#x1f384; &#x1f308;我是边境矢梦&#xff0c;一个正在为秋招和算法竞赛做准备的学生&#x1f308; &#x1f386;喜欢的朋友可以关注一下&#x1faf0;&#x1faf…

【Docker】Dockerfile使用技巧

开启Buildkit BuildKit是Docker官方社区推出的下一代镜像构建神器&#xff0c;可以更加快速&#xff0c;有效&#xff0c;安全地构建docker镜像。 尽管目前BuildKit不是Docker的默认构建工具&#xff0c;但是完全可以考虑将其作为Docker&#xff08;v18.09&#xff09;的首选…