网站建设开发的规划流程,厦门网站的制作,衡水医院网站建设,家装设计费用多少钱一平方目录
0.前言
1.什么是队列 2.选择什么结构实现队列
3.用C语言实现队列
3.1用什么可以封装代表一个队列
3.2队列接口的设计
3.3 队列的初始化
3.4 队列的销毁
3.5* 队列的状态分析
3.6 队列的插入
3.7 队列的删除
3.8 队列的大小#xff08;有效元素的数目#xff…目录
0.前言
1.什么是队列 2.选择什么结构实现队列
3.用C语言实现队列
3.1用什么可以封装代表一个队列
3.2队列接口的设计
3.3 队列的初始化
3.4 队列的销毁
3.5* 队列的状态分析
3.6 队列的插入
3.7 队列的删除
3.8 队列的大小有效元素的数目
3.9判断队列是否为空
3.10 获取队头数据
3.11 获取队尾数据
4.测试实现的队列 0.前言 4队列的实现 · onlookerzy123456qwq/data_structure_practice_primer - 码云 - 开源中国 (gitee.com)https://gitee.com/onlookerzy123456qwq/data_structure_practice_primer/tree/master/4%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9E%E7%8E%B0本文所有代码都已上传至gitee可以自取。 1.什么是队列 我们想象一个管道在这个管道运行的时候比如我们现在要输送石油从新疆到上海那么这个管道当中石油是从新疆端 入的石油是从上海端 出的并且石油只允许从新疆输入石油只允许从上海端输出。同时在管道里的石油肯定是先输入的石油更快到达上海后面输入的石油是在先输入的石油到达之后才到达上海因为先输入的石油是堵在管道前面的必须先进的先出之后后进的才能出。 这个管道就是一个队列。先后输入的石油就是队列里面的元素。 栈是只允许在一端进行插入/删除而我们的队列与之相反队列是只允许在一端进行插入只能在相反的另一端进行删除。 同时队列也是只能先进先出的后进后出的先入队列的元素肯定是堵在后入队列的元素的前面必须先入队列的数据先出队列之后相对后入的队列才能出队列。 负责插入入队列的一端称为队尾负责删除出队列的一端称之为队头。 2.选择什么结构实现队列 实现队列我们可供选择的有两种结构一种是顺序表结构一种是链式结构在这个效率至上的时代我们肯定是选择链式结构实现队列因为队列是只允许在一端插入另一端删除的所以我们就需要 头插配尾删此时顺序表/链表的头部是队尾尾部是队头 或者是 头删配尾插此时此时顺序表/链表的头部是队头尾部是队尾而我们的顺序表天然在头部进行插入删除的效率是极低的效率为ON因为需要挪动数据。所以链表结构便成为了不二选择。 我们以单链表的头head 作为队列的队头出数据以单链表的尾tail 作为队列的队尾入数据 单链表头删的效率是O1但是单链表尾插由于需要找尾效率会降为ON这是这并没有太大的关系因为我们在用链式结构实现队列的时候可以一直记录tail尾的位置即我们在封装Queue的时候除了记录头节点head的位置也记录住尾节点tail的位置每次删除/插入操作的时候适当更新tail就不用找尾此时我们对tail尾部的插入的效率就也是O1了。 3.用C语言实现队列
3.1用什么可以封装代表一个队列 我们选择的是一个链式结构作为基础实现队列所以我们要保存一个单链表如何代表一个单链表其实我们只需要记录一个单链表的头head即可。同时为了方便我们进行尾插我们还需要维护一个单链表的tail指针。 所以队列通过一个链表节点head和tail指针就可代表了。 所以我们定义一个存储队列数据的节点struct Node类然后对封装的Queue类当中封装两个节点指针headtail即可。 //范式类型
typedef int QDataType;//节点
typedef struct QueueNode
{QDataType _data;struct QueueNode* _next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* _head;//队头QueueNode* _tail;//队尾
}Queue;3.2队列接口的设计 我们要修改的是一个队列Queue q对象我们就不能做对Queue q的直接传值传参因为这样的话就是在调用的函数栈帧当中拷贝一个相同的Queue tmp_q并不是这个我们的q。 所以我们应该传入的是main函数当中Queue q对象的指针即Queue* pq你传入的是q对象的指针这样pq指向的就是我main函数中的q实体了在Func函数当中指针找到的也是main函数当中的q实体。 所以接口我们这样设计 //队列相关接口
/*传入一级指针即可传入(指向[Queue两个指针实体]的指针可以修改Queue *head *tail实体)*/
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);3.3 队列的初始化 我们定义出来一个队列类的对象那这个对象里面的_head和_tail一定是随机值野指针如果不对之进行初始化那后续我们对这个队列进行插入删除等操作的时候灾难性的野指针问题就会暴露出来非法访问。 所以每次定义一个队列我们都要对这个队列对象进行初始化 void QueueInit(Queue* pq)
{//须传入队列实体assert(pq);pq-_head NULL;pq-_tail NULL;
}3.4 队列的销毁 每次使用完队列我们不能就不管了因为堆区申请的空间需要我们主动释放在这个队列的实现当中我们是在堆区里申请了一个一个的节点组成了一个链表如果不释放的话那么就会造成内存泄漏这些堆区空间就会一直被“霸占”着无法被再使用。 所以每次使用完一个队列我们都要对之释放清理资源 void QueueDestroy(Queue* pq)
{//须传入队列实体assert(pq);//依次释放所有的节点QueueNode* cur pq-_head;while(cur){QueueNode* next cur-_next;free(cur);cur next;}//置空,防止野指针pq-_head NULL;pq-_tail NULL;
}3.5* 队列的状态分析 我们分析一下队列在各个状态下_head _tail成员的实际情况 队列空的时候head和tail都是NULL。 在通常情况下队列_head指向队头的数据节点 负责删除更新头删_tail指向队尾的数据节点负责插入更新尾插。 再紧接着分析一下队列的插入删除对_head_tail成员的影响 对队列插入就是在_tail的后面进行链接新创建的节点并记录更新_tail为新节点。对队列的删除就是对_head所在位置的节点释放删除并记录更新_head为原来_head的下一个节点的位置。 但是这样真的就行了吗入队列即尾插真的只更新_tail就行了吗出队列即头删真的只更新_head就行了吗当然不行 万一现在是空队列_head和_tail都是NULL空那你入队列插入一个数据此时_head和_tail都需要更新为新节点不能只顾_tail。万一现在队列只有一个节点那你删除之后此时_head和_tail也都想需更新为NULL不能只顾_head。 3.6 队列的插入 大致思路就是创建新节点然后链接到tail后面并更新tail。 检查队列是合法的用户传入的是一个有效队列指针提前判断一开始队列就是空的特殊情况此时除了_tail需要更新为新节点_head也需要更新。 void QueuePush(Queue* pq,QDataType x)
{//须传入队列实体assert(pq);//创建新节点QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));newnode-_next NULL;newnode-_data x;/*插入分两种情况情况一直接在tail后面链接新节点然后更新tail即可情况二队列为空headtailNULL此时需要更新headtail为新节点指针*/if (pq-_head NULL)//QueueEmpty(pq){pq-_head newnode;pq-_tail newnode;}else {pq-_tail-_next newnode;pq-_tail newnode;}
}3.7 队列的删除 大致思路就是把_head指向的队头的节点进行释放删除然后更新_head为下一个节点的位置。 检查队列是合法的用户传入的是一个有效队列指针检查此时队列不为空为空即没有有效数据不能进行删除需要报错提前判断一开始队列就是只有一个节点的特殊情况此时除了_tail需要更新为NULL_head也需要更新且更新为NULL。 void QueuePop(Queue* pq)
{//传入有效队列assert(pq);//有有效数据即队列非空才可以删assert(!QueueEmpty(pq));//pq-_head ! NULL/*分两种情况情况一直接删除head节点,然后更新head到next第二个节点的指针情况二现在只有一个节点,删除该节点后head变成next空节点NULL,此时tail也需更新为NULL,因为现在tail还指向着刚刚删除的节点的空间,出现野指针问题*/QueueNode* next pq-_head-_next;free(pq-_head);pq-_head next;if (pq-_head NULL)//删除到空{pq-_tail NULL;}
}
3.8 队列的大小有效元素的数目 获取当前队列里面一共有多少个有效数据其实就是看从_head到_tail这两个节点之间有多少个有效节点数据。思路就是依次从_head往后直至遍历到NULL统计数量。 int QueueSize(Queue* pq)
{//须传入队列实体assert(pq);//链式结构通常不存节点数目//所以通常进行遍历统计int size 0;QueueNode* cur pq-_head;while (cur){cur cur-_next;size;}return size;
}
3.9判断队列是否为空 队列为空的时候_head为NULL。 bool QueueEmpty(Queue* pq)
{ //须传入队列实体assert(pq);//队头是空即可return pq-_head NULL;
}3.10 获取队头数据 获取队头的数据即下一个要出队列的队头QueueFront但是需要判断队列不为空如果队列为空即没有有效数据的话那就是需要报错的。 QDataType QueueFront(Queue* pq)
{//传入有效队列实体assert(pq);//必须有数据队列非空才能取assert(!QueueEmpty(pq));//Front就是队头head的元素数据return pq-_head-_data;
}3.11 获取队尾数据 获取队尾的数据即最近一次插入的队列的队尾QueueBack但是需要判断队列不为空如果队列为空即没有有效数据的话那就是需要报错的。 QDataType QueueBack(Queue* pq)
{//传入有效队列实体assert(pq);//必须有数据队列非空才能取assert(!QueueEmpty(pq));//Back就是队尾tail的元素数据return pq-_tail-_data;
}
4.测试实现的队列 任何实现都离不开测试这里笔者建议大家不要写一堆之后再测试应该最好是写一点测一点写一个接口测试一下这样可以帮助我们快速的定位问题bug的所在处。这并不是在浪费时间而是在节省时间。 void QueueTest1()
{Queue q;QueueInit(q);printf(Queue Size:%d\n, QueueSize(q));printf(Queue Empty:%d\n, QueueEmpty(q));QueueDestroy(q);
}
void QueueTest2()
{Queue q;QueueInit(q);QueuePush(q,5);QueuePush(q, 9);QueuePush(q, 7);printf(Queue Size:%d\n, QueueSize(q));printf(Queue Empty:%d\n, QueueEmpty(q));QueueDestroy(q);
}
void QueueTest3()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 0);QueuePush(q, 0);QueuePush(q, 8);QueuePush(q, 6);printf(Queue Size:%d\n, QueueSize(q));printf(Queue Empty:%d\n, QueueEmpty(q));QueuePop(q);printf(Queue Size:%d\n, QueueSize(q));QueueDestroy(q);
}
void QueueTest4()
{Queue q;QueueInit(q);QueuePush(q, 1);printf(Queue Back:%d , QueueBack(q));QueuePush(q, 0);printf(Queue Back:%d , QueueBack(q));QueuePush(q, 0);printf(Queue Back:%d , QueueBack(q));QueuePush(q, 8);printf(Queue Back:%d , QueueBack(q));QueuePush(q, 6);printf(Queue Back:%d , QueueBack(q));printf(\n);printf(Queue Size:%d\n, QueueSize(q));printf(Queue Empty:%d\n, QueueEmpty(q));//测试具体的遍历栈的过程//数据是先进先出while (!QueueEmpty(q)){printf(Queue Front:%d Pop\n, QueueFront(q));QueuePop(q);}
}
int main()
{//QueueTest1();//QueueTest2();//QueueTest3();QueueTest4();return 0;
}
