【把玩数据结构】详解队列

目录队列介绍队列概念队列的结构生活中的队列队列的实现队列的初始化队列的销毁队尾入队列队头出队列获得队头元素获得队尾元素统计队列元素个数队列介绍队列概念队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFOFirst In First Out的原则。入队列队列的插入操作叫做入队列进行插入操作的一端称为队尾。出队列队列的删除操作叫做出队列进行删除操作的一端称为队头队列的结构生活中的队列在生活中最常见的队列无非就是在食堂的窗口进行打饭了总是先去排队的同学先离开队列。队列的实现队列的初始化typedefintQDataType;//方便以后修改存储的数据类型typedefstructQueueNode//队列中的节点{QDataType val;structQueueNode*next;}QueueNode;typedefstructQueue{QueueNode*phead;QueueNode*ptail;intsize;//不要忘了保存数列的有效数据个数}Queu队列底层一般是用单链表来实现然后队列本身有队头指针和队尾指针还有有效数据个数size组成voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;pq-size0;}队列的销毁voidQueueDestroy(Queue*pq){assert(pq);while(pq-phead!pq-ptail){QueueNode*delpq-phead;pq-pheadpq-phead-next;free(del);delNULL;}free(pq-phead);pq-pheadNULL;pq-ptailNULL;//不要忘了把ptail也设置NULL,虽然他们是指向同一块空间但是指针变量不是同一块空间pq-size0;//不要忘了把size设置0}这里要注意释放队尾指针虽然最后都是指向和队头指向的同一块空间但是指针变量的空间不一样队尾入队列这里入队列就要创建一个节点QueueNode*QBuyNode(QDataType x){QueueNode*tmp(QueueNode*)malloc(sizeof(QueueNode));if(tmpNULL){perror(malloc failed);exit(1);}tmp-valx;tmp-nextNULL;returntmp;}voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnodeQBuyNode(x);//注意考虑队列为空的情况if(pq-pheadNULL)//队列为空{pq-pheadpq-ptailnewnode;}else{pq-ptail-nextnewnode;pq-ptailnewnode;}pq-size;}注意队列为空的情况队头和对尾是指向同一个节点队头出队列voidQueuePop(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假就会触发if(pq-pheadpq-ptail)//如果队列只有一个数据,所有数据结构最好都考虑为空和只有一个数据的情况{free(pq-phead);pq-pheadpq-ptailNULL;}else{QueueNode*delpq-phead;pq-pheadpq-phead-next;free(del);delNULL;}//不要搞忘了--sizepq-size--;}注意队列只有一个数据的情况和size–。获得队头元素QDataTypeQueueFront(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假会触发returnpq-ptail-val;}获得队尾元素QDataTypeQueueBack(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假会触发returnpq-ptail-val;}统计队列元素个数intQueueSize(Queue*pq){assert(pq);returnpq-size;}