数据结构与算法学习笔记三---队列的表示和实现(C语言)

ops/2024/10/23 3:10:33/

目录

前言

1.定义         

2.队列的表示和实现

1.链队列

1.定义

2.初始化

3.入队

4.出队

5.队列为空

6.队列长度

7.清空队列

8.获取队首元素

9.完整代码

2.顺序队列

1.定义

2.初始化

3.入队

4.出队

5.队列为空

6.队列长度

7.清空队列

8.获取队首元素

9.完整代码

前言

        这篇博客主要讲队列的用法。

1.定义         

        队列是一种常见的数据结构，它按照先进先出（FIFO，First In First Out）的原则管理元素。队列可以被看作是一个有限长度的线性表，它有两个主要的操作：入队和出队。

1. 入队（enqueue）：将新元素添加到队列的末尾。
2. 出队（dequeue）：从队列的头部移除并返回元素。

        队列的特点是只能在队列的一端进行插入（入队），在另一端进行删除（出队）。这种操作方式保证了队列中的元素按照其添加的顺序被处理。除了入队和出队操作，队列通常还包括以下常用操作：

1.队列是否为空（isEmpty）：判断队列中是否有元素。
2.队列的长度（size）：返回队列中元素的数量。
3.获取队首元素（front）：返回队列中的第一个元素，但不从队列中移除它。

         队列的应用十分广泛，例如：

1.在计算机科学中，队列常用于实现广度优先搜索算法（BFS）、任务调度等。
2.在操作系统中，队列可用于实现进程调度、缓存管理等。
3. 在网络通信中，队列用于数据包的传输与接收。
4.在生活中，队列的概念也常见于排队等待购票、排队买东西等场景。

2.队列的表示和实现

        队列可以分别使用顺存和链式两种存储方式实现。

1.链队列

        使用链式存储结构表示队列。

1.定义

        和单链表的定义相同，我们需要定义队列的指针域和值域。

// 节点类型定义
typedef struct QNode{int data;//元素struct QNode * next;//指向下一个节点的指针
}QNode,*QueuePtr;typedef struct {QueuePtr front; // 队首指针QueuePtr rear;  // 队尾指针
}LinkQueue;

2.初始化

        初始化队列的时候，首先给队列分配存储空间，然后设置队首指针和队尾指针

// 初始化队列
int initQueue(LinkQueue *queue) {queue->front = queue->rear = (QueuePtr)malloc(sizeof(QNode));if (!queue->front) {return 0;}queue->front->next = NULL;return 1;
}

3.入队

        入队的时候，首先生成一个新节点，节点的值域指向我们传递的数据元素，然后把新节点插入到队尾。

// 入队
int EnQueue(LinkQueue *queue, int element) {QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode)); // 新节点if (!newNode) { // 存储分配失败return 0;}newNode->data = element;newNode->next = NULL;queue->rear->next = newNode; // 新节点插入到队列尾部queue->rear = newNode;       // 更新队尾指针return 1;
}

4.出队

        出队列的时候，修改队首指针。这里要注意的是如果队列中只有一个数据元素的时候，要更新下尾节点指针。

// 出队
int DeQueue(LinkQueue *queue, int *element) {if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}QueuePtr temp = queue->front->next; // 暂存队首节点*element = temp->data;              // 获取要出队的元素值queue->front->next = temp->next;    // 更新队首指针if (queue->rear == temp) {queue->rear = queue->front;     // 如果出队后队列为空，更新队尾指针}free(temp);                         // 释放出队节点的内存return 1; // 出队成功
}

5.队列为空

        队首和队尾相同的时候，队列为空。

// 是否为空队列
int QueueEmpty(LinkQueue *queue) {return queue->front == queue->rear;
}

6.队列长度

        遍历队列中的数据元素。

// 队列长度
void QueueLength(LinkQueue *queue) {int length = 0;QueuePtr p = queue->front->next;while (p) {length++;p = p->next;}printf("队列长度：%d\n", length);
}

7.清空队列

        遍历队列中的数据元素，释放数据元素的存储空间。

// 清空队列
void clearQueue(LinkQueue *queue) {QueuePtr p = queue->front->next;while (p) {QueuePtr temp = p;p = p->next;free(temp);}queue->front->next = NULL;queue->rear = queue->front;
}

8.获取队首元素

// 获取队首元素
void getQueueHead(LinkQueue *queue) {if (QueueEmpty(queue)) {printf("队列为空，无法获取队首元素！\n");} else {printf("队首元素：%d\n", queue->front->next->data);}
}

