网站的域名做邮箱,网络营销和传统营销的区别和联系,高端企业展厅设计公司,商标设计生成器本章介绍数据结构队列的内容#xff0c;我们会从队列的定义以及使用和OJ题来了解队列#xff0c;话不多说#xff0c;我们来实现吧
队列
1。队列的概念及结构 队列#xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;… 本章介绍数据结构队列的内容我们会从队列的定义以及使用和OJ题来了解队列话不多说我们来实现吧
队列
1。队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。 我们来看一下下面的这张图让我们更好的理解它 我们从队尾入队头出只能是这样入栈和出栈
2。队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数 组头上出数据效率会比较低。
那队列的实现我们是用链式结构来实现的因为用数组下标的话出栈的时候要往前挪动数据会更麻烦这样队列的意义就下降了所以我们这里用的方法是链式结构。
typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;
这里我们定义的结构体Queue有很大的作用因为队列不是像单链表那样队列是有它的特点的其中最大的一个特点就是入栈只能从尾入出栈就是头出所以我们在这里定义head和tail有很大的作用定义在结构体当中会方便不少那我们现在继续往下看我们的接口函数吧。 给大家看一下下面实现队列的接口函数然后我们一步一步的来实现他们 // 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);队列的初始化 void QueueInit(Queue* q); 初始化我们初始的是结构体Queue中的内容
void QueueInit(Queue* q)
{assert(q);q-head q-tail NULL;
}首先要判断传过来的指针是否是为空然后将头指针和尾指针都置为NULL。
销毁队列
void QueuePush(Queue* q, QueueDataType data)
首先我们要创造一个节点将它放入创造节点的结构体就是QueueNode然后我们要更新后面节点中的head和tail这里大家肯定有疑问我们竟然是更新指针那我们应该传指针的地址才能起到作用一级指针只能改变结构体的内容那我们在这里传的话难道不会产生问题吗答案是不会我们的结构体中放的就是指针那我们只需要改变结构体的内容就是head和tail就行竟然是这样的话我们传一个一级指针就可以起到我们的作用所以传的是一级那现在我们在插入函数中先创造一个节点因为只能从队列的尾插入而且有了这个指针我们就不需要像单链表那样再去找尾我们每次插入都会更新尾。
void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data data;newnode-next NULL;if (q-head NULL){q-head q-tail newnode;}else{q-tail-next newnode;q-tail newnode;}
}有了入栈就有出栈出栈的话是从我们的队列最开始的地方出队我们来实现一下吧
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext q-head-next;free(q-head);q-head headnext;}
/这里的空是因为如果我们的队列都是空的话我们哪里还有数据进行删除呢 所以要先检查一下是不是为空那接着我们把这个函数也实现一下吧
bool QueueEmpty(Queue* q)
{assert(q);return q-head NULL;
}这个很好理解如果为空就代表一个数也没有那我们就不能再对队列进行操作了那再来看我们下面的接口函数吧。
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q);return q-head-data;
}有头就有尾希望我们的人生也是 那我再来实现一下取尾的接口吧
QueueDataType QueueBack(Queue* q)
{assert(q);return q-tail-data;
}我们继续往下走实现一下我们后面的接口函数这些基本上都很简单我就也不再解释了看代码就能理解的
int QueueSize(Queue* q)
{assert(q);int count 0;QueueNode* cur q-head;while (cur){count;cur cur-next;}return count;
}销毁队列
void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext q-head-next;free(q-head);q-head headnext;}}统计我们队列节点的数量我们遍历一遍就可以实现了定义一个cur指针进行遍历那其他的我们也都讲完了后面分享栈和队列的OJ题给大家看完之后对队列有了更深的理解
完整代码
#includeQueue.h// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-head q-tail NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{assert(q);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data data;newnode-next NULL;if (q-head NULL){q-head q-tail newnode;}else{q-tail-next newnode;q-tail newnode;}
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QueueNode* headnext q-head-next;free(q-head);q-head headnext;}
// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{return q-head-data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{return q-tail-data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);int count 0;QueueNode* cur q-head;while (cur){count;cur cur-next;}return count;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q)
{assert(q);return q-head NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{while (!QueueEmpty(q)){QueueNode* headnext q-head-next;free(q-head);q-head headnext;}}#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int QueueDataType;
typedef struct QueueNode
{QueueDataType* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueDataType* head;QueueDataType* tail;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);今天的分享就到这里了我们下次再见
