C语言实现队列的示例详解
前言
前一段时间，我们试着用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;
}
以上就是C语言实现队列的示例详解的详细内容，更多关于C语言 队列的资料请关注其它相关文章！
相关文章