重生之我在异世界学编程之数据结构与算法：深入队列篇

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在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;
}

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！