数据结构中的链式队列
目录
一、链式队列的定义
二、链式队列的实现
三、链式队列的基本操作
-
①初始化
②判空
③入队
④出队
⑤获取长度
⑥打印
四、循环队列的应用
五、总结
六、全部代码
七、结果
在数据结构中,队列(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文章来源:https://www.toymoban.com/news/detail-733954.html
#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;
}
七、结果
文章来源地址https://www.toymoban.com/news/detail-733954.html
到了这里,关于十、数据结构——链式队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!