【数据结构】链式队列解析（C语言版）

数据结构——链队列解析过程和简单代码实现：
  • 一、简单概念：
    • 动图展示：
      • (1)入队：
      • (2)出队：
  • 二、顺序队列：
    • 思路
    • 步奏：
      • （1）入队操作：
      • （2）出队操作：
    • 简单实现代码：
  • 三、链式队列
    • （1）声明
    • （2）入队操作：
    • （3）出队操作：
    • （4）检查队列是否为空：
    • 全部代码：

一、简单概念：

队列，又称为伫列（queue），是先进先出（FIFO,First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加

与栈（stack）不同的是，队列是FIFO（First In First Out，先进先出），进入队列的一端叫尾部（rear），出队列的一端叫头部（front）。队列的主要操作也有两个：入队（offer）、出队（poll）

动图展示：

(1)入队：

在这里插入图片描述

从图中可以看到，A、B、C三个元素都是从队尾（rear）进入，就像现实生活中的排队，先来的就排在前面

(2)出队：

在这里插入图片描述

从图中可以看出，出队的顺序是A->B->C，也就是入队的顺序，即说明了队列是遵循FIFO的。队列的引用也十分广泛，锁的实现、生产者-消费者模型等都离不开队列

队列也有两种实现方式：顺序队列、链式队列

二、顺序队列：

思路

在顺序队列中，通常让队尾指针rear指向刚进队的元素的位置，让队首指针 front 指向刚出队的元素的位置。因此，元素进队的时候rear指针要向后移动，元素出队的时候front指针也要向后移动。这样经过一系列的操作后，两个指针最终会到达数组的末端处，虽然队中已没有了元素，但是仍然无法插入元素，这就是所谓的“假溢出”。

为了解决假溢出的问题，可以将数组弄成一个环状，让 rear 和 front 指针沿着环走，这样就不会出现无法继续走下去的情况，这样就产生了循环队列，如下图所示 :

  • 队空状态 ：qu.rear == qu.front

  • 队满状态 ： (qu.rear + 1) % Maxsize == qu.front

  • 元素的进队操作 ：qu.rear = (qu.rear + 1) % Maxsize ; qu.data[qu.rear] = x ;

  • 元素的出队操作 ：qu.front = (qu.front + 1) % Maxsize ; x = qu.data[qu.front] ;

本次思路中 元素入队时先移动指针，后存入元素；元素出队时也是先移动指针，后元素出队

步奏：

（1）入队操作：
int inQueue(Squeue &qu,int x)
{
    //判断队列是否已满，若满则无法入队
	if((qu.rear + 1) % Maxsize == qu.front)
	{
		return 0;
	}
    //队列没有满，则先移动指针，在插入元素
	qu.rear = (qu.rear + 1) % Maxsize;
	qu.data[qu.rear] = x;
	return 1; 
}
（2）出队操作：
int deQueue(Squeue &qu,int &x)
{
    //若队列已空，则无法取出元素
	if(qu.front == qu.rear)
	{
		return 0;
	}
    //否则先移动指针，再将元素取出
	qu.front = (qu.front + 1) % Maxsize;
	x = qu.data[qu.front];
	return 1;
}

简单实现代码：

//顺序队列
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 20
 
//定义队列的结构体 
typedef struct Squeue{
	int data[Maxsize];
	int front;
	int rear;
}Squeue; 
 
//初始化队列 
void InitQueue(Squeue &qu)
{
	qu.front = qu.rear = 0;
}
 
//判断队列是否为空 
int isQueueEmpty(Squeue qu)
{
	if(qu.front == qu.rear)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
 
//元素入队操作 
int inQueue(Squeue &qu,int x)
{
	//若队满则无法入队 
	if((qu.rear + 1) % Maxsize == qu.front)
	{
		return 0;
	}
	qu.rear = (qu.rear + 1) % Maxsize;
	qu.data[qu.rear] = x;
	return 1; 
}
 
//元素出队操作 
int deQueue(Squeue &qu,int &x)
{
	//若队空则无法出队 
	if(qu.front == qu.rear)
	{
		return 0;
	}
	qu.front = (qu.front + 1) % Maxsize;
	x = qu.data[qu.front];
	return 1;
}
 
int main()
{
	Squeue q;
	int i , n , x , a;
	InitQueue(q);
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		scanf("%d",&a);
		inQueue(q,a);
	}
	//当队列非空时，输出队列中所有数据 
	while(!isQueueEmpty(q))
	{
		deQueue(q,x);
		printf("%d ",x);
	}
	return 0;
}

