引言
队列是一种广泛应用于计算机科学的数据结构，具有先进先出（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; }
五、总结
- 初始化队列：创建一个空队列，准备进行后续操作。
- 入队：实现了在队尾添加新元素的功能，确保队列能够动态扩展。
- 队列判空：提供了检查队列是否为空的方法，便于在操作前判断队列状态。
- 出队：实现了从队首移除元素的功能，遵循先进先出的原则。
- 取队首元素：能够访问当前队首元素，但不移除它，方便查看下一个处理的元素。
- 取队尾元素：允许访问队尾元素，虽然不常见，但在某些场景中有其用途。
- 获取队列长度：实现了获取当前队列中元素数量的功能，便于管理和监控队列状态。
- 销毁队列：提供了清理队列资源的方法，防止内存泄漏。
通过实现这些基本操作，我们展示了队列的基本特性和使用方法，为理解队列在实际应用中的重要性奠定了基础。队列作为一种重要的数据结构，在任务调度、资源管理等多个领域都有广泛应用。希望这篇博客能帮助你更好地理解和使用队列。
