【数据结构】14 队列（带头结点的链式存储和顺序存储实现）

定义

队列是一个有序线性表，但是队列的插入、删除操作是分别在线性表的两个不同端点进行的。
设一个队列 Q = ( a 1 , a 2 , . . . , a n ) Q = (a_1, a_2,...,a_n) Q=(a1​,a2​,...,an​)，那么 a 1 a_1 a1​被称为队头元素， a n a_n an​为队尾元素。假如将元素A,B,C,D依次插入队列，第一个从队列中删除的元素为A，即先插入的将被先删除，故队列也称为先进先出表。

抽象数据类型：
类型名称：队列
数据对象集：一个有0个或者多个元素的有穷线性表
操作集：对于一个长度为正整数MaxSize的队列 Q Q Q， 记队列中的任一元素 X X X，队列的基本操作集为：

  1. Queue CreateQueue(int MaxSize)
  2. bool IsFull(Queue Q)
  3. bool AddQ(Queue Q, ElementType X)
  4. bool Is Empty(Queue Q)
  5. ElementType DeleteQ(Queue Q)

队列的顺序存储实现

队列的最简单的表示方法是用数组。用数组存储队列有许多具体的方法。一般可以选择将队列头放数组下标小的位置，而将队列尾放在数组下标大的位置，并用两个变量Front和Rear分别指示队列的头和尾。一般把Front和Rear先初始化为-1。当有元素入队时，Rear向右移动一格，放入队尾元素；当有元素出队时，先将Front向右移动一格，再删除队首元素。
在这里插入图片描述
随着入队出队的进行会使整个队列整体向后移动这样就出现了如上图所示的现象，指针已经移到了最后，在再有元素入队时就会出现溢出，可是事实上此时队中并未真的满员，这种现象称为假溢出。

为了解决队尾溢出而实际上数组中仍有空余空间的问题，一般在队列的顺序存储结构中采用循环队列的方式，队尾指针和队首指针到达数组端点时能折回到数组开始处即相当于将数组头尾相接想象成环形，如图所示当插入和删除操作的作用单元达到数组的末端后用公式"Rear % 数组长度"取余运算就可以实现折返到起始单元。
在这里插入图片描述
队列初始化时，将Front和Rear都初始化为0，当插入一个元素时，Rear+1，删除一个元素时,Front加一。
当Front = Rear时，队列为空。
当队尾指针加1就会从后面赶上头指针，(Rear + 1)%数组长度 = Front
在这里插入图片描述

代码实现

顺序存储

数据结构

typedef int ElementType;
typedef int Position;
typedef struct QNode* PtrToQNode;
struct QNode {
	ElementType* Data;
	Position Front, Rear;
	int MaxSize;
};
typedef PtrToQNode Queue;

创建循环队列

Queue CreateQueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->MaxSize = MaxSize;
	Q->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);
	Q->Front = 0;
	Q->Rear = 0;
	return Q;
}

插入元素


bool IsFull(Queue Q) {
	if ((Q->Rear + 1) % Q->MaxSize == Q->Front) {
		return true;
	}
	else {
		return false;
	}
}

bool AddQ(Queue Q, ElementType X) {
	if (IsFull(Q)) {
		printf("The Queue is full!\n");
		return false;
	}
	else {
		Q->Rear = (Q->Rear + 1) % Q->MaxSize;
		Q->Data[Q->Rear] = X;
		return true;
	}
}

删除元素

bool IsEmpty(Queue Q) {
	if (Q->Rear == Q->Front) {
		return true;
	}
	else {
		return false;
	}
}


ElementType DeleteQ(Queue Q) {
	if (IsEmpty(Q)) {
		printf("The Queue is empty!\n");
		return -1;
	}
	else {
		Q->Front = (Q->Front + 1) % (Q->MaxSize);
		return Q->Data[(Q->Front)];


	}
}

完整代码

# include <stdio.h>
#include < stdlib.h>
#include <ctype.h>
#include <string.h>

typedef int ElementType;
typedef int Position;
typedef struct QNode* PtrToQNode;
struct QNode {
	ElementType* Data;
	Position Front, Rear;
	int MaxSize;
};
typedef PtrToQNode Queue;


Queue CreateQueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->MaxSize = MaxSize;
	Q->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);
	Q->Front = 0;
	Q->Rear = 0;
	return Q;
}

bool IsFull(Queue Q) {
	if ((Q->Rear + 1) % Q->MaxSize == Q->Front) {
		return true;
	}
	else {
		return false;
	}
}


bool AddQ(Queue Q, ElementType X) {
	if (IsFull(Q)) {
		printf("The Queue is full!\n");
		return false;
	}
	else {
		Q->Rear = (Q->Rear + 1) % Q->MaxSize;
		Q->Data[Q->Rear] = X;
		return true;
	}
}


