链式队列深潜：掌握数据流动的秘密
引言
队列是一种广泛应用于计算机科学的数据结构，具有先进先出（FIFO）的特性。这一特性使得队列在多个实际应用中发挥了关键作用，如任务调度、缓冲区管理、消息传递等。本文将深入探讨队列的基本概念，并通过链表实现一个简单而高效的队列结构。
一、基本概念
1.1 定义
队列是一种线性数据结构，其主要特点是遵循先进先出（FIFO，First In First Out）原则。具体而言，最先被插入的元素会最先被移除。队列模拟了现实生活中的排队现象：新到的人在队尾加入，而在队首的人则逐个离开。
在下面的示意图中，队列头部称为“队首”，尾部称为“队尾”。将元素添加到队尾的操作称为“入队”，而删除队首元素的操作则称为“出队”。
队列示意图
1.2 基本操作
969bd4e7009949c28a541dc7e974f9b5.gif
队列的主要操作包括：
- 入队（Push）：将一个元素添加到队列的尾部。
- 出队（Pop）：从队列的头部移除并返回一个元素。
- 取队首元素（Front）：返回队首的元素，但不删除它。
- 取队尾元素（Back）：返回队尾的元素，但不删除它。
- 队列判空（isEmpty）：判断队列中是否有元素。
- 获取队列长度（Size）：获取队列中有效元素的个数。
1.3 队列的特点
队列具有以下几个显著特点：
- 先进先出（FIFO）：最先进入的元素最先被移除。
- 操作限制：只能在队列的头部出队，而在尾部入队。
- 队首元素：队首是当前可以访问和移除的元素。
- 空队列：队列为空时无法进行出队操作。
- 动态大小：队列可以根据需要扩展或收缩，适应不同的存储需求。
三、链式队列的实现
2ee3104913264cee96fc3905bb1a931b.png
1. 链表节点的定义
在实现链式队列之前，首先定义一个链表节点结构：
typedef int DataType;
//定义节点结构体
typedef struct Node
{
DataType data;//数据域
struct Node* next;//指针域
}Node;2. 队列结构的定义
接下来，定义队列结构，包括队头、队尾指针以及队列长度：
//定义队列结构体
typedef struct Queue
{
Node* phead;//队头
Node* ptail;//队尾
int size;//队列长度
}QU;3. 基本操作
接下来，我们将实现一些基本操作，以便更好地管理队列。
(1) 初始化队列
// 初始化队列
void QueueInit(QU* p)
{
assert(p);
p->phead = p->ptail = NULL; // 头尾指针初始化为 NULL
p->size = 0; // 队列大小初始化为 0
}(2) 入队
入队操作将新元素添加到队列的尾部。我们需要检查队列是否为空，以决定如何添加新节点。
ae0d63fd2cfd4242b89160852ba0966d.png
// 创建新节点
Node* CreateNode(DataType x)
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL) {
perror("malloc fail");
exit(1); // 分配失败，退出程序
}
newnode->data = x; // 设置节点数据
newnode->next = NULL; // 初始化后继指针为 NULL
return newnode; // 返回新节点
}
// 入队操作（从队尾插入）
void QueuePush(QU* p, DataType x)
{
assert(p);
Node* newnode = CreateNode(x);
if (p->phead == NULL) // 队列为空时
{
p->phead = p->ptail = newnode; // 头尾指针都指向新节点
}
else // 队列不为空时
{
p->ptail->next = newnode; // 尾节点的 next 指向新节点
p->ptail = newnode; // 更新尾指针为新节点
}
++p->size; // 队列大小加 1
}(3) 队列判空
// 判断队列是否为空
bool QueueEmpty(QU* p)
{
assert(p);
return p->phead == NULL; // 头指针为 NULL 表示队列为空
}(4) 出队
出队操作从队首移除元素，我们需要处理两种情况：队列为空或只有一个元素的情况。
0615740d529a4d07935513913a9bb66d.png
// 出队操作（从队头删除）
void QueuePop(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
if (p->phead == p->ptail) // 只有一个元素时
{
free(p->phead); // 释放头节点
p->phead = p->ptail = NULL; // 更新头尾指针为 NULL
}
else
{
Node* del = p->phead; // 保存要删除的节点
p->phead = p->phead->next; // 更新头指针为下一个节点
free(del); // 释放删除的节点
}
--p->size; // 队列大小减 1
}(5) 取队首元素
// 获取队头数据
DataType QueueFront(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
return p->phead->data; // 返回头节点的数据
}(6) 取队尾元素
// 获取队尾数据
DataType QueueBack(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
return p->ptail->data; // 返回尾节点的数据
}(7) 获取队列长度
// 获取队列长度
int QueueSize(QU* p)
{
assert(p);
return p->size; // 返回队列的大小
}(8) 销毁队列
最后，我们提供一个销毁队列的操作，以释放分配的内存，防止内存泄漏。
// 销毁队列
void QueueDestroy(QU* p)
{
assert(p);
Node* pcur = p->phead;
while (pcur) // 遍历所有节点并释放内存
{
Node* next = pcur->next;
free(pcur);
pcur = next;
}
p->phead = p->ptail = NULL; // 头尾指针置为 NULL
p->size = 0; // 队列大小置为 0
}四、完整代码
Queue.h
该部分主要包括函数的声明、以及头文件的引用
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int DataType;
//定义节点结构体
typedef struct Node
{
DataType data;//数据域
struct Node* next;//指针域
}Node;
//定义队列结构体
typedef struct Queue
{
Node* phead;//队头
Node* ptail;//队尾
int size;//队列长度
}QU;
//初始化队列
void QueueInit(QU* p);
//入队列，队尾
void QueuePush(QU* p, DataType x);
//队列判空
bool QueueEmpty(QU* p);
//出队列，队头
void QueuePop(QU* p);
//取队头数据
DataType QueueFront(QU* p);
//取队尾数据
DataType QueueBack(QU* p);
//队列长度
int QueueSize(QU* p);
//销毁队列
void QueueDestroy(QU* p);Queue.c
该部分主要包括函数的定义
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
// 初始化队列
void QueueInit(QU* p)
{
assert(p);
p->phead = p->ptail = NULL; // 头尾指针初始化为 NULL
p->size = 0; // 队列大小初始化为 0
}
// 创建新节点
Node* CreateNode(DataType x)
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL) {
perror("malloc fail");
exit(1); // 分配失败，退出程序
}
newnode->data = x; // 设置节点数据
newnode->next = NULL; // 初始化后继指针为 NULL
return newnode; // 返回新节点
}
// 入队操作（从队尾插入）
void QueuePush(QU* p, DataType x)
{
assert(p);
Node* newnode = CreateNode(x);
if (p->phead == NULL) // 队列为空时
{
p->phead = p->ptail = newnode; // 头尾指针都指向新节点
}
else // 队列不为空时
{
p->ptail->next = newnode; // 尾节点的 next 指向新节点
p->ptail = newnode; // 更新尾指针为新节点
}
++p->size; // 队列大小加 1
}
// 判断队列是否为空
bool QueueEmpty(QU* p)
{
assert(p);
return p->phead == NULL; // 头指针为 NULL 表示队列为空
}
// 出队操作（从队头删除）
void QueuePop(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
if (p->phead == p->ptail) // 只有一个元素时
{
free(p->phead); // 释放头节点
p->phead = p->ptail = NULL; // 更新头尾指针为 NULL
}
else
{
Node* del = p->phead; // 保存要删除的节点
p->phead = p->phead->next; // 更新头指针为下一个节点
free(del); // 释放删除的节点
}
--p->size; // 队列大小减 1
}
// 获取队头数据
DataType QueueFront(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
return p->phead->data; // 返回头节点的数据
}
// 获取队尾数据
DataType QueueBack(QU* p)
{
assert(p);
assert(!QueueEmpty(p)); // 确保队列不为空
return p->ptail->data; // 返回尾节点的数据
}
// 获取队列长度
int QueueSize(QU* p)
{
assert(p);
return p->size; // 返回队列的大小
}
// 销毁队列
void QueueDestroy(QU* p)
{
assert(p);
Node* pcur = p->phead;
while (pcur) // 遍历所有节点并释放内存
{
Node* next = pcur->next;
free(pcur);
pcur = next;
}
p->phead = p->ptail = NULL; // 头尾指针置为 NULL
p->size = 0; // 队列大小置为 0
}main.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void test()
{
QU qu;
QueueInit(&qu);
QueuePush(&qu, 1);
QueuePush(&qu, 2);
QueuePush(&qu, 3);
QueuePush(&qu, 4);
QueuePop(&qu);
printf("head:%d\n", QueueFront(&qu));
printf("back:%d\n", QueueBack(&qu));
printf("size:%d\n", QueueSize(&qu));
}
int main()
{
test();
return 0;
}五、总结
在本次博客中，我们实现了一个基本的队列数据结构，涵盖了以下几个关键功能：
- 初始化队列：创建一个空队列，准备进行后续操作。
- 入队：实现了在队尾添加新元素的功能，确保队列能够动态扩展。
- 队列判空：提供了检查队列是否为空的方法，便于在操作前判断队列状态。
- 出队：实现了从队首移除元素的功能，遵循先进先出的原则。
- 取队首元素：能够访问当前队首元素，但不移除它，方便查看下一个处理的元素。
- 取队尾元素：允许访问队尾元素，虽然不常见，但在某些场景中有其用途。
- 获取队列长度：实现了获取当前队列中元素数量的功能，便于管理和监控队列状态。
- 销毁队列：提供了清理队列资源的方法，防止内存泄漏。
通过实现这些基本操作，我们展示了队列的基本特性和使用方法，为理解队列在实际应用中的重要性奠定了基础。队列作为一种重要的数据结构，在任务调度、资源管理等多个领域都有广泛应用。希望这篇博客能帮助你更好地理解和使用队列。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