三、链式队列

以 模拟患者在医院等待就诊的情况为例子 实现链式队列：

  • 患者到达诊室，将病历交给护士，排到等待队列中候诊
  • 护士从等待队列中取出下一位患者的病历，该患者进入诊室就诊
  • 功能如下：

1）排队： 输入排队患者的病历号（随机产生），加入到就诊患者排队队列中
2）就诊： 患者队列中最前面的病人就诊，并将其从队列中删除
3）查看： 从队首到队尾列出所有排队患者的病历号
4）下班： 退出运行

（1）声明

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


typedef int ElementType;

typedef struct Node{
	
	ElementType data;		//	存放数据 
	struct Node *next;		//	链表指针 
	
}Node;

typedef struct SeqQueue{
	
	Node *head;				//	队列头部 
	Node *wei; 				//	队列尾巴 
	ElementType size;		//	计算队列长度 
}Seq; 

typedef struct SeqQueue* Queue;		//	代表队列这个结构体指针

（2）入队操作：

//	创建链表，存放数据
Node *Create_Link(ElementType data)
{
	Node * new = (Node *)malloc(sizeof(Node));	//	开辟空间存数据 
	
	if(new == NULL)
	{
		printf("开辟空间失败\n");
	}
	
	new ->data = data;			//	存放队列数据
	new ->next = NULL;			//	让尾巴指向NULL
	
	return new;					//	返回节点指针
}

//	判断队列是否为空
bool QueueEmpty(Queue q) {

	if (q->head == NULL)
		return true;		//		队列为空
	return false;
}

//	入队 
Queue * Push(Queue sum,ElementType data)	
{
	Node *LinkHead = Create_Link(data);		//	接收链表空间节点指针
	Queue p = sum;
	if(QueueEmpty(p) == true){
	
		p->head = p->wei= LinkHead;		//		第一次赋值会进入 
	
		return p;			//	返回值指向队列的头指针
	}else{
		
		p->wei->next = LinkHead;		//		让队尾next指针指向这个空间 
		
		p->wei = LinkHead;				//		队尾指针存入这个空间 
	}
	
	p->size++;				//		计算队伍长度 
}

（3）出队操作：

//	出队 
ElementType Pop(Queue q)
{
	ElementType count;		//	取队列数据 
	Node *Link;				
	
	if(QueueEmpty(q) == true)
	{
		printf("数据已经从队列出完\n");
		q->wei = NULL;
		return -1;
	}
	
	Link = q->head;			//	让队列头给链表指针 
	count = Link->data;		//	链表头指针取出数据 
	q->head = Link->next;	//	让队列头指针移到链表头指针下一个节点位置，并指向它 
	free(Link);				//	释放已经出队的链表节点 
	
	return count;			//	返回取出的数据 
}

（4）检查队列是否为空：

//	判断队列是否为空
bool QueueEmpty(Queue q) {

	if (q->head == NULL)
		return true;		//		队列为空
	return false;
}

全部代码：

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


typedef int ElementType;

typedef struct Node{
	
	ElementType data;		//	存放数据 
	struct Node *next;		//	链表指针 
	
}Node;

typedef struct SeqQueue{
	
	Node *head;				//	队列头部 
	Node *wei; 				//	队列尾巴 
	ElementType size;		//	计算队列长度 
}Seq; 

typedef struct SeqQueue* Queue;

//	初始化队列 
void Init_SeqQueue(Queue q)
{
	q->head = NULL;
	q->wei  = NULL;
	q->size = 0;	
}

//	创建链表，存放数据
Node *Create_Link(ElementType data)
{
	Node * new = (Node *)malloc(sizeof(Node));	//	开辟空间存数据 
	
	if(new == NULL)
	{
		printf("开辟空间失败\n");
	}
	
	new ->data = data;			//	存放队列数据
	new ->next = NULL;			//	让尾巴指向NULL
	
	return new;					//	返回节点指针
}

//	判断队列是否为空
bool QueueEmpty(Queue q) {

	if (q->head == NULL)
		return true;		//		队列为空
	return false;
}