void printQ(Queue Q) {
	int f = Q->Front;
	int r = Q->Rear;
	while (f != r) {
		f = (f + 1) % (Q->MaxSize);
		printf("QNode: %d\n", Q->Data[f]);
	}
}

bool IsEmpty(Queue Q) {
	if (Q->Rear == Q->Front) {
		return true;
	}
	else {
		return false;
	}
}


ElementType DeleteQ(Queue Q) {
	if (IsEmpty(Q)) {
		printf("The Queue is empty!\n");
		return -1;
	}
	else {
		Q->Front = (Q->Front + 1) % (Q->MaxSize);
		return Q->Data[(Q->Front)];


	}
}

int main() {

	Queue Q = CreateQueue(10);
	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (AddQ(Q, X) == false) {
			printf("Add error!\n");
		}

	}

	printQ(Q);
	while (!IsEmpty(Q)) {
		ElementType out = DeleteQ(Q);
		printf("Out : %d\n", out);
		printf("\n");
		printQ(Q);
	}
	



}

链式存储

队列的头必须指向的是队列的头结点，队尾指向链表的尾节点

数据结构

typedef int ElementType;
typedef struct Node* PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode Next;
};

typedef struct Node* Position;

struct QNode {
	Position Rear, Front;
	int MaxSize;
};
typedef struct QNode * Queue;

队列的创建

Queue CreateQueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->MaxSize = MaxSize;
	PtrToNode L = (PtrToNode)malloc(sizeof(struct Node));
	
	L->Next = NULL;
	Q->Front = L;
	Q->Rear = L;

	
	printf("finish!\n");

	return Q;


}

加入元素


bool IsFull(Queue Q) {
	int cnt = 0;
	
	Position t = Q->Front;
	
	while (t != Q->Rear) {
		t = t->Next;
		cnt++;
	}
	printf("cnt : %d\n", cnt);
	if (cnt == Q->MaxSize) {
		return true;
	}
	else {
		return false;
	}
}


bool AddQ(Queue Q, ElementType X) {
	if (IsFull(Q)) {
		printf("The Queue is full!\n");
		return false;
	}

	Position R = Q->Rear;
	while (R->Next != NULL) {
		R = R->Next;
	}
	PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
	t->Data = X;
	t->Next = R->Next;
	R->Next = t;
	Q->Rear = t;

	return true;


}

删除元素


bool IsEmpty(Queue Q) {
	if (Q->Front->Next == NULL) {
		return true;
	}
	else {
		return false;
	}
}

ElementType DeleteQ(Queue Q) {
	if(IsEmpty(Q)) {
		printf("The Queue is empty!\n");
		return -1;
	}
	else {

		ElementType t = Q->Front->Next->Data;
		Position te = Q->Front;
		Q->Front->Next = Q->Front->Next->Next;
		return t;
	}
}

完整代码

# include <stdio.h>
#include < stdlib.h>
#include <ctype.h>
#include <string.h>

typedef int ElementType;
typedef struct Node* PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode Next;
};

typedef struct Node* Position;

struct QNode {
	Position Rear, Front;
	int MaxSize;
};
typedef struct QNode * Queue;


Queue CreateQueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->MaxSize = MaxSize;
	PtrToNode L = (PtrToNode)malloc(sizeof(struct Node));
	
	L->Next = NULL;
	Q->Front = L;
	Q->Rear = L;

	
	printf("finish!\n");

	return Q;


}

bool IsFull(Queue Q) {
	int cnt = 0;
	
	Position t = Q->Front;
	
	while (t != Q->Rear) {
		t = t->Next;
		cnt++;
	}
	printf("cnt : %d\n", cnt);
	if (cnt == Q->MaxSize) {
		return true;
	}
	else {
		return false;
	}
}


bool AddQ(Queue Q, ElementType X) {
	if (IsFull(Q)) {
		printf("The Queue is full!\n");
		return false;
	}

	Position R = Q->Rear;
	while (R->Next != NULL) {
		R = R->Next;
	}
	PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
	t->Data = X;
	t->Next = R->Next;
	R->Next = t;
	Q->Rear = t;

	return true;


}

void printq(Queue Q) {
	Position t = Q->Front;
	while (t != Q->Rear)
	{
		t = t->Next;
		printf("QNode: %d\n", t->Data);
	}

}

bool IsEmpty(Queue Q) {
	if (Q->Front->Next == NULL) {
		return true;
	}
	else {
		return false;
	}
}

