十、数据结构——链式队列

数据结构中的链式队列

目录

一、链式队列的定义
二、链式队列的实现
三、链式队列的基本操作

• ①初始化
  ②判空
  ③入队
  ④出队
  ⑤获取长度
  ⑥打印

四、循环队列的应用
五、总结
六、全部代码
七、结果

在数据结构中，队列（Queue）是一种常见的线性数据结构，遵循先进先出（First In First Out，FIFO）的原则。链式队列是队列的一种实现方式，它使用链表来存储队列中的元素。本篇博客将详细介绍链式队列的定义、实现和基本操作，并附带有带有注释的示例代码。

一、链式队列的定义

链式队列是通过链表实现的一种队列，它将队列的元素通过指针连接起来。链式队列不需要预先分配固定大小的存储空间，因此可以动态增长，更加灵活。

二、链式队列的实现

// 定义节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 定义链式队列
typedef struct {Node* front;Node* rear;
} LinkedQueue;

三、链式队列的基本操作

①初始化链式队列

// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {queue->front = NULL;queue->rear = NULL;
}

②判断队列是否为空

// 判断队列是否为空
int isEmpty(LinkedQueue* queue) {return queue->front == NULL;
}

③入队操作

// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {// 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(queue)) {// 队列为空，新节点成为队头queue->front = newNode;queue->rear = newNode;} else {// 将新节点插入到队尾queue->rear->next = newNode;queue->rear = newNode;}
}

④ 出队操作

// 出队操作
int dequeue(LinkedQueue* queue) {int value = -1;if (!isEmpty(queue)) {// 保存队头节点的值value = queue->front->data;// 删除队头节点Node* temp = queue->front;queue->front = queue->front->next;free(temp);// 队列为空时，更新rear指针if (queue->front == NULL) {queue->rear = NULL;}}return value;
}

⑤获取队列中元素的个数

// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {Node* current = queue->front;int length = 0;while (current != NULL) {length++;current = current->next;}return length;
}

⑥打印队列内元素

// 打印队列内的元素
void printQueue(LinkedQueue* queue) {Node* current = queue->front;printf("Queue: ");while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}

四、链式队列的应用

链式队列适用于在不确定队列大小的情况下，动态地存储数据。它可以用于解决生产者-消费者问题，以及在需要异步处理数据的情况下。

五、总结

①入队操作：

• 当队列为空时，新节点既是队头也是队尾。
• 当队列不为空时，将新节点插入到队尾，并更新rear指针为新节点。
• 入队操作涉及动态内存分配，要注意释放节点内存以避免内存泄漏。

②出队操作：

• 在出队操作之前，要先检查队列是否为空，避免出现空队列的错误。
• 出队操作要删除队头节点，并更新front指针为下一个节点。
• 如果队列为空，同时要更新rear指针为空。

③判断队列是否为空：

• 需要根据front指针是否为空来判断队列是否为空。

④获取队列长度：

• 需要遍历队列中的节点，并计算节点个数来获取队列长度。

⑤动态内存管理：

• 在链式队列中，需要使用malloc函数为节点分配内存空间。
• 在节点不再需要时，要使用free函数释放节点的内存空间，以避免内存泄漏。

⑥打印队列元素：

• 可以通过遍历队列的节点，并输出节点的数据来打印队列中的元素。

⑦队列的初始化：

• 在使用链式队列之前，要先对其进行初始化，将front和rear指针都设置为空。

⑧注意空队列和满队列：

• 链式队列一般不会出现满队列的情况，但要注意空队列的处理，以避免出现空指针引用错误。

⑨链表的插入和删除：

• 在链式队列中，入队操作涉及链表的插入，而出队操作涉及链表的删除。要确保插入和删除的指针操作正确，避免出现内存泄漏或者空指针错误。

⑩异常处理：

• 在队列操作时，要考虑异常情况，如空队列出队、空指针操作等，要对这些情况进行适当的处理，避免程序崩溃或出现不可预料的错误。

六、全部代码

①listqueue.h

#ifndef _LISTQUEUE_H_
#define _LISTQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
typedef int TypeData;
typedef struct Node {TypeData data;struct Node* next;
} Node;typedef struct {Node* front;Node* rear;
} LinkedQueue;// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue);// 判断队列是否为空
int isEmpty(LinkedQueue* queue);// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) ;// 出队操作
int dequeue(LinkedQueue* queue);// 获取队列的长度
int getQueueLength(LinkedQueue* queue)// 打印队列内的元素
void printQueue(LinkedQueue* queue);#endif

②listqueue.c

#include "listqueue.h"
// 初始化链式队列
void initLinkedQueue(LinkedQueue* queue) {queue->front = NULL;queue->rear = NULL;
}// 判断队列是否为空
int isEmpty(LinkedQueue* queue) {return queue->front == NULL;
}// 入队操作
void enqueue(LinkedQueue* queue, TypeData value) {// 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(queue)) {// 队列为空，新节点成为队头queue->front = newNode;queue->rear = newNode;} else {// 将新节点插入到队尾queue->rear->next = newNode;queue->rear = newNode;}
}// 出队操作
int dequeue(LinkedQueue* queue) {int value = -1;if (!isEmpty(queue)) {// 保存队头节点的值value = queue->front->data;// 删除队头节点Node* temp = queue->front;queue->front = queue->front->next;free(temp);// 队列为空时，更新rear指针if (queue->front == NULL) {queue->rear = NULL;}}return value;
}// 获取队列的长度
int getQueueLength(LinkedQueue* queue) {Node* current = queue->front;int length = 0;while (current != NULL) {length++;current = current->next;}return length;
}// 打印队列内的元素
void printQueue(LinkedQueue* queue) {Node* current = queue->front;printf("Queue: ");while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}

③listqueue_main.c

#include "listqueue.h"
#include "listqueue.c"
int main() {LinkedQueue queue;initLinkedQueue(&queue);// 入队操作enqueue(&queue, 10);enqueue(&queue, 20);enqueue(&queue, 30);// 打印队列内的元素printQueue(&queue);// 获取队列长度int length = getQueueLength(&queue);printf("Queue length: %d\n", length);// 出队操作int value = dequeue(&queue);printf("Dequeued value: %d\n", value);// 打印出队后的队列printQueue(&queue);// 获取出队后的队列长度length = getQueueLength(&queue);printf("Queue length: %d\n", length);return 0;
}

七、结果