程序员经验分享-hwhale

C语言 队列（循环队列和链队初始化进出队等基本操作）

2023-11-05

目录

一、队列的定义

 二、循环队列

1、 循环队列的储存结构

2、初始化

3、输出队列元素

4、入队

5、出队

6、取队头元素

7、求队列长度

8、源代码

三、链式队列

1、队列的链式存储结构表示

2、初始化

3.输出队列元素

4.入队

5.出队

6.取队头元素

7. 源代码

总结

一、队列的定义

队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性表。

在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。这和日常生活中的排队时一致的，最早进入队列的元素最早离开。

常见队列有三种：循环队列、链式队列、双端队列。

双端队列又名double ended queue，简称deque，是队列的一种变形，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队

队列基本操作有：

  • 初始化队列：InitQueue（Q）
  • 判断队列是否为空：IsEmpty（Q）
  • 判断队列是否已满：IsFull（Q）
  • 入队操作：EnterQueue（Q，data）
  • 出队操作：DeleteQueue（Q，&data）
  • 取队首元素：GetHead（Q，&data）
  • 清空队列：ClearQueue(&Q)

 二、循环队列

 循环队列其实就是将数组的首尾相连，组成的一个特殊结构。头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1"的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

数据结构与算法（六）——循环队列的顺序存储结构（超详解，附动图+代码）_站在远方看童年的博客-CSDN博客_循环队列的顺序存储结构

1、 循环队列的储存结构

typedef struct {
	int* base;//储存空间的基地址
	int front;//头指针
	int rear;//尾指针
	int maxsize;//队列最大长度
}SqQueue;

2、初始化

动态分配一个大小为size的数组空间，base指向数组空间首地址。

SqQueue* InitQueue(int size) {
	SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针
	Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间
	//队列最大长度置为size，头指针尾指针置为0，队列为空
	Q->maxsize = size;
	Q->front = 0;
	Q->rear = 0;
	return Q;
}

3、输出队列元素

void print(SqQueue* Q) {
	printf("(front) ");
	int i;
	//跟遍历数组差不多，就是要通过模运算防止越界
	for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {
		printf("%d ", Q->base[i]);
	}
	printf("(rear)\n");
}

4、入队

入队指在队尾插入一个新元素。

bool EnQueue(SqQueue* Q, int e) {
	//插入e作为新队尾元素
	if ((Q->rear + 1) % Q->maxsize == Q->front)	return false;//尾指针在循环意义上加1后等于头指针说明队满
	Q->base[Q->rear] = e;//将元素e插入队尾
	Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1
	return true;
}

示例

初始化一个最大长度为5的队列，用循环将四个元素入队 ，最后输出。

5、出队

出队指将队头元素删除

bool DeQueue(SqQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];//用e保存队头元素
	Q->front = (Q->front + 1) % Q->maxsize;//头指针加1
	return true;
}

 示例

接着入队示例，出队三个元素，再入队两个元素，最后输出。

6、取队头元素

bool GetHead(SqQueue* Q, int* e) {
	//返回队头元素，不修改头指针
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];
	return true;
}

7、求队列长度

对于非循环队列，尾指针与头指针的差值就是队列长度；但是循环队列差值可能为负数，所以需要将差值加上maxsize再与maxsize求余。

int QueueLength(SqQueue* Q) {
	//返回队列元素个数
	return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;
}