ElementType DeleteQ(Queue Q) {
	if(IsEmpty(Q)) {
		printf("The Queue is empty!\n");
		return -1;
	}
	else {

		ElementType t = Q->Front->Next->Data;
		Position te = Q->Front;
		Q->Front->Next = Q->Front->Next->Next;
		return t;
	}
}

int main() {

	Queue Q = CreateQueue(10);

	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (AddQ(Q, X) == false) {
			printf("Add error!\n");
		}

	}

	printq(Q);
	while (!IsEmpty(Q)) {
		int out = DeleteQ(Q);
		printf("\n");
		printf("Out : %d\n", out);
		//printq(Q);
	}
	


}

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

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

相关文章

【实战】一、Jest 前端自动化测试框架基础入门 —— 前端要学的测试课 从Jest入门到TDD BDD双实战（一）

【实战】一、Jest 前端自动化测试框架基础入门 —— 前端要学的测试课 从Jest入门到TDD BDD双实战（一）

文章目录 一、前端要学的测试课1.前端要学的测试2.前端工程化的一部分3.前端自动化测试的例子4.前端为什么需要自动化测试&#xff1f;5.课程涵盖内容6.前置技能7.学习收获 二、Jest 前端自动化测试框架基础入门1. 自动化测试背景及原理前端自动化测试产生的背景及原理 2.前端自…
阅读更多...
Javaweb之SpringBootWeb案例之事务进阶的详细解析

Javaweb之SpringBootWeb案例之事务进阶的详细解析

1.3 事务进阶 前面我们通过spring事务管理注解Transactional已经控制了业务层方法的事务。接下来我们要来详细的介绍一下Transactional事务管理注解的使用细节。我们这里主要介绍Transactional注解当中的两个常见的属性&#xff1a; 异常回滚的属性&#xff1a;rollbackFor 事…
阅读更多...
springboot179基于javaweb的流浪宠物管理系统的设计与实现

springboot179基于javaweb的流浪宠物管理系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…
阅读更多...
【C++】STL之string 超详解

【C++】STL之string 超详解

目录 1.string概述 2.string使用 1.构造初始化 2.成员函数 1.迭代器 2.容量操作 1.size和length 返回字符串长度 2.resize 调整字符串大小 3.capacity 获得字符串容量 4.reserve 调整容量 5.clear 清除 6.empty 判空 3.string插入、追加 、拼接 1.运算…
阅读更多...
【MySQL】MySQL函数学习和总结