//	入队 
Queue Push(Queue sum,ElementType data)	
{
	Node *LinkHead = Create_Link(data);		//	接收链表空间节点指针
	Queue p = sum;
	if(QueueEmpty(p) == true){
	
		p->head = p->wei= LinkHead;		//		第一次赋值会进入 
	
		return p;			//	返回值指向队列的头指针
	}else{
		
		p->wei->next = LinkHead;		//		让队尾next指针指向这个空间 
		
		p->wei = LinkHead;				//		队尾指针存入这个空间 
	}
	
	p->size++;				//		计算队伍长度 
}

//	出队 
ElementType Pop(Queue q)
{
	ElementType count;		//	取队列数据 
	Node *Link;				
	
	if(QueueEmpty(q) == true)
	{
		printf("数据已经从队列出完\n");
		q->wei = NULL;
		return -1;
	}
	
	Link = q->head;			//	让队列头给链表指针 
	count = Link->data;		//	链表头指针取出数据 
	q->head = Link->next;	//	让队列头指针移到链表头指针下一个节点位置，并指向它 
	free(Link);				//	释放已经出队的链表节点 
	
	return count;			//	返回取出的数据 
}

//	初始化菜单 
void Init_Memu()
{
	printf("***********************************\n");
	printf("*          1.入队                 *\n");
	printf("*          2.出队                 *\n");
	printf("*          3.取队头元素           *\n");
	printf("*          4.查看队列是否为空     *\n");
	printf("*          5.插入队列(排队)       *\n");
	printf("*          6.就诊                 *\n");
	printf("*          7.查看                 *\n");
	printf("*          8.下班                 *\n");
	printf("***********************************\n");
	
}

//功能选择函数 
ElementType Choose_GN()
{
	int flag;
	scanf("%d",&flag);
	return flag;
}

//	主函数 
int main()
{
	Seq S_Queue;			//	创建队列结构体对象 
	Init_SeqQueue(&S_Queue);	//	初始化队列 
	Queue q = NULL;			 

	int temp;
	int num=0;
	while(1)
	{
		Init_Memu();
		printf("请选择你的需求:\n"); 
		temp =  Choose_GN();
		Node* p = NULL;
		switch(temp)
		{
			//	入队 
			case 1:
			{
				ElementType num;
				while(1){
					printf("请输入你要进队列的数据(输入0时结束输入):\n"); 
					scanf("%d",&num);
					if( num == 0)
					{
						break;
					}
					q = Push(&S_Queue,num);		//	接受队头指针head 
				}
			}
				break;
			
			//	出队	
			case 2:
			{
				int flag;
				while(1){
					flag = Pop(&S_Queue);
					if(flag == -1)
					{
						printf("出队列完毕\n");	
						break;
					}else{
						printf("出队数据为: %d\n",flag);
					}
				}
				
			}
				break;
			
			//	取队头元素	
			case 3:
			{
				ElementType sum;
				p = q->head;		//	取出队头指针 
				if( p == NULL)
				{
					printf("队伍已经出队，没有数据\n");
					break;
				} 
				sum = p->data;		//	队头指针取值 
			 
				printf("队列头数据为: %d \n",sum);
			}	
				break;
			
			//	查看队列是否为空	
			case 4:
			{
				if(QueueEmpty(q) == true)
				{
					printf("队伍为空\n");
				}else{
					printf("队伍还有数据,不为空\n"); 
				}
			}
				break;
			
			//	插入队列元素 
			case 5:
			{
				int s;
				printf("请输入你要添加到就诊队伍的病历号:\n");
				scanf("%d",&s);
				q = Push(q,s);		//	把输入的数据插入队列中 
				printf("添加成功！\n");	
			} 
				break;
			
			//	就诊	
			case 6:
			{
				ElementType count1;
				Node *Link1;
				
				Link1 = q->head;			//	取队头指针 
				count1 = Link1->data;		//	队头指针指向内容取值 
				q->head = Link1->next;		//	让队头指针移到下一个节点 
				free(Link1);				//	释放刚才那个头节点
				 
				printf("第%d 个患者开始就诊，病历号为: %d\n",++num,count1);
				
				if(QueueEmpty(q) == true)	//	判断队伍是否还有人 
				{
					printf("病人已经全部就诊完毕\n");
					break; 
				}
			}
				break;
			
			//	查看（相当于出队） 
			case 7:
			{
				int flag1;
				int i=0; 
				while(1){
					flag1 = Pop(&S_Queue);
					if(flag1 == -1)
					{
						printf("查看完毕完毕\n");	
						break;
					}else{
						printf("第%d 个患者病历号为: %d\n",++i,flag1);
					}
				}		
			}
				break;
			
			//	下班	
			case 8:
				printf("工作结束,打卡下班\n");
				exit(-1);		//	结束进程 
				
			default:printf("选择功能错误，请重新选择！！！！\n");break;
		}
		
	}
	
	return 0;
}