9.完整代码

        

#include <stdlib.h>// 节点类型定义
typedef struct QNode{int data;//元素struct QNode * next;//指向下一个节点的指针
}QNode,*QueuePtr;typedef struct {QueuePtr front; // 队首指针QueuePtr rear;  // 队尾指针
}LinkQueue;
// 初始化队列
int initQueue(LinkQueue *queue) {queue->front = queue->rear = (QueuePtr)malloc(sizeof(QNode));if (!queue->front) {return 0;}queue->front->next = NULL;return 1;
}// 入队
int EnQueue(LinkQueue *queue, int element) {QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode)); // 新节点if (!newNode) { // 存储分配失败return 0;}newNode->data = element;newNode->next = NULL;queue->rear->next = newNode; // 新节点插入到队列尾部queue->rear = newNode;       // 更新队尾指针return 1;
}// 出队
int DeQueue(LinkQueue *queue, int *element) {if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}QueuePtr temp = queue->front->next; // 暂存队首节点*element = temp->data;              // 获取要出队的元素值queue->front->next = temp->next;    // 更新队首指针if (queue->rear == temp) {queue->rear = queue->front;     // 如果出队后队列为空，更新队尾指针}free(temp);                         // 释放出队节点的内存return 1; // 出队成功
}// 打印队列中的数据元素
void printQueue(LinkQueue *queue) {if (queue->front == queue->rear) {printf("队列为空\n");return;}QueuePtr p = queue->front->next;printf("队列元素：");while (p) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 是否为空队列
int QueueEmpty(LinkQueue *queue) {return queue->front == queue->rear;
}// 队列长度
void QueueLength(LinkQueue *queue) {int length = 0;QueuePtr p = queue->front->next;while (p) {length++;p = p->next;}printf("队列长度：%d\n", length);
}// 清空队列
void clearQueue(LinkQueue *queue) {QueuePtr p = queue->front->next;while (p) {QueuePtr temp = p;p = p->next;free(temp);}queue->front->next = NULL;queue->rear = queue->front;
}// 获取队首元素
void getQueueHead(LinkQueue *queue) {if (QueueEmpty(queue)) {printf("队列为空，无法获取队首元素！\n");} else {printf("队首元素：%d\n", queue->front->next->data);}
}void test_queue(void) {LinkQueue queue;// 初始化队列printf("初始化队列...\n");if (initQueue(&queue)) {printf("队列初始化成功！\n");} else {printf("队列初始化失败！\n");}// 入队元素 10printf("入队元素 10...\n");if (EnQueue(&queue, 10)) {printf("入队成功！\n");} else {printf("入队失败！\n");}// 入队元素 20printf("入队元素 20...\n");if (EnQueue(&queue, 20)) {printf("入队成功！\n");} else {printf("入队失败！\n");}// 入队元素 30printf("入队元素 30...\n");if (EnQueue(&queue, 30)) {printf("入队成功！\n");} else {printf("入队失败！\n");}// 打印队列printf("当前队列：\n");printQueue(&queue);// 出队int element;printf("出队元素...\n");if (DeQueue(&queue, &element)) {printf("出队元素：%d\n", element);} else {printf("队列为空，出队失败！\n");}// 打印队列printf("当前队列：\n");printQueue(&queue);// 获取队首元素printf("获取队首元素...\n");getQueueHead(&queue);// 清空队列printf("清空队列...\n");clearQueue(&queue);// 打印队列printf("当前队列：\n");printQueue(&queue);
}

2.顺序队列

1.定义

        队列的顺序类型定义中，base表示队列的基地址，front表示队首指针，rear表示队尾指针。

#define MAXQSIZE 100 //最大队列长度
typedef struct{int * base;//队列基址int front; //队首指针,若队列不为空 指向队列头元素int rear;  //队尾指针 若队尾不为空 指向队尾指针元素的下一个位置
}SeqQueue;

2.初始化

        初始化队列的时候，首先分配存储空间，然后队首和队尾的数据元素都为0；

// 初始化队列
int initSeqQueue(SeqQueue *seqQueue){seqQueue->base = (int *)malloc(sizeof(int) * MAXQSIZE);if (!seqQueue->base) {return 0;}seqQueue->front = seqQueue->rear = 0;return 1;
}

3.入队

        判断是否对满，对满的时候无法入队，入队之后rear++。

// 入队
int EnSeqQueue(SeqQueue *queue,int element){if (queue->rear >= MAXQSIZE ) {return 0;}queue->base[queue->rear++] = element;return 1;
}

4.出队

        出队的时候判断队列是否为空，不为空的话,front++。

// 出队
int DeSeqQueue(SeqQueue *queue, int *element){if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}*element = queue->base[queue->front]; // 获取队首元素queue->front++; // 更新队首指针return 1; // 出队成功
}

