数据结构中的链式队列
目录
一、链式队列的定义
二、链式队列的实现
三、链式队列的基本操作
- ①初始化
②判空
③入队
④出队
⑤获取长度
⑥打印
四、循环队列的应用
五、总结
六、全部代码
七、结果
在数据结构中，队列（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;
}
七、结果
