C语言 队列
。菀枯。 人气:0前言
前一段时间,我们试着用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; typedef struct 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; typedef struct 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; }
加载全部内容