8、源代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
	int* base;//储存空间的基地址
	int front;//头指针
	int rear;//尾指针
	int maxsize;//队列最大长度
}SqQueue;
//初始化
SqQueue* InitQueue(int size) {
	SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针
	Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间
	//队列最大长度置为size，头指针尾指针置为0，队列为空
	Q->maxsize = size;
	Q->front = 0;
	Q->rear = 0;
	return Q;
}
//输出
void print(SqQueue* Q) {
	printf("(front) ");
	int i;
	//跟遍历数组差不多，就是要通过模运算防止越界
	for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {
		printf("%d ", Q->base[i]);
	}
	printf("(rear)\n");
}
//入队
bool EnQueue(SqQueue* Q, int e) {
	//插入e作为新队尾元素
	if ((Q->rear + 1) % Q->maxsize == Q->front)	return false;//尾指针在循环意义上加1后等于头指针说明队满
	Q->base[Q->rear] = e;//将元素e插入队尾
	Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1
	return true;
}
//出队
bool DeQueue(SqQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];//用e保存队头元素
	Q->front = (Q->front + 1) % Q->maxsize;//头指针加1
	return true;
}
//取队头元素
bool GetHead(SqQueue* Q, int* e) {
	//返回队头元素，不修改头指针
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];
	return true;
}
//求队列长度
int QueueLength(SqQueue* Q) {
	//返回队列元素个数
	return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;
}
int main() {
	int i, n, e;
	SqQueue* Q = InitQueue(5);
	for (scanf("%d", &n), i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	for (scanf("%d", &n), i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
}

三、链式队列

链队列是指采用链式存储结构实现的队列。通常链队列用单链表来表示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队列添加一个头结点，并令头指针始终指向头结点。

当然也有用单向循环链表表示的队列,与单链表不同的是尾节点指向了头结点，所以只需

一个指针指向尾结点就可以实现基本操作。

1、队列的链式存储结构表示

typedef struct {
	int data;
	struct QNode* next;
}QNode;
typedef struct {
	QNode* front;//队头指针
	QNode* rear;//队尾指针
}LinkQueue;

2、初始化

链队的初始化操作就是构造一个只有一个头结点的空队。

LinkQueue* InitQueue() {
	LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针
	Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点
	Q->rear = Q->front;
	Q->front->next = NULL;//头结点指针域置空
	return Q;
}

3.输出队列元素

跟遍历链表一样，就是要判断队是否为空。

void print(LinkQueue *Q) {
	//前提为队不为空
	printf("(front) ");
	if (Q->front != Q->rear) {
		QNode* p = Q->front->next;
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
	}
	printf("(rear)\n");
}

4.入队

链队入队不需要判断队满，只需为入队元素动态分配一个结点空间。

void EnQueue(LinkQueue* Q, int e) {
	QNode* p = malloc(sizeof(QNode));//生成新结点
	p->data = e;//新结点数据域置为e，指针域置空
	p->next = NULL;
	Q->rear->next = p;//新结点插入队尾
	Q->rear = p;//修改队尾指针
}

示例

用循环将5个元素入队，最后输出队列。 

运行结果如下

5.出队

需要判断队是否为空，出队后可释放队头元素空间。

bool DeQueue(LinkQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;//p指向队头元素
	*e = p->data;//e保存队头元素
	Q->front->next = p->next;//修改头结点指针域
	if (Q->rear == p)	Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点
	free(p);//释放队头元素空间
	return true;
}

 示例

接着入队示例，出队一个元素并输出，最后输出队列

运行结果如下

6.取队头元素

bool GetHead(LinkQueue* Q, int* e) {
	//返回队头元素，不修改队头指针
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;
	*e =p->data;//用e返回队头元素值
	return true;
}

7. 源代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
	int data;
	struct QNode* next;
}QNode;
typedef struct {
	QNode* front;//队头指针
	QNode* rear;//队尾指针
}LinkQueue;
//初始化
LinkQueue* InitQueue() {
	LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针
	Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点
	Q->rear = Q->front;
	Q->front->next = NULL;//头结点指针域置空
	return Q;
}
//入队
void EnQueue(LinkQueue* Q, int e) {
	QNode* p = malloc(sizeof(QNode));//生成新结点
	p->data = e;//新结点数据域置为e，指针域置空
	p->next = NULL;
	Q->rear->next = p;//新结点插入队尾
	Q->rear = p;//修改队尾指针
}
//出队
bool DeQueue(LinkQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;//p指向队头元素
	*e = p->data;//e保存队头元素
	Q->front->next = p->next;//修改头结点指针域
	if (Q->rear == p)	Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点
	free(p);//释放队头元素空间
	return true;
}
//取队头元素
bool GetHead(LinkQueue* Q, int* e) {
	//返回队头元素，不修改队头指针
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;
	*e = p->data;//用e返回队头元素值
	return true;
}
//输出
void print(LinkQueue* Q) {
	//前提为队不为空
	printf("(front) ");
	if (Q->front != Q->rear) {
		QNode* p = Q->front->next;
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
	}
	printf("(rear)\n");
}
int main() {
	LinkQueue* Q = InitQueue();
	int i, n, e;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
	DeQueue(Q, &e);
	printf("%d\n", e);
	print(Q);
	return 0;
}

总结

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

c语言

数据结构

C语言 队列（循环队列和链队初始化进出队等基本操作） 的相关文章

  • Unity发布WebGL的填坑笔记

    an error occurred running the unity content on this page see your browser javascript console for more info the error was

  • VS2019-解决新建qt项目无法打开*.ui

    更新vs和qt项目管理 在解决方案资源管理器 在Form Files文件夹下的 ui右键 点击打开方式 单击添加 选自己的designer exe路径 绿色图标 本人的路径是 然后确认 无需退出vs2019 在上述路径下找到 Qt5WebE

随机推荐

  • UnityEngine.Screen.safeArea

    Unity 2017 2 1及以后 Screen safeArea会返回移动平台安全区的Rect 参考代码 public class SafeArea MonoBehaviour float safeArea left Start is c

  • 【致敬未来的攻城狮计划】--RA2E1 开发板测评（4）UART通讯

    前言 1 首先感谢 李肯前辈的活动 从而申请到了RA2L1开发板的测评 2 学习本文之前要具备的知识 致敬未来的攻城狮计划 RA2E1 开发板测评 1 keil环境配置 致敬未来的攻城狮计划 RA2E1 开发板测评 2 LED闪烁 3 本文

  • go 常用标准库之-time

    文章目录 go 常用标准库之 time 基本使用 时间戳 时间间隔 时间操作 Add Sub Equal Before After 时间格式化 字符串格式化成时间 时区 定时任务 go 常用标准库之 time 基本使用 time Time类

  • 配置自己的VLC转码参数(#transcode)

    刚接触vlc 查资料总能看到类似 sout transcode vcodec h264 scale 自动 acodec mpga ab 128 channels 2 samplerate 44100 scodec none no sout

  • 3分钟入门：Flex 布局

    flex 布局原理 全称 flexible box 弹性布局 如何开启 为元素添加 display flex 开启 flex 布局的元素 称为 flex 容器 flex container 其子元素成为容器成员 称为 flex 项目 fle

  • 华为eNSP实现ospf动态路由，STP，VRRP，DHCP、ACL、NAT、Telnet企业内网访问外网案例

    目录 一 背景 二 需求分析 三 拓扑搭建 四 项目实施步骤 一 项目背景 Xan20公司新建了一栋办公大楼作为分公司 为了满足日常的办公需求 公司决定为财务部 项目管理部 技术部 行政部和服务器群建立互联互通的有线网络 其中 为方便各部门

  • 贝叶斯网络—MATLAB学习笔记（1）

    快速导览 一 贝叶斯网络的原理 二 构建贝叶斯网络 1 matlab中添加贝叶斯网络构建工具FullBNT 2 实例分析 实例1 实例2 三 注意事项 四 所遇问题及解决方案 1 问题一 贝叶斯网络无箭头 2 问题二 draw graph函

  • 前端bootstrapTable添加行，删除行，获取选择数据，表格数据

    前端bootstrapTable获取选择数据 表格数据 1 获取表格所有数据 var allData tableId bootstrapTable getData 获取表格所有数据 2 获取表格选择的数据 var selectedModel

  • 【React】15课 react项目打包并运行

    react项目的打包 在该项目文件夹中打开终端输入 npm run build 项目打包命令 打包成功后文件夹中会多出一个 build 文件 该文件就是打包好的项目 react项目打包后的启动方法 我们如何启动该项目呢 首先我们全局安装li

  • 如何在matlab中画二元函数的图像,Matlab画怎么画这个二元函数图像

    www mh456 com防采集 二元函数可以用mesh或者surf函数画图 1 首先打开matlab 2 在 matlab 当前目录空间右键 3 然后点击 new gt M File 4 然后将文件命令为hello m 5 然后双击该文件

  • cos三次方积分_cos三次方的定积分

    求不定积分 cosx 的三次方dx 要求 要有最详细的过程 不要简写 一 详细过程如下 cos xdx cos xdsinx 1 sin x dsinx dsinx sin xdsinx sinx sin x 3 C 二 拓展资料 关于不定

  • 10. 数据类型 - 元组详解

    Hi 大家好 我是茶桁 之前两节分别介绍了字符串和列表 今天 我们来讲讲另外一个常用到的数据类型 元组 元组和列表很像 两者都是一组有序的数据的组合 但是也有很多不同点 比如元组内的元素一旦定义了就不可以再修改 因此元组称为不可变数据类型

  • UIKit框架之—— UIButton

    按钮通常使用 Touch Up Inside 事件来体现 能够抓取用户用手指按下并在该按钮上松开发生的事件 当检测到事件后 便可能触发相应视图控件中的操作 IBAction 创建一个按钮 初始化按钮的frame UIButton butto

  • DVWA系列Web常见漏洞XSS(DOM)源码分析及漏洞利用

    前言 本期主要讲解什么是基于DOM的XSS漏洞 XSS DOM 漏洞攻击实例 基于DOM的XSS漏洞产生的原因以及一般会在何处产生 最后讲解如何利用基于DOM的XSS漏洞 如XSS经典的窃取cookie等 DOM 全称Document Ob

  • 人脸检测(图像处理)

    FaceDetector类支持从指定的位图中检测出人脸所在的区域 检测结果用DetectedFace对象表示 人脸检测结果可以从DetectedFace类公开的FaceBox属性中获取 包含人脸区域相对于位图的位置 例如X和Y坐标 以及宽度

  • SIEM 中不同类型日志监控及分析

    安全信息和事件管理 SIEM 解决方案通过监控来自网络的不同类型的数据来确保组织网络的健康安全状况 日志数据记录设备上发生的每个活动以及整个网络中的应用程序 若要评估网络的安全状况 SIEM 解决方案必须收集和分析不同类型的日志数据 什么是

  • java需要掌握的知识点

    一阶段 JavaSE基础 第一步 夯实Java基础语法 1 Java语言的发展史 2 JDK的下载和安装 3 DOS命令的介绍和使用 4 Path环境变量的配置 5 第一个代码HelloWorld案例 6 NotePad 软件的安装和使用

  • 小程序踩坑

    1 swiper 点击 class不能使用原生名字 去掉round dot才能去掉点 2 转发 3 下拉刷新 json enablePullDownRefresh true 要及时关闭刷新等待 wx stopPullDownRefresh

  • 搭建前端环境

    搭建前端环境 一 安装好谷歌浏览器 二 官网下载地址 下载 Node js Node js默认安装目录为 C Program Files nodejs 你也可以修改目录 记住 一路都是 next 下一步 最后install 等安装好 在命令

  • C语言 队列（循环队列和链队初始化进出队等基本操作）

    目录 一 队列的定义 二 循环队列 1 循环队列的储存结构 2 初始化 3 输出队列元素 4 入队 5 出队 6 取队头元素 7 求队列长度 8 源代码 三 链式队列 1 队列的链式存储结构表示 2 初始化 3 输出队列元素 4 入队 5

热门标签