国外的建筑设计网站,全栈开发需要学什么课程,核心关键词是什么意思,织梦网站内容管理系统C语言数据结构——详细讲解《队列》 前言一、队列的概念二、队列的操作#xff08;一#xff09;定义队列结构#xff08;二#xff09;初始化队列#xff08;三#xff09;入队列操作#xff08;四#xff09;出队列操作#xff08;五#xff09;获取队头元素#… C语言数据结构——详细讲解《队列》 前言一、队列的概念二、队列的操作一定义队列结构二初始化队列三入队列操作四出队列操作五获取队头元素六检查队列是否为空七销毁队列 三本文所有代码1.Queue.h文件2.Queue.c文件 前言
在上一篇博客中我们详细探讨了栈这种数据结构今天让我们深入了解另一种与栈类似重要的数据结构 —— 队列。 一、队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。队列遵循先进先出的原则入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为队头。 大家思考一个问题队列的底层结构是数组还是链表
队列的底层结构既可以是数组也可以是链表 基于数组实现的队列优点 实现简单逻辑清晰可直接通过索引随机访问元素时间复杂度为 O (1)。 缺点 需预先确定队列大小。若队列元素超数组大小扩容操作复杂且耗时 基于链表实现的队列优点 可动态调整大小无需预先确定队列长度队头和队尾的插入、删除操作时间复杂度为 O (1) 缺点 每个节点需额外存储指针占用空间。 无法直接通过索引访问元素随机访问效率低 今天我们来详细讲解一下基于链表实现的队列 二、队列的操作
一定义队列结构
首先我们需要定义队列链表节点结构体
//定义队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;队列结点结构中的data成员用于存储队列中的实际数据接下来我们定义队列结构体本身
//定义队列的结构
typedef struct Queue
{QueueNode* phead; //队头QueueNode* ptail; //队尾
}Queue;接下来需要初始化队列
// 初始化队列
void initQueue(Queue *pq) {pq-phead NULL;pq-ptail NULL;
}二初始化队列
在使用队列之前我们需要对其进行初始化操作将队头和队尾指针都设置为 NULL表示队列为空。
// 初始化队列
void initQueue(Queue *pq)
{pq-phead NULL;pq-ptail NULL;
}三入队列操作
// 入队操作
void enqueue(Queue *pq, int x) {Node *newNode (Node *)malloc(sizeof(Node));newNode-data x;newNode-next NULL;if (pq-ptail NULL) {// 队列为空的情况pq-phead newNode;pq-ptail newNode;} else {pq-ptail-next newNode;pq-ptail newNode;}
}
先创建一个新节点给它分配内存空间把要入队的元素值赋给新节点的 data并把 next 设为 NULL。然后看队列是不是空的如果空新节点就既是队头又是队尾如果不空就把新节点接到队尾节点后面并更新队尾指针指向新节点
四出队列操作 //出队列
int dequeue(Queue* pq)
{assert(pq-phead ! NULL);Node* temp pq-phead;int x temp-data;if (pq-phead pq-ptail){pq-phead NULL;pq-ptail NULL;}else{pq-phead pq-phead-next;}free(temp);return x;
}从队列的队头取出一个元素并删掉对应的节点。先检查队列不能是空的然后把队头节点的数据存起来接着看队列是不是只有一个元素如果是就把队头和队尾指针都设为 NULL如果不止一个元素就更新队头指针指向下一个节点最后释放原来队头节点的内存并返回取出的元素值。
五获取队头元素 // 获取队头元素
int front(Queue* pq)
{assert(pq-phead ! NULL);return pq-phead-data;
}能获取队列的队头元素的值但不把这个元素从队列里取出来。先得确保队列不是空的然后直接返回队头节点的 data 值就行
六检查队列是否为空
int isEmpty(Queue *pq)
{return pq-front NULL;
}
如果是就说明队列为空返回相应结果这样在其他操作前可以先检查下队列状态避免在空队列上做无效操作
七销毁队列
// 释放队列内存
void freeQueue(Queue* pq)
{Node* current pq-phead;Node* next;while (current ! NULL){next current-next;free(current);current next;}pq-phead NULL;pq-ptail NULL;
}
在队列用完后用来释放它占用的内存资源。从队头开始逐个遍历队列里的节点释放每个节点的内存最后把队头和队尾指针都设为 NULL让队列回到初始的空状态
三本文所有代码
1.Queue.h文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h// 链表节点结构体
typedef struct Node {int data;struct Node* next;
} Node;// 队列结构体
typedef struct Queue {Node* phead;Node* ptail;
} Queue;// 初始化队列
void initQueue(Queue* pq) {pq-phead NULL;pq-ptail NULL;
}//入队列
void enqueue(Queue* pq, int x)
{Node* newnode (Node*)malloc(sizeof(Node));newnode-data x;newnode-next NULL;if (pq NULL){pq-phead newnode;pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}
}//出队列
int dequeue(Queue* pq)
{assert(pq-phead ! NULL);Node* temp pq-phead;int x temp-data;if (pq-phead pq-ptail){pq-phead NULL;pq-ptail NULL;}else{pq-phead pq-phead-next;}free(temp);return x;
}// 获取队头元素
int front(Queue* pq)
{assert(pq-phead ! NULL);return pq-phead-data;
}// 检查队列是否为空
int isEmpty(Queue* pq)
{return (pq-phead ! NULL) ? 0 : 1;
}// 释放队列内存
void freeQueue(Queue* pq)
{Node* current pq-phead;Node* next;while (current ! NULL){next current-next;free(current);current next;}pq-phead NULL;pq-ptail NULL;
}
2.Queue.c文件
#include Queue.h
#include stdio.hint main() {Queue myQueue;initQueue(myQueue);// 先输入一串数据来初始化队列int num;printf(请输入一串整数以空格分隔用于初始化队列输入非整数结束输入\n);// 逐个读取输入的数据并将其入队while (scanf_s(%d, num) 1) {enqueue(myQueue, num);}// 清除输入缓冲区中的剩余字符例如换行符等while (getchar() ! \n);int choice, value;do {printf(请选择操作\n);printf(1. 入队\n);printf(2. 出队\n);printf(3. 获取队头元素\n);printf(4. 检查队列是否为空\n);printf(5. 退出\n);scanf_s(%d, choice);switch (choice) {case 1:printf(请输入要入队的值);scanf_s(%d, value);enqueue(myQueue, value);break;case 2:if (!isEmpty(myQueue)) {printf(出队元素: %d\n, dequeue(myQueue));}else {printf(队列为空无法出队\n);}break;case 3:if (!isEmpty(myQueue)) {printf(当前队头元素: %d\n, front(myQueue));}else {printf(队列为空无队头元素\n);}break;case 4:if (isEmpty(myQueue)) {printf(队列为空\n);}else {printf(队列不为空\n);}break;case 5:printf(退出程序\n);break;default:printf(无效的选择请重新输入\n);}} while (choice ! 5);// 释放队列内存freeQueue(myQueue);return 0;
}