5.队列为空

        队首和队尾相同的时候，队列为空。

// 是否为空队列
int seqQeueEmpty(SeqQueue *seqQueue){return seqQueue->front == seqQueue->rear;
}

6.队列长度

        遍历队列中的数据元素。

// 队列长度
int seqQueueLength(SeqQueue * seqQueue){return seqQueue->rear - seqQueue->front;
}

7.清空队列

        遍历队列中的数据元素，释放数据元素的存储空间。

// 清空队列
void clearQueue(LinkQueue *queue) {QueuePtr p = queue->front->next;while (p) {QueuePtr temp = p;p = p->next;free(temp);}queue->front->next = NULL;queue->rear = queue->front;
}

8.获取队首元素

        首先判断队列是否为空，空队列无法获取队首元素。

// 队列首元素
int getSeqQueueHead(SeqQueue * seqQueue,int * element){if (!seqQeueEmpty(seqQueue)) {* element = seqQueue->base[seqQueue->front];return 1;}return 0;
}

9.完整代码

        

#include <stdlib.h>
#include <stdio.h>#define MAXQSIZE 5 //最大队列长度
typedef struct{int * base;//队列基址int front; //队首指针,若队列不为空 指向队列头元素int rear;  //队尾指针 若队尾不为空 指向队尾指针元素的下一个位置
}SeqQueue;// 打印队列中的数据元素
void printSeqQueue(SeqQueue *queue){for (int i = 0; i<queue->rear; i++) {printf("%d\t",queue->base[i]);}printf("\n");
}// 初始化队列
int initSeqQueue(SeqQueue *seqQueue){seqQueue->base = (int *)malloc(sizeof(int) * MAXQSIZE);if (!seqQueue->base) {return 0;}seqQueue->front = seqQueue->rear = 0;return 1;
}
// 出队
int DeSeqQueue(SeqQueue *queue, int *element){if (queue->front == queue->rear) {return 0; // 队列为空，出队失败}*element = queue->base[queue->front]; // 获取队首元素queue->front++; // 更新队首指针return 1; // 出队成功
}
// 入队
int EnSeqQueue(SeqQueue *queue,int element){if (queue->rear >= MAXQSIZE ) {return 0;}queue->base[queue->rear++] = element;return 1;
}// 是否为空队列
int seqQeueEmpty(SeqQueue *seqQueue){return seqQueue->front == seqQueue->rear;
}// 队列长度
int seqQueueLength(SeqQueue * seqQueue){return seqQueue->rear - seqQueue->front;
}// 清空队列
void clearSeqQueue(SeqQueue * seqQueue){seqQueue->front = seqQueue->rear = 0;
}
// 销毁队列
void destroySeqQueue(SeqQueue * seqQueue){if (seqQueue->base) {free(seqQueue->base);seqQueue->base = NULL;}seqQueue->front = seqQueue->rear = 0;
}
// 队列首元素
int getSeqQueueHead(SeqQueue * seqQueue,int * element){if (!seqQeueEmpty(seqQueue)) {* element = seqQueue->base[seqQueue->front];return 1;}return 0;
}
//创建测试队列
SeqQueue createTestSeqQueue(SeqQueue seqQueue){int success = 0;for (int i = 1; i<= 5; i++) {if (EnSeqQueue(&seqQueue, 10 * i)) {//入队成功success = 1;}else{break;}}return seqQueue;
}void testSeqQueue(void){SeqQueue seqQueue;printf("队列初始化.......\n");if(initSeqQueue(&seqQueue)){printf("队列初始化成功\t✅\n");}else{printf("队列初始化失败\n");}//测试入队for (int i = 1; i<= 5; i++) {//入队if (EnSeqQueue(&seqQueue, 10 * i)) {printf("第%d次入队 数据入队数据元素:%d 成功! 入队之后front = %d\t rear=%d\t\t✅\n",i,10 * i,seqQueue.front,seqQueue.rear);}else{printf("入队失败!");}}printf("\n********************\t队列长度和队列是否为空测试\t********************\n");printf("\n********************\t队列中的数据元素\t********************\n");printSeqQueue(&seqQueue);if (!seqQeueEmpty(&seqQueue)) {printf("\n队列不为空\t队列长度为:%d\t✅\n",seqQueueLength(&seqQueue));}int queueHeadElement;if (getSeqQueueHead(&seqQueue, &queueHeadElement)) {printf("队列首元素:%d\n",queueHeadElement);}printf("\n********************\t队列清空测试\t********************\n");clearSeqQueue(&seqQueue);if (seqQeueEmpty(&seqQueue)) {printf("队列为空,清空测试通过\t✅\n");}printf("\n********************\t队列销毁测试\t********************\n");seqQueue = createTestSeqQueue(seqQueue);printf("销毁之前队列:\n");destroySeqQueue(&seqQueue);if (seqQueueLength(&seqQueue)==0) {printf("队列为空,队列销毁成功\t✅\n");}printSeqQueue(&seqQueue);
}int main(int argc, const char *argv[]) {testSeqQueue();return 0;
}

http://www.ppmy.cn/ops/25969.html

相关文章

K8S集群安装

K8S集群安装

安装Docker sudo yum remove docker* sudo yum install -yum-utils ​ #配置docker的yum镜像仓库 sudo yum-config-manager \ --add-rep \ https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo ​ #安装指定版本docker... sudo yum install -y docker-ce-19.03…
阅读更多...
视觉语言模型详解

视觉语言模型详解

视觉语言模型可以同时从图像和文本中学习&#xff0c;因此可用于视觉问答、图像描述等多种任务。本文&#xff0c;我们将带大家一览视觉语言模型领域: 作个概述、了解其工作原理、搞清楚如何找到真命天“模”、如何对其进行推理以及如何使用最新版的 trl 轻松对其进行微调。 什…
阅读更多...
开发一个语音聊天社交app小程序H5需要多少钱？

开发一个语音聊天社交app小程序H5需要多少钱？

社交&#xff0c;即时通讯APP系统。如何开发一个社交App||开发一个即时通信应用是一项复杂而充满挑战的任务&#xff0c;需要考虑多个技术、开发时间和功能方面的因素。以下是一个概要&#xff0c;描述了从技术、开发时间和功能角度如何开发这样的应用&#xff1a; 1. 技术要点…
阅读更多...
[note]李宏毅Deep Learning 之 BackPropagation笔记

[note]李宏毅Deep Learning 之 BackPropagation笔记

文章目录 Gradient DescentMath premiseBack Propagationforward passbackward pass Summary 中文名&#xff1a;反向传播算法 用于Gradient Descent 来train 一个neural network时用到 BackPropagation的核心是通过链式法则改变微分形式&#xff0c;并用forward pass 与 back…
阅读更多...
【论文笔记】Training language models to follow instructions with human feedback A部分

【论文笔记】Training language models to follow instructions with human feedback A部分

Training language models to follow instructions with human feedback A 部分 回顾一下第一代 GPT-1 &#xff1a; 设计思路是 “海量无标记文本进行无监督预训练少量有标签文本有监督微调” 范式&#xff1b;模型架构是基于 Transformer 的叠加解码器&#xff08;掩码自注意…
阅读更多...
【后端】rabbitmq常见使用问题

【后端】rabbitmq常见使用问题

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、rabbitmq常见问题二、rabbitmq常见报错三、总结 前言 例如&#xff1a;随着人工智能的不断发展&#xff0c;机器学习这门技术也越来越重要&#xff0c;很多…
阅读更多...
java+jsp+Oracle+Tomcat 记账管理系统论文（一）

java+jsp+Oracle+Tomcat 记账管理系统论文（一）

⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️ ➡️点击免费下载全套资料:源码、数据库、部署教程、论文、答辩ppt一条龙服务 ➡️有部署问题可私信联系 ⬆️⬆️⬆️​​​​​​​⬆️…
阅读更多...
docker-ubuntu-24.04安装openresty1.21.4.3全过程

docker-ubuntu-24.04安装openresty1.21.4.3全过程

拉取最新的ubuntu镜像 docker pull ubuntu:latest 创建启动容器 docker run -it --name 容器名称 -p 8082:8082 镜像id /bin/bash 更换apt-get为阿里云镜像 sed -i sarchive.ubuntu.com//mirrors.aliyun.com/g /etc/apt/sources.list && apt-get update 创建目录…
阅读更多...
最新文章

Copyright @ 2022~2023