队列的深度解析：链式队列的实现

平凡之路.

发布于 2024-10-09 15:09:00

1250

发布于 2024-10-09 15:09:00

文章被收录于专栏：学习

引言

队列是一种广泛应用于计算机科学的数据结构，具有先进先出（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;
	p->size = 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;
//	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;
		p->ptail = newnode;
	}
	++p->size;
}

(3).队列判空

//队列判空 
bool QueueEmpty(QU* p)
{
	assert(p);
	return p->phead == NULL;
}

(4).出队

//出队列，队头 
void QueuePop(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列为空不能出队
	if (p->phead == p->ptail)//只有一个元素时
	{
		free(p->phead);
		p->phead = p->ptail = NULL;
	}
	else
	{
		Node* del = p->phead;
		p->phead = p->phead->next;
		free(del);
	}
	--p->size;
}

(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);
	assert(!QueueEmpty(p));//队列不能为空
	Node* pcur = p->phead;
	while (pcur)
	{
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL;
	p->size = 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;
	p->size = 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;
	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;
		p->ptail = newnode;
	}
	++p->size;
}
//队列判空 
bool QueueEmpty(QU* p)
{
	assert(p);
	return p->phead == NULL;
}
//出队列，队头 
void QueuePop(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p));//队列为空不能出队
	if (p->phead == p->ptail)//只有一个元素时
	{
		free(p->phead);
		p->phead = p->ptail = NULL;
	}
	else
	{
		Node* del = p->phead;
		p->phead = p->phead->next;
		free(del);
	}
	--p->size;
}
//取队头数据 
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);
	assert(!QueueEmpty(p));//队列不能为空
	Node* pcur = p->phead;
	while (pcur)
	{
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL;
	p->size = 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;
}