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

队列介绍

队列概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFO（First In First Out）的原则。

入队列：队列的插入操作叫做入队列，进行插入操作的一端称为队尾。

出队列：队列的删除操作叫做出队列，进行删除操作的一端称为队头

队列的结构

生活中的队列

在生活中最常见的队列无非就是在食堂的窗口进行打饭了，总是先去排队的同学先离开队列。

队列的实现

队列的初始化

typedefintQDataType;//方便以后修改存储的数据类型typedefstructQueueNode//队列中的节点{QDataType val;structQueueNode*next;}QueueNode;typedefstructQueue{QueueNode*phead;QueueNode*ptail;intsize;//不要忘了保存数列的有效数据个数}Queu

队列底层一般是用单链表来实现，然后队列本身有队头指针和队尾指针，还有有效数据个数size组成

voidQueueInit(Queue*pq){assert(pq);pq->phead=pq->ptail=NULL;pq->size=0;}

队列的销毁

voidQueueDestroy(Queue*pq){assert(pq);while(pq->phead!=pq->ptail){QueueNode*del=pq->phead;pq->phead=pq->phead->next;free(del);del=NULL;}free(pq->phead);pq->phead=NULL;pq->ptail=NULL;//不要忘了把ptail也设置NULL,虽然他们是指向同一块空间，但是指针变量不是同一块空间pq->size=0;//不要忘了把size设置0}

这里要注意释放队尾指针，虽然最后都是指向和队头指向的同一块空间，但是指针变量的空间不一样

队尾入队列

这里入队列就要创建一个节点

QueueNode*QBuyNode(QDataType x){QueueNode*tmp=(QueueNode*)malloc(sizeof(QueueNode));if(tmp==NULL){perror("malloc failed");exit(1);}tmp->val=x;tmp->next=NULL;returntmp;}

voidQueuePush(Queue*pq,QDataType x){assert(pq);QueueNode*newnode=QBuyNode(x);//注意考虑队列为空的情况if(pq->phead==NULL)//队列为空{pq->phead=pq->ptail=newnode;}else{pq->ptail->next=newnode;pq->ptail=newnode;}pq->size++;}

注意队列为空的情况，队头和对尾是指向同一个节点

队头出队列

voidQueuePop(Queue*pq){assert(pq);assert(!QEmpty(pq));//assert为假就会触发if(pq->phead==pq->ptail)//如果队列只有一个数据,所有数据结构最好都考虑为空和只有一个数据的情况{free(pq->phead);pq->phead=pq->ptail=NULL;}else{QueueNode*del=pq->phead;pq->phead=pq->phead->next;free(del);del=NULL;}//不要搞忘了--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;}