学习笔记，欢迎交流，共同进步

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

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

相关文章

Makefile编译原理 打造专业的编译环境

Makefile编译原理 打造专业的编译环境

一.打造专业的编译环境
阅读更多...
Spring Cloud Hystrix 参数配置、简单使用、DashBoard

Spring Cloud Hystrix 参数配置、简单使用、DashBoard

Spring Cloud Hystrix 文章目录 Spring Cloud Hystrix一、Hystrix 服务降级二、Hystrix使用示例三、OpenFeign Hystrix四、Hystrix参数HystrixCommand.Setter核心参数Command PropertiesFallback降级配置Circuit Breaker 熔断器配置Metrix 健康统计配置Request Context 相关参数…
阅读更多...
用C语言列出Linux或Unix上的网络适配器

用C语言列出Linux或Unix上的网络适配器

上代码&#xff1a; 1. #include <sys/socket.h> 2. #include <stdio.h> 3. 4. #include <netdb.h> 5. #include <ifaddrs.h> 6. 7. int main() { 8. struct ifaddrs *addresses; 9. if(getifaddrs(&addresses) -1) { 10. printf("…
阅读更多...
Lua 教程

Lua 教程

Lua 教程 (今天又又又开新坑啦) Lua 教程 手册简介 Lua 是一种轻量小巧的脚本语言&#xff0c;用标准C语言编写并以源代码形式开放。 手册说明 Lua是什么? Lua 是一个小巧的脚本语言。是巴西里约热内卢天主教大学&#xff08;Pontifical Catholic University of Rio de …
阅读更多...
《21天精通IPv4 to IPv6》第5天：IPv4与IPv6共存策略——如何为不同的系统实现IPv4与IPv6共存问题？

《21天精通IPv4 to IPv6》第5天：IPv4与IPv6共存策略——如何为不同的系统实现IPv4与IPv6共存问题？

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
c语言数据类型定义错误导致的数据溢出或者死循环

c语言数据类型定义错误导致的数据溢出或者死循环

数据溢出问题 #include <stdio.h>/* 数据溢出 */int main() {char i; // 数据表示范围[-128,127] 0xf0 ~ 0x7ffor(i0;i<130;i) // {printf("%d ",i);}return 0; }/* 编译运行上面的程序&#xff0c;你会发现程序陷入了死循环&#xff0c;一直在不断…
阅读更多...
你真的了解线性表中的顺序表了吗？（静态与动态顺序）

你真的了解线性表中的顺序表了吗？（静态与动态顺序）

今天开启我们数据结构中的第二篇文章了&#xff0c;过了几天我们今天就来了解了解我们常说的顺序表。 在这之前我们也先了解一下线性表。 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构&#…
阅读更多...
文件的操作（上）

文件的操作（上）

上一期代码题中我们补充一下&#xff0c;代码1中我们创建了一个指针变量来接收我们开辟的空间的首地址&#xff0c;出了函数只是变量被销毁&#xff0c;但是我们在堆区申请的空间却不会自己销毁&#xff0c;这样容易造成内存泄漏&#xff0c;只有等整个程序结束&#xff0c;才会…
阅读更多...
电气器件系列四十九：室内加热器（取暖器）

电气器件系列四十九：室内加热器（取暖器）

这个的注意事项有好大一堆&#xff0c;有几个地方挺有意思的&#xff0c;可以了解一下。 第2条&#xff0c;查了一下&#xff0c;小太阳是真的可以把旁边的东西烤到很高的温度并起火 4、可能造成开关的损坏和发热管的损坏&#xff0c;插入异物可能吧加热管搞坏 5、小太阳是发…
阅读更多...
Kafka集群安装与部署

Kafka集群安装与部署

集群规划 准备工作 安装 安装包下载&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1BtSiaf1ptLKdJiA36CyxJg?pwd6666 Kafka安装与配置 1、上传并解压安装包 tar -zxvf kafka_2.12-3.3.1.tgz -C /opt/moudle/2、修改解压后的文件名称 mv kafka_2.12-3.3.1/ kafka…
阅读更多...
KVM和JVM的虚拟化技术有何区别？

KVM和JVM的虚拟化技术有何区别？

