C语言实现队列的示例详解

目录

前言

一. 什么是队列

二. 使用什么来实现栈

三. 队列的实现

3.1头文件

3.2 函数的实现

四.完整代码

前言

前一段时间,我们试着用C语言实现了数据结构中的顺序表,单链表,双向循环链表,栈。今天我们再用C语言来实现另一种特殊的线性结构:队列

一. 什么是队列

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

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

二. 使用什么来实现栈

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

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问可以直接访问任何元素必须从头节点开始往后寻找
任意位置插入或删除元素要搬移其他的元素,效率低。只需要修改节点的指针指向,效率高
插入动态顺序表,当空间不够时需要扩容无容量概念,需要就申请,不用就释放
应用场景元素高效存储,并且需要频繁访问需要在任意位置插入或者删除频繁

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

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

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

三. 队列的实现 3.1头文件

1.包含的标准库

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

2.定义结构体

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

3.函数声明

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 函数的实现

1.队列的初始化

将头尾置为空指针即可。

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

2.队列的销毁

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

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; }

3.入队

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

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

2.如果不为空队列,只用改变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; } }

4.出队

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

队列为空,改变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; } }

5. 取出队首元素

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

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

6.判断是否为空队列

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

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

7. 求队伍长度

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

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语言 队列的资料请关注易知道(ezd.cc)其它相关文章!

推荐阅读

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    区域语言设置|区域语言设置工具

    区域语言设置|区域语言设置工具,,区域语言设置工具你好,大致的方法如下,可以参考:1、按下键盘的windows 图标,再开始菜单中单击“设置”;出现的

    c4d语言设置|c4d汉语设置

    c4d语言设置|c4d汉语设置,,1. c4d汉语设置mac版的C4D是这样的,中文字体是有的,但是是以拼音的形式存在,比如黑体就是ht。中文字体以拼音方式

    电脑宣传语|电脑宣传语言

    电脑宣传语|电脑宣传语言,,1. 电脑宣传语言1.我做好了与你过一辈子的打算,也做好了你随时要走的准备,2.每段青春都会苍老,但我希望记忆里的你

    office语言设置|微软office语言设置

    office语言设置|微软office语言设置,,微软office语言设置一、首先点击桌面左下角“WIN键”。二、弹出选项内点击“所有程序”。三、接着点

    小米设置日语|小米设置日语语言

    小米设置日语|小米设置日语语言,,1. 小米设置日语语言MIUI系统文字目前只支持简体中文、繁体中文、英文、藏文和维吾尔文,不支持日文 2. 小

    易语言开发电脑系统|易语言电脑版

    易语言开发电脑系统|易语言电脑版,,1. 易语言电脑版首先编译——是将程序编译为exe文件,只能在有易语言的机子上运行,独立编译——是将程序