网站建设在哪里推广,义乌的论坛网站建设,深圳企业名录,wordpress08影视源码目录 一.队列的定义
二.队列的分类
三.队列的功能
四.链式队列的声明
五.链式队列功能的实现
5.1 初始化队列
5.2 判断队列是否为空
5.3 获取队头元素
5.4 获取队尾元素
5.5获取队列长度
5.6 入队
5.7出队
5.8 打印队列元素
5.9 销毁队列 一.队列的定义
队列queue是一种只允许在一端进行插入操作而在另一端进行删除操作的线性表。其严格遵循先进先出First In First Out的规则简称FIFO。
队列与栈类似实现方式有两种。一种是以数组的方式实现另一种以单链表来实现。这两种实现方式各有优劣并且都有细节需要处理。
二.队列的分类
队列可以根据分为单向队列、双向队列特殊的队列、循环队列三种。
其中单向队列为本篇文章中要实现的队列
双向队列为可以从两端进行插入和删除的队列我也不知道为什么要弄一个这样的队列出来根定义不一样了都
循环队列是循环的队列。
三.队列的功能
队列主要需要实现如下功能 5.1 初始化队列 5.2 判断队列是否为空 5.3 获取队头元素 5.4 获取队尾元素 5.5获取队列长度 5.6 入队 5.7出队 5.8 打印队列元素 5.9 销毁队列 四.链式队列的声明
由于我们实现的队列是由链表实现的因此我们需要先声明一个结构体类型表示链表。
之后我们就可以声明队列了队列其中的成员分别是队列的头指针、队列的尾指针、队列的长度。
typedef int QDataType;
typedef struct QueueNode
{QDataType data;//队列数据struct QueueNode* next;//指向下一个队列块
}QNode;
typedef struct Queue
{QNode* front;//队列头QNode* rear;//队列尾int size;//队列长度
}Queue;
五.链式队列功能的实现
5.1 初始化队列
初始化队列就是给队列的每个成员赋初值。
由于front和rear是指针因此我们初始化为空。
由于size是整型因此我们初始化为0.
void QueueInit(Queue* q)
{q-front NULL;q-rear NULL;q-size 0;
}
5.2 判断队列是否为空
判断一个队列是否为0的方式有很多
可以通过判断size是否为0判断
也可以通过队列头和队列尾的指针来判断 。
这里我们通过size是否等于0来判断。
bool QueueEmpty(Queue* q)
{assert(q);return q-size;
}
5.3 获取队头元素
获取队列的头元素只要保证队列存在并且不为空即可。
队列的头元素就是队列头指针的data我们访问即可。
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q-front-data;
}
5.4 获取队尾元素 队列的尾部数据的获取和获取队头数据类似直接返回队尾指针即可。
、
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q-rear-data;
}
5.5获取队列长度 直接返回size即可。
//获取队列长度
int QueueSize(Queue* q)
{assert(q);return q-size;
}
5.6 入队
入队列首先我们应动态申请一个链表结点。
之后我们就可以自行初始化链表结点的值了。
再然后我们要分为两种情况了
第一种情况是链表没有结点这时我们的结点入队列对队头和队尾都会产生影响
第二种情况是链表中已有结点这时我们的结点入队列只会对队尾产生影响。
因此我们在这里需要通过分支结构处理这个问题。
由于这两种情况都需要处理size为了防止代码冗长我们将size的自增语句写在分支结构之外。
void QueuePush(Queue* q, QDataType x)
{assert(q);//初始化新结点QNode* newnode (QNode*)malloc(sizeof(QNode));newnode-data x;newnode-next NULL;//队列为空if (q-front q-rear NULL){//更新信息q-front q-rear newnode;//q-size;}else{//更新信息q-rear-next newnode;q-rear newnode;//q-size;}q-size;
}
5.7出队
在已经讲解了入队列之后我们再讲解一下出队列。
出队列首先要确保队列中已有队列结点否则将无队列结点可出。
出队列也分为两种情况
第一种情况是队列中只有一个结点我们需要释放掉这个结点并将队列的头指针和尾指针置空
第二种情况是队列中有好多个结点这时我们释放掉队列头的结点之后更新队头即可。
//出队
//1.考虑情况要全面
//2.在更新队列时要将数据结构中受到影响的成员全部更新
//3.如果分不清谁受到了影响就逐个排查。
void QueuePop(Queue* q)
{assert(q);assert(q-front);if (q-size 1){free(q-front);q-front q-rear NULL;}else{QNode* ret q-front-next;free(q-front);q-front ret;}q-size--;
} 在有多个结点的情况下我们在出队时需要注意的是需要定义一个指针保存队头的下一个结点否则在更新时则无从下手。
5.8 打印队列元素
与链表的打印方式一样打印即可。
void QueuePrint(Queue* q)
{assert(q);QNode* cur q-front;printf(队头-);while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(队尾);
}
5.9 销毁队列 与链表的销毁方法一样销毁即可。
void QueueDestroy(Queue* q)
{assert(q);QNode* ret q-front;while (ret){QNode* next ret-next;free(ret);ret next;}q-front q-rear NULL;
}