随着虚拟化技术的不断发展&#xff0c;KVM和JVM已成为两种主流的虚拟化技术。尽管它们都提供了虚拟化的解决方案&#xff0c;但它们在实现方式、功能和性能方面存在一些重要的差异。本文将深入探讨KVM和JVM的虚拟化技术之间的区别。 KVM&#xff08;Kernel-based Virtual Mac…
阅读更多...
【VTKExamples::PolyData】第二十六期 IterateOverLine

【VTKExamples::PolyData】第二十六期 IterateOverLine

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ：870202403 前言 本文分享VTK样例IterateOverLine，讲解如何遍历线，希望对各位小伙伴有所帮助！ 感谢各位小伙伴的点赞+关注，小易会继续努力分享，一起进步！ 你的点赞就是我的动力(＾Ｕ＾)ノ~ＹＯ 1. IterateOverLine There…
阅读更多...
在Linux系统中设置全局HTTP代理的步骤与技巧

在Linux系统中设置全局HTTP代理的步骤与技巧

在Linux系统中&#xff0c;设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问&#xff0c;还可以在某些情况下绕过网络限制或实现匿名上网。下面&#xff0c;我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一&#xf…
阅读更多...
D7 Elasticsearch-Mongodb（搜索记录）

D7 Elasticsearch-Mongodb（搜索记录）

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 知…
阅读更多...
如何避免陷入穷忙的陷阱

如何避免陷入穷忙的陷阱

哈喽&#xff0c;你好啊&#xff0c;我是雷工&#xff01; 在2006年小日子过得不错的日本出了一部纪录片《穷忙族》&#xff0c; 记录了一些收入不多却整日奔波劳碌&#xff0c;虽然努力工作&#xff0c;却依然无法摆脱贫穷的一群人。 他们越忙越穷&#xff0c;越穷越忙&#…
阅读更多...
手把手教你开发Python桌面应用-PyQt6图书管理系统-图书信息表格数据显示及搜索实现

手把手教你开发Python桌面应用-PyQt6图书管理系统-图书信息表格数据显示及搜索实现

锋哥原创的PyQt6图书管理系统视频教程&#xff1a; PyQt6图书管理系统视频教程 Python桌面开发 Python入门级项目实战 (无废话版) 火爆连载更新中~_哔哩哔哩_bilibiliPyQt6图书管理系统视频教程 Python桌面开发 Python入门级项目实战 (无废话版) 火爆连载更新中~共计24条视频&…
阅读更多...
读完《王志纲谈生涯规划》后感

读完《王志纲谈生涯规划》后感

(点击即可收听) 经常在短视频刷到,这位王志钢老师,在微信读书里面也看到过,于是拜读了一下,这是一本生涯规划书,但更多的是他个人经历的一个描述 有大道理&#xff0c;有些话还是值得认可的 比如&#xff1a;他谈到,想要减少个人乃至社会的悲剧&#xff0c;最好的办法就是尽自己…
阅读更多...
Java学习第十一节之命令行传参和断更原因

Java学习第十一节之命令行传参和断更原因

package method;public class Demo03 {public static void main(String[] args) {//args.length数组长度for (int i 0; i < args.length; i) {System.out.println("args[" i "]:"args[i]);}}}为什么没更新了&#xff1f; 家里有长辈生病了不好在医院照…
阅读更多...
React18原理: 再聊Fiber架构下的时间分片

React18原理: 再聊Fiber架构下的时间分片

时间分片 react的任务可以被打断&#xff0c;其实就是基于时间分片的人眼最高能识别的帧数不超过30帧&#xff0c;电影的帧数差不多是在24浏览器的帧率一般来说是60帧&#xff0c;也就是每秒60个画面, 平均一个画面大概是16.5毫秒左右浏览器正常的工作流程是运算渲染&#xff…
阅读更多...
（已解决）将overleaf上的文章paper上传到arxiv上遇到的问题。

（已解决）将overleaf上的文章paper上传到arxiv上遇到的问题。

文章目录 前言初级问题后续问题 前言 首先说一点&#xff0c;将paper的pdf文件直接上传arxiv是不行的&#xff0c;arxiv要求我们要上传源文件&#xff0c;所以才这么麻烦。 初级问题 首先上传文件之后有可能会在下面这个界面出现问题&#xff0c;这里一般都比较常见的问题&a…
阅读更多...
最新文章

Copyright @ 2022~2023