网站源码之家,网站企业网站建设需求文档,jsp做网站遇到的问题,沈阳做网站找黑酷科技目录
队列的概念及其结构
队列的实现
数组队列
链式队列
队列的常见接口的实现
主函数Test.c
头文件函数声明Queue.h
头文件
函数声明
函数实现Queue.c
初始化QueueInit
创建节点Createnode
空间释放QueueDestroy
入队列QueuePush
出队列QueuePop
队头元…目录
队列的概念及其结构
队列的实现
数组队列
链式队列
队列的常见接口的实现
主函数Test.c
头文件函数声明Queue.h
头文件
函数声明
函数实现Queue.c
初始化QueueInit
创建节点Createnode
空间释放QueueDestroy
入队列QueuePush
出队列QueuePop
队头元素QueueFront
队尾元素QueueBack
判断队列是否为空QueueEmpty
队列元素个数QueueSize
链式队列总代码 队列的概念及其结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。 队列具有 先进先出 /后进后出 FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾。 出队列进行删除操作的一端称为 队头。 队列的实现
队列的实现也有两种方式。队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低
数组队列 虽然数组也可以实现【队列】但是挪动数据的效率真的很低
链式队列
无论是【栈】还是【队列】双向链表都是通吃的。但是我们为了节省资源就是要用【单链表】去实现队列。我们用【单链表】去实现【队列】需要注意
入队列 尾插出队列 头删需要ptail指针维护队列最后一个元素需要phead指针维护队列最后一个元素二级指针一级指针带不带哨兵位的头节点都可哨兵位的头节点最后要释放空间 应用场景办理业务排队打号机。因为【队列】是绝对公平的。 队列的常见接口的实现
入队列和出队列的顺序都只有一种传二级指针/传一级指针的情况怎么去计算队列元素个数❓怎么用其他方式替代传二级指针❓空间换时间的方式链表都需要考虑❓链表没有元素❓链表只有一个元素//两种情况即对应指针的判断情况二级指针 头节点 返回值 结构体包含两个一级指针
主函数Test.c
#includeQueue.h
int main()
{Queue pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);QueuePush(pq, 77);QueuePush(pq, 7);while (!QueueEmpty(pq)){printf(队头元素%d\n, QueueFront(pq));//printf(队尾元素%d\n, QueueBack(pq));QueuePop(pq);}QueueDestroy(pq);return 0;
}
头文件函数声明Queue.h
头文件
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
函数声明
创建节点
typedef int QDataType;
//创建队列节点
typedef struct QueueNode
{QDataType val;struct QueueNode* next;//易错❌QNode*next
}QNode;
创建维护队列的指针
//两个指针维护链表队列
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
初始化
void QueueInit(Queue* pq);
销毁释放空间
void QueueDestroy(Queue* pq);
入队列
void QueuePush(Queue* pq, QDataType x);
出队列
void QueuePop(Queue* pq);
队头元素
QDataType QueueFront(Queue* pq);
队尾元素
QDataType QueueBack(Queue* pq);
判断队列是否为空
bool QueueEmpty(Queue* pq);
队列元素个数
int QueueSzie(Queue* pq);
函数实现Queue.c
初始化QueueInit
#includeQueue.h
//不需要头节点初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
创建节点Createnode
Queue* Createnode(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(fail malloc);return;}newnode-val x;newnode-next NULL;return newnode;
}
空间释放QueueDestroy
//空间释放
void QueueDestroy(Queue* pq)
{assert(pq);while (pq-phead){Queue* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}
入队列QueuePush
//Push元素
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建节点Queue* newnode Createnode(pq,x);if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
出队列QueuePop
删到空的情况phead/ptail野指针的情况删到只剩一个节点的情况ptail野指针的情况
//Pop元素
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size 0);//为NULL的判断Queue* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;//为一个节点的判断if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}
队头元素QueueFront
//队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-size 0);return pq-phead-val;
}
队尾元素QueueBack
//队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-size 0);return pq-ptail-val;
}
判断队列是否为空QueueEmpty
//判断是否为NULL
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
队列元素个数QueueSize
//队员元素个数
int QueueSzie(Queue* pq)
{assert(pq);return pq-size;
}
链式队列总代码
//Test.c
#includeQueue.h
int main()
{Queue pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);QueuePush(pq, 77);QueuePush(pq, 7);while (!QueueEmpty(pq)){printf(队头元素%d\n, QueueFront(pq));//printf(队尾元素%d\n, QueueBack(pq));QueuePop(pq);}QueueDestroy(pq);return 0;
}
//Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int QDataType;
//创建队列节点
typedef struct QueueNode
{QDataType val;struct QueueNode* next;//易错❌QNode*next
}QNode;
//两个指针维护链表队列
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//接口的实现
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//空间释放
void QueuePush(Queue* pq, QDataType x);//放元素到队列尾
void QueuePop(Queue* pq);//出元素到队头
QDataType QueueFront(Queue* pq);//队列头的元素
QDataType QueueBack(Queue* pq);//队列尾的元素
bool QueueEmpty(Queue* pq);//判断队列是否是否为NULL
int QueueSzie(Queue* pq);//队列里面的元素个数
//Queue.c
#includeQueue.h
//不需要头节点初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}Queue* Createnode(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(fail malloc);return;}newnode-val x;newnode-next NULL;return newnode;
}
//Push元素
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建节点Queue* newnode Createnode(pq,x);if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}//Pop元素
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size 0);//为NULL的判断Queue* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;//为一个节点的判断if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}//队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-size 0);return pq-phead-val;
}//队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-size 0);return pq-ptail-val;
}//判断是否为NULL
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}//队员元素个数
int QueueSzie(Queue* pq)
{assert(pq);return pq-size;
}//空间释放
void QueueDestroy(Queue* pq)
{assert(pq);while (pq-phead){Queue* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}✔✔✔✔✔最后感谢大家的阅读若有错误和不足欢迎指正下篇博文会分享一些【栈和队列的OJ题目】【循环队列】各位小伙伴乖乖敲代码哦。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱2784139418qq.com】
