队列的定义及基本操作实现(链式)

news/2024/10/30 13:38:37/

个人主页:【😊个人主页】
系列专栏:【❤️数据结构与算法】
学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高

系列文章目录

第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归


文章目录

  • 系列文章目录
  • 前言
  • 一.队列是什么?🧐🧐🧐
  • 二、队列与线性表的关系🆚🆚🆚
  • 三、队列的基本操作🔬🔬🔬
    • 1.队列的储存结构结构💻
    • 2.队列的初始化✨
    • 3. 入队🚗
    • 4.出队🚅
    • 5.清空与销毁🆘
  • 总结🎆🎆🎆


前言

在这里插入图片描述


一.队列是什么?🧐🧐🧐

和栈相反,队列( queue)是一种先进先出( First In First Out, FIFO) 的线性表。它只允许在表的一端进行插人,而在另一端删除元素。这和日常生活中的排队是一致的, 最早进入队列的元素最早离开。在队列中,允许插入的一端称为队尾( rear),允许删除的一端则称为队 头( front) 。假设队列为q=(a1,a2, .,an),那么,a就是队头元素, a,则是队尾元素。队列中的元素是按照a, a, … a,的顺序进人的,退出队列也只能按照这个次序依次退出,也就是说,只有在a,a., an,都离开队列之后,a,才能退出队列。

请添加图片描述

二、队列与线性表的关系🆚🆚🆚

与栈一样队列也是一种重要的线性结构。从数据结构角度看,队列也是线性表,其特殊性在于队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为具有限定性的数据结构。但从数据类型角度看,它是和线性表不相同的两类重要的抽象数据类型。


三、队列的基本操作🔬🔬🔬

1.队列的储存结构结构💻

typedef struct Qnode
{Elemtype data;struct Qnode* next;
}QNode, * QueuePrt;//建立链表
typedef struct
{QueuePrt front;QueuePrt rear;//指向头和尾的两个指针}LinkQueue;//建立队列

2.队列的初始化✨

InitQueue(LinkQueue* q)
{q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点if (!q->front)exit(0);q->front->next = NULL;
}//初始队列

其实就是链表中的创建头结点


3. 入队🚗

InsertQueue(LinkQueue *q, Elemtype e)
{QueuePrt p;p = (QueuePrt)malloc(sizeof(QNode));//创建结点if (p == NULL)exit(0);p->data = e;//赋值p->next = NULL;//q->rear->next = p;//头指针指向下一个结点q->rear = p;
}

在这里插入图片描述


4.出队🚅

DeletQueue(LinkQueue* q, Elemtype* e)
{QueuePrt p;if (q->front == q->rear)return 0;*e = p->data;q->front->next = p->next;if (q->rear == p)q->rear = q->front;free(p);
}

5.清空与销毁🆘

DesteoyQueue(LinkQueue* q)
{while (q->rear = q->front->next){free(q->front);q->front = q->rear;}
}

总结🎆🎆🎆

队列是一种先进先出的线性表。它只允许在表的一端进行插人, 而在另一端进行删除。队列也有两种存储表示,顺序表示(循环队列)和链式表示( 链队)。队列的主要操作是进队和出队,对于顺序表示的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。

#include<stdio.h>
#include<stdlib.h>
typedef int Elemtype;//定义类型
typedef struct Qnode
{Elemtype data;struct Qnode* next;
}QNode, * QueuePrt;//建立链表
typedef struct
{QueuePrt front;QueuePrt rear;//指向头和尾的两个指针}LinkQueue;//建立队列
InitQueue(LinkQueue* q)
{q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));//创建头结点if (!q->front)exit(0);q->front->next = NULL;
}//初始队列
InsertQueue(LinkQueue *q, Elemtype e)
{QueuePrt p;p = (QueuePrt)malloc(sizeof(QNode));//创建结点if (p == NULL)exit(0);p->data = e;//赋值p->next = NULL;//q->rear->next = p;//头指针指向下一个结点q->rear = p;
}
DeletQueue(LinkQueue* q, Elemtype* e)
{QueuePrt p;if (q->front == q->rear)return 0;*e = p->data;q->front->next = p->next;if (q->rear == p)q->rear = q->front;free(p);
}
DesteoyQueue(LinkQueue* q)
{while (q->rear = q->front->next){free(q->front);q->front = q->rear;}
}

