C语言如何实现队列

这篇文章主要介绍了C语言如何实现队列的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言如何实现队列文章都会有所收获，下面我们一起来看看吧。

一. 什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

这个队列就可以理解成我们平时的排队，先进入的先出去，与我们之前实现的先进后出的栈相反。

二. 使用什么来实现栈

再把上次的图拿出来，我们看看是用线性表来实现队列，还是链表比较好

综合上表来看，我觉得链表较为方便，原因如下：

队列有多少元素不确定，链表可以做到需要就申请，不用就释放，较为方便

队列是先进先出，顺序固定，不需要随机访问。

三. 队列的实现

3.1头文件

包含的标准库

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

定义结构体

typedef int QDateType;//队列存储数据类型typedef struct QueueNode //队列元素节点{QDateType val;struct QueueNode* next;}QueueNode;typedefstruct Queue //队列{QueueNode* head;QueueNode* tail;}Queue;

函数声明

void QueueInti(Queue* pq);// 队列初始化void QueueDestory(Queue* pq);// 队列的销毁void QueuePush(Queue* pq, QDateType x);// 入队void QueuePop(Queue* pq);// 出队QDateType QueueFront(Queue* pq);// 取出队首元素int QueueSize(Queue* pq);// 求队列的长度bool QueueEmpty(Queue* pq);// 判断队是否为空

3.2 函数的实现

队列的初始化

将头尾置为空指针即可。

void QueueInti(Queue* pq){    assert(pq); //防止pq为空指针    pq->head = pq->tail = NULL;}

队列的销毁

遍历队列元素，然后将每一个元素释放。

void QueueDestory(Queue* pq){    assert(pq); //防止pq为空指针    QueueNode* cur = pq->head;    while (cur)    {        QueueNode* next = cur->next;        free(cur);        cur = next;    }    pq->tail = pq->head = NULL;}

入队

对于入队，我们首先需要去开辟一个新的节点来存储数据，然后将这个节点加入到tail后即可。此时我们就要分别考虑。

如果为空队列，那么我们不仅要改变tail，还要改变head的值

如果不为空队列，只用改变tail即可。

void QueuePush(Queue* pq, QDateType x){assert(pq); //防止pq为空指针QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newNode){printf("malloc error\n");exit(-1);}newNode->val = x;newNode->next = NULL;//开辟一个新节点存储数据if (pq->tail == NULL)//判断是否为空队列{assert(pq->head == NULL);pq->head = pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}}

出队

对于出队，我们同样需要考虑两种情况

• 队列为空，改变head的同时改变tail

• 队列不为空，改变head即可。

void QueuePop(Queue* pq){    assert(pq);//防止pq为空指针    assert(pq->head && pq->tail); //防止队列为空队列    if (pq->head->next == NULL)    {        free(pq->head);        pq->head = pq->tail = NULL;    }    else    {        QueueNode* next = pq->head->next;        free(pq->head);        pq->head = next;    }}

取出队首元素

没啥说的，直接访问头节点取出即可

QDateType QueueFront(Queue* pq){    assert(pq);//防止pq为空指针    assert(pq->head && pq->tail); //防止队列为空队列    return pq->head->val;}

判断是否为空队列

我们只需要判断头指针是否为NULL，如果是则为空

bool QueueEmpty(Queue* pq){    assert(pq);    return pq->head == NULL;}

求队伍长度

创建一个变量，遍历队伍求长度。

int QueueSize(Queue* pq){    assert(pq);    QueueNode* cur = pq->head;    int count = 0;    while (cur)    {        cur = cur->next;        count++;    }    return count;}

四.完整代码

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <assert.h>typedef int QDateType;typedef struct QueueNode{QDateType val;struct QueueNode* next;}QueueNode;typedefstruct Queue{QueueNode* head;QueueNode* tail;}Queue;void QueueInti(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->tail = pq->head = NULL;}void QueuePush(Queue* pq, QDateType x){assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newNode){printf("malloc error\n");exit(-1);}newNode->val = x;newNode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}QDateType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->val;}int QueueSize(Queue* pq){assert(pq);QueueNode* cur = pq->head;int count = 0;while (cur){cur = cur->next;count++;}return count;}

关于“C语言如何实现队列”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C语言如何实现队列”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注编程网行业资讯频道。