【MySQL】MySQL函数学习和总结

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-Ny0xnYjfHqF7s3aS {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…
阅读更多...
【DDD】学习笔记-精炼领域分析模型

【DDD】学习笔记-精炼领域分析模型

通过统一语言与“名词动词法”可以迫使团队研究问题域的词汇表&#xff0c;简单而快速地帮助我们获得初步的分析模型。但是这种方法获得的模型品质&#xff0c;受限于语言描述的写作技巧&#xff0c;统一语言的描述更多体现在是对现实世界的模型描述&#xff0c;缺乏深入精准的…
阅读更多...
招商证券流年不利：屡因保荐失职“连坐”，各业务分部收入下滑

招商证券流年不利：屡因保荐失职“连坐”，各业务分部收入下滑

近日&#xff0c;安徽证监局发布公告称&#xff0c;招商证券股份有限公司&#xff08;下称“招商证券”&#xff09;“15城六局”债券的受托管理方面存在未督导发行人做好募集资金管理、未持续跟踪和监督发行人履行有关信披临时报告义务等情形。 根据《公司债券发行与交易管理…
阅读更多...
Java中的IO介绍

Java中的IO介绍

本章内容 一 、File概念 File可以代表一个目录或者一个文件&#xff0c;并不能代表文件的内容 文件和流的区别&#xff1a;File关注的是文件本身的特征&#xff0c;如名称、路径、修改时间、大小。 流关注的是文件的内容。 二、File基本的操作 常见构造方法 | File(String p…
阅读更多...
nginx2

nginx2

mkdir /usr/local/develop cd /usr/local/develop 下载 wget http://nginx.org/download/nginx-1.17.4.tar.gz yum install git git clone https://github.com/arut/nginx-rtmp-module.git 解压文件 tar zxmf nginx-1.17.4.tar.gz 进入解压目录 cd nginx-1.17.4/ 安装编译…
阅读更多...
EMC学习笔记（二十六）降低EMI的PCB设计指南（六）

EMC学习笔记（二十六）降低EMI的PCB设计指南（六）

降低EMI的PCB设计指南&#xff08;六&#xff09; 1.PCB布局1.1 带键盘和显示器的前置面板PCB在汽车和消费类应用中的应用1.2 敏感元器件的布局1.3 自动布线器 2.屏蔽2.1 工作原理2.2 屏蔽接地2.3 电缆屏蔽至旁路2.4 缝隙天线&#xff1a;冷却槽和缝隙 tips&#xff1a;资料主要…
阅读更多...
蓝桥杯嵌入式第六届真题（完成）STM32G431

蓝桥杯嵌入式第六届真题（完成）STM32G431

蓝桥杯嵌入式第六届真题&#xff08;完成&#xff09;STM32G431 题目部分 相关文件 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program b…
阅读更多...
windows11 MSYS2下载安装教程

windows11 MSYS2下载安装教程

MSYS2 可以理解为在windows平台上模拟linux编程环境的开源工具集 当前环境&#xff1a;windows11 1. 下载 官网地址可下载最新版本&#xff0c;需要科学上网 https://www.msys2.org/ 2. 安装 按照正常安装软件流程一路next就可以 打开 3. 配置环境 网上很多教程提到需…
阅读更多...
基于multiprocessing.pool的多进程池与单进程访问多网页的比较示例

基于multiprocessing.pool的多进程池与单进程访问多网页的比较示例

一、示例代码&#xff1a; from multiprocessing import Pool import time import requestsurls [ # URL队列&#xff0c;通过多进程访问http://www.python.org,http://www.python.org/about/,http://www.python.org/doc/,http…
阅读更多...
【JavaEE】_CSS选择器

【JavaEE】_CSS选择器

目录 1. 基本语法格式 2. 引入方式 2.1 内部样式 2.2 内联样式 2.3 外部样式 3. 基础选择器 3.1 标签选择器 3.2 类选择器 3.3 ID选择器 4. 复合选择器 4.1 后代选择器 4.2 子选择器 4.3 并集选择器 4.4 伪类选择器 1. 基本语法格式 选择器若干属性声明 2. 引入…
阅读更多...
模拟串口LV2,解决硬件串口资源不足问题！！！！

模拟串口LV2,解决硬件串口资源不足问题！！！！

模拟串口通信 2.0 版本&#xff01;&#xff01; 我在前面的文章里面有写了 虚拟串口通信&#xff0c;虽然说能用&#xff0c;但是用过的小伙伴都说 “好!” 优缺点: 先说一点&#xff0c;2.0版本并不适用于同硬件串口的所有场合&#xff0c;仅仅针对自己开发的电子垃圾的主…
阅读更多...
Python - 面向对象编程 - 类变量、实例变量/类属性、实例属性

Python - 面向对象编程 - 类变量、实例变量/类属性、实例属性

什么是对象和类 什么是 Python 类、类对象、实例对象 类变量、实例变量/类属性、实例属性 前言 只是叫法不一样 实例属性 实例变量 类属性 类变量 个人认为叫属性更恰当 类属性和实例属性区别 类属性&#xff0c;所有实例对象共享该属性实例属性&#xff0c;属于某一…
阅读更多...
【MySQL】操作库 —— 库的操作 -- 详解

【MySQL】操作库 —— 库的操作 -- 详解

一、增删数据库 1、创建数据库 create database db_name; 本质就是在 /var/lib/mysql 创建一个目录。 说明&#xff1a; 大写的表示关键字。[ ] 是可选项。CHARACTER SET&#xff1a;指定数据库采用的字符集。COLLATE&#xff1a;指定数据库字符集的校验规则。 2、数据库删除…
阅读更多...
Python||数据分析之pyecharts 绘图（词云、气泡）

Python||数据分析之pyecharts 绘图（词云、气泡）

1. echarts 和 Pyecharts 简介 1.1echarts 简介: • echarts 是一个使用 JavaScript 实现的开源可视化库，涵盖各行业图表，满足各种需求。 • echarts 遵循 Apache-2.0 开源协议，免费商用。 • ECharts 最初由百度团队开源，并于 2018 年初捐赠给 Apache 基金会，成为 AS…
阅读更多...
算法day12

算法day12

算法day12 二叉树理论基础114 二叉树的前序遍历145 二叉树的后序遍历94 二叉树的中序遍历迭代法 二叉树理论基础 直接看代码随想录就完事了&#xff0c;之前考研也学过&#xff0c;大概都能理解 我这里就说说代码层面的。 二叉树的存储&#xff1a; 1、链式存储&#xff1a;这…
阅读更多...
内容检索（2024.02.12）

内容检索（2024.02.12）

随着创作数量的增加&#xff0c;博客文章所涉及的内容越来越庞杂&#xff0c;为了更为方便地阅读&#xff0c;后续更新发布的文章将陆续在此做简介并附上原文链接&#xff0c;感兴趣的小伙伴们可持续关注文章发布动态&#xff1a; 信号仿真类话题如何看待频域与时域的仿真差别-…
阅读更多...
最新文章

Copyright @ 2022~2023