欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 焦点 > 98.【C语言】数据结构之队列

98.【C语言】数据结构之队列

2024/12/22 9:22:36 来源:https://blog.csdn.net/2401_85828611/article/details/143758115  浏览:    关键词:98.【C语言】数据结构之队列

目录

1.定义

2.队头和队尾

3.示意图

4.实现队列

两种解决方法

1.使用双向带头循环链表

2.为单向链表再定义一个尾指针tail

操作队列的函数 

初始化函数QueueInit

插入函数QueuePush

删除函数QueuePop

写法1

注意

写法2

计算队列大小函数QueueSize

销毁函数QueueDestroy 


1.定义

只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表

2.队头和队尾

:进行删除(即出队Dequeue)操作的一端

:进行插入(即入队Enqueue)操作的一端

注意到:由于队列的特性,删除只在队头,插入只在队尾(这里和链表不一样:链表支持头删、尾删、头插和尾插)

特点:FIFO(First In First Out)先进先出

3.示意图

6376208b5e584062a1e2d56559f33fea.png

这里比较像链表的尾插

4.实现队列

main函数的第一行代码

QNode* head = NULL;

如果频繁尾插,会导致找尾麻烦,因此不建议这样写,

两种解决方法

1.使用双向带头循环链表

有关双向带头循环链表的内容参见

94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

95.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

2.为单向链表再定义一个尾指针tail

Queue.h写入

typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

除了有头指针和尾指针之外,还要用变量size来存储队列的大小

再用一个结构体去定义队列中的每一个节点

typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;

这里和以往的链表的定义不一样,用两个结构体来定义 ,将头指针,尾指针和size打包成结构体是为了方便操作

画图则为:

操作队列的函数 

初始化函数QueueInit

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

一开始队列一个元素都没有插入,因此head和tail全部置NULL,队列大小size为0

插入函数QueuePush

每插入一个节点需要做两件事:

1.开辟节点并写入节点(节点指针和节点值)

做法:malloc开辟空间,检查空间是否成功开辟,再用newnode接收新开辟空间的起始地址,

2.修改结构体Queue的成员变量

注意:如果一开始队列中一个节点都没有,不能直接尾插,否则导致pq->tail->next = newnode;和pq->tail = newnode;变为NULL->next = newnode;和NULL = newnode;不合法

如果为NULL,做的操作应该是头指针和尾指针都应该指向newnode,size++而不是去尾插

队列中有节点,直接为插,size++

void QueuePush(Queue* pq, QDataType x)
{
//开辟节点并写入节点(节点指针和节点值)QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;//---------------------------------------------------//修改结构体Queue的成员变量if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

删除函数QueuePop

队列的性质只支持

写法1
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL)pq->tail = NULL;pq->size--;
}
注意

1.队列不能头删,因此断言assert(pq->head != NULL);

2.头删要先保存头节点的下一个节点的地址,之后free(头结点的地址)

3.如果头删后没有节点,则投头指针和尾指针都要赋值为NULL

写法2
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}

计算队列大小函数QueueSize

由于提前创建好了结构体Queue,则直接返回size即可

void QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

销毁函数QueueDestroy 

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

1.由于malloc是以节点为单位开辟空间的,则内存释放时也要以节点为单位释放,因此内存释放要先保存头节点的下一个节点的地址,之后free(头结点的地址)

2.恢复头指针,尾指针和size的初始值

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com