数据结构（队列及其实现）

概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，

队列具有先进先出FIFO(First In First Out)原则。

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队列底层结构选型

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低。

---

队列的实现

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
int size;//保存队列有效数据个数
}Queue;

void QueueInit(Queue* pq);
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

此处代码与头文件中的代码一一对应。

初始化

void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

入队列（尾）

// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//申请新节点
QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;

//ptail newnode
if (pq->phead == NULL)
{//队列为空
pq->phead = pq->ptail = newnode;
}
else
{
//队列不为空
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;//newnode
}
pq->size++;
}

队列判空

//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
}

出队列（队头）

// 出队列，队头
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

//只有一个结点的情况，避免ptail变成野指针
if (pq->ptail == pq->phead)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//删除队头元素、
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;
}

取队头数据

//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->phead->data;
}

取队尾数据

//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->ptail->data;
}

队列有效元素个数

//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
/*int size = 0;
QueueNode* pcur = pq->phead;
while (pcur)
{
size++ ;
pcur = pcur->next;
}
return size;*/
return pq->size;
}

销毁队列

//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}

---

以上便是本期队列的全部内容，感谢大家的观看与支持，这是激励我前进的不竭动力！

原文地址：https://blog.csdn.net/2406_83947720/article/details/140594453

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！