(文章中图片与部分内容来源与网络,如有侵权请联系删除)
在这里插入图片描述


http://www.ppmy.cn/news/32571.html

相关文章

OV13850摄像头显示效果调试

前言在前面的博客 (14条消息) RK3568驱动OV13850摄像头模组调试过程_fhqlongteng的博客-CSDN博客 中讲述了RK3568驱动OV13850摄像头的过程&#xff0c;里面重点介绍了如何修改设备树驱动摄像对的过程。上面的驱动摄像头成功了&#xff0c;但是摄像头显示出来的画面很黑&#xf…

阿里p8测试总监,让我们用这份《测试用例规范》,再也没加班过

经常看到无论是刚入职场的新人&#xff0c;还是工作了一段时间的老人&#xff0c;都会对编写测试用例感到困扰&#xff1f;例如&#xff1a; 固然&#xff0c;编写一份好的测试用例需要&#xff1a;充分的需求分析能力 理论及经验加持&#xff0c;作为测试职场摸爬打滚的老人&…

15000 字的 SQL 语句大全 第一部分

一、基础 1、说明&#xff1a;创建数据库CREATE DATABASE database-name 2、说明&#xff1a;删除数据库drop database dbname 3、说明&#xff1a;备份sql server--- 创建 备份数据的 device USE master EXEC sp_addumpdevice disk, testBack, c:\mssql7backup\MyNwind_1.dat …

2023还有人不知道kubernetes?| 初步理解kubernetes

文章目录Kubernetes(K8s)一、Openstack&VM1、**认识虚拟化****1.1**、什么是虚拟化**1.2、虚拟化分类**2、OpenStack与KVM、VMWare2.1、OpenStack2.2、KVM2.3、VMWare二、容器&编排技术1、容器发展史1.1、Chroot1.2、FreeBSD Jails1.3、Solaris Zones1.4、LXC1.5、Dock…

JDBC指南

目录 第一阶段 JDBC地位 JDBC应用流程 JDBC应用流程详解 基础应用&#xff1a;"验证用户的登录"功能 Statement缺陷引出PreparedStatement 优化-"基础应用&#xff1a;验证用户的登录"功能 练习&#xff1a;操作数据库数据的增删改 练习&#xff1a;…

前端处理并发的最佳实践

什么是并发&#xff1f; 因为js是单线程的&#xff0c;所以前端的并发指的是在极短时间内发送多个数据请求&#xff0c;比如说循环中发送ajax。 举一个简单的例子&#xff1a; 下面一段代码是常规的mount阶段执行的请求&#xff1a; useEffect(async () > {console.time…

Spark高手之路1—Spark简介

文章目录Spark 概述1. Spark 是什么2. Spark与Hadoop比较2.1 从时间节点上来看2.2 从功能上来看3. Spark Or Hadoop4. Spark4.1 速度快4.2 易用4.3 通用4.4 兼容5. Spark 核心模块5.1 Spark-Core 和 弹性分布式数据集(RDDs)5.2 Spark SQL5.3 Spark Streaming5.4 Spark MLlib5.5…

SpringBoot IOC容器的高级特性

一、IOC 高级特性通过前面章节中对Spring IOC容器的源码分析&#xff0c;我们已经基本上了解了Spring IOC容器对Bean定义资源的定位、载入和注册过程&#xff0c;同时也清楚了当用户通过 getBean()方法向IOC容器获取被管理的Bean时&#xff0c;IOC 容器对 Bean 进行的初始化和依…