重生之我在异世界学编程之数据结构与算法：深入队列篇
大家好，这里是小编的博客频道
小编的博客：就爱学编程
很高兴在
CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！
目录
那接下来就让我们开始遨游在知识的海洋！
一、概述
链表队列是一种基于链表的先进先出
（FIFO）数据结构。与数组实现的队列不同，链表队列可以动态地分配和释放内存，因此更适合处理元素数量不确定或需要频繁插入和删除操作的场景。
二、链表节点结构
在链表队列中，每个节点通常包含两个部分：
数据域和指针域。数据域用于存储节点的值，而指针域则用于指向下一个节点。
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域
} Node;
三、队列结构
链表队列通常由两个指针组成：
front和rear。front指针指向队列的头节点（即第一个元素），而rear指针指向队列的尾节点（即最后一个元素）。当队列为空时， front 和 rear 都为 NULL。
typedef struct Queue {
Node* front; // 头指针
Node* rear; // 尾指针
} Queue;
四、基本操作
1.初始化队列
创建一个空的链表队列，将
front和rear指针都设置为NULL。
void initializeQueue(Queue* q) {
q->front = q->rear = NULL;
}
2.判断队列是否为空
检查 front 指针是否为 NULL。如果是，则队列为空；否则，队列不为空。
int isEmpty(Queue* q) {
return q->front == NULL;
}
3.入队操作
在队列的尾部添加一个新节点。首先创建一个新节点，并将其数据域设置为要插入的值。然后更新
rear指针的next域为新节点，并将rear指针移动到新节点上。如果队列为空（即front为NULL），则将 front 指针也设置为新节点。
void enqueue(Queue* q, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
}
4.出队操作
从队列的头部移除一个节点。首先检查队列是否为空。如果不为空，则保存头节点的值，并更新
front指针为头节点的下一个节点。如果移除的是最后一个节点（即rear与front相同），则将rear也设置为NULL。最后释放原头节点的内存空间。
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty!
");
exit(EXIT_FAILURE); // 或者返回一个特殊值表示错误
}
Node* temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return value;
}
5. 获取队列头元素
获取队列头部的元素值而不移除它。首先检查队列是否为空。如果不为空，则返回头节点的数据域值。
int peek(Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty!
");
exit(EXIT_FAILURE); // 或者返回一个特殊值表示错误
}
return q->front->data;
}
五、源码
Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int TreeDatatype;
typedef struct QuequeNode {
TreeDatatype* data;
struct QuequeNode* next;
}QNode;
typedef struct Queue{
QNode* head;//单链表的头指针作为队头
QNode* tail;//单链表的尾指针作为队尾
int size;//存储队列元素数量
}Que;
//初始化队列
void QInit(Que* ps);
//销毁队列
void QDestroy(Que* ps);
//插入数据（从队尾）------入队
void QPush(Que* ps, QDatatype x);
//删除数据（从对头）------出队
void QPop(Que* ps);
//判空
bool QEmpty(Que* ps);
//得出队内元素数量
int QSize(Que* ps);
//得到队头元素的数据
QDatatype QFront(Que* ps);
//得到队尾元素的数据
QDatatype QBack(Que* ps);
Queue.c
#include"Queue.h"
//初始化队列
void QInit(Que* ps) {
assert(ps);
ps->head = ps->tail = NULL;
ps->size = 0;
}
//销毁队列
void QDestroy(Que* ps) {
assert(ps);
QNode* cur = ps->head;
while (cur) {
QNode* next = cur->next;
free(cur);
cur = next;
}
ps->size = 0;
ps->head = ps->tail = NULL;
}
//插入数据（从队尾）------入队
void QPush(Que* ps, QDatatype* x) {
assert(ps);
QNode* cur = (QNode*)malloc(sizeof(QNode));
if (cur == NULL) {
perror("malloc fail");
return;
}
if (ps->head == NULL) {
assert(ps->tail == NULL);
ps->head = ps->tail = cur;
}
else {
ps->tail->next = cur;//先赋值
ps->tail = cur;//再更新尾指针
}
cur->next = NULL;
cur->data = x;
ps->size++;
}
//删除数据（从对头）------出队
void QPop(Que* ps) {
assert(ps);
assert(!QEmpty(&q);
if (ps->head->next == NULL) {
free(ps->head);
ps->head = ps->tail = NULL;
ps->size = 0;
return;
}
QNode* next = ps->head->next;
free(ps->head);
ps->head = next;
ps->size--;
}
//判空
bool QEmpty(Que* ps) {
assert(ps);
return (ps->size == 0);
}
//得出队内元素数量
int QSize(Que* ps) {
assert(ps);
return (ps->size);
}
//得到队头元素的数据
QDatatype QFront(Que* ps) {
assert(ps && !QEmpty(ps));
return (ps->head->data);
}
//得到队尾元素的数据
QDatatype QBack(Que* ps) {
assert(ps && !QEmpty(ps));
return (ps->tail->data);
}
Test.c
#include"Queue.h"
void test1() {
Que q;
QInit(&q);
QPush(&q, 1);
QPush(&q, 2);
QPush(&q, 3);
QPush(&q, 4);
QPush(&q, 5);
while (!QEmpty(&q)) {
printf("%d ", QFront(&q));
QPop(&q);
}
printf("\n");
QDestroy(&q);
}
int main(){
test1();
return 0;
}
快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！
原文地址：https://blog.csdn.net/z15879084549/article/details/144823303
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！