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