链式队列深潜：掌握数据流动的秘密

队列是一种广泛应用于计算机科学的数据结构，具有先进先出（FIFO）的特性。在许多实际应用中，例如任务调度、缓冲区管理等，队列扮演着重要角色。本文将详细介绍队列的基本概念，并通过链表实现一个简单的队列。

平凡程序猿~

1166人浏览 · 2024-09-25 18:39:17

平凡程序猿~ · 2024-09-25 18:39:17 发布

引言

队列是一种广泛应用于计算机科学的数据结构，具有先进先出（FIFO）的特性。这一特性使得队列在多个实际应用中发挥了关键作用，如任务调度、缓冲区管理、消息传递等。本文将深入探讨队列的基本概念，并通过链表实现一个简单而高效的队列结构。

一、基本概念

1.1 定义

队列是一种线性数据结构，其主要特点是遵循先进先出（FIFO，First In First Out）原则。具体而言，最先被插入的元素会最先被移除。队列模拟了现实生活中的排队现象：新到的人在队尾加入，而在队首的人则逐个离开。

在下面的示意图中，队列头部称为“队首”，尾部称为“队尾”。将元素添加到队尾的操作称为“入队”，而删除队首元素的操作则称为“出队”。

队列示意图

1.2 基本操作

队列的主要操作包括：

入队（Push）：将一个元素添加到队列的尾部。
出队（Pop）：从队列的头部移除并返回一个元素。
取队首元素（Front）：返回队首的元素，但不删除它。
取队尾元素（Back）：返回队尾的元素，但不删除它。
队列判空（isEmpty）：判断队列中是否有元素。
获取队列长度（Size）：获取队列中有效元素的个数。

1.3 队列的特点

队列具有以下几个显著特点：

先进先出（FIFO）：最先进入的元素最先被移除。
操作限制：只能在队列的头部出队，而在尾部入队。
队首元素：队首是当前可以访问和移除的元素。
空队列：队列为空时无法进行出队操作。
动态大小：队列可以根据需要扩展或收缩，适应不同的存储需求。

三、链式队列的实现

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) 入队

入队操作将新元素添加到队列的尾部。我们需要检查队列是否为空，以决定如何添加新节点。

// 创建新节点
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) 出队

出队操作从队首移除元素，我们需要处理两种情况：队列为空或只有一个元素的情况。

// 出队操作（从队头删除）
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;
}