一篇博客读懂队列——Queue

目录

一、队列的概念和结构

​二、队列的实现 

2.1队列的初始化QueueInit 

2.2队列的摧毁QueueDestroy

2.3插入结点QueuePush

 2.4删除结点QueuePop

2.5返回队头QueueFront

2.6返回队尾QueueBack

2.7判断队列为空QueueEmpty

2.8统计队列数目QueueSize

---

一、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出性质。
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾

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

 二、队列的实现 

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

当用链表实现时，我们布置的结构体肯定要包含一个val，还需要一个next。

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;

但结构体的布置并非到这里就结束了，当我们有数据要入队时，我们是不是需要让头指针遍历一遍链表找到队尾呢？而且要改变队尾前一个结点next的指向，是不是要传入二级指针呢？同样，当我们布置其他函数体时也会遇到类似的问题。那么如何让我们的代码量化到最简呢？

我们再设置一个结构体来存储相关的数据，这样修改指向时不用再用二级指针，而是只需要修改结构体的值即可。我们用phead指向队列的头结点，便于出队；用ptail指向队列的尾结点，便于入队

typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

2.1队列的初始化QueueInit 

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

2.2队列的摧毁QueueDestroy

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.3插入结点QueuePush

首先我们要新开结点，其次我们要判断链表是否为空，如果为空，那么ptail和phead都指向新结点；如果不为空，phead的指向不用改变，而ptail的next要只想newnode，然后再把ptail向后移

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->ptail = pq->phead = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

 2.4删除结点QueuePop

首先先让队头指向next结点，接着我们就要判断删除的是不是整个队列的最后一个结点，如果删除的是最后一个结点，那么就会影响到我们ptail的指向，所以我们通过判断避免ptail变成野指针。

void QueuePop(Queue* pq)
{assert(pq);// assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL)pq->ptail = NULL;pq->size--;
}

2.5返回队头QueueFront

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.6返回队尾QueueBack

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

2.7判断队列为空QueueEmpty

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

2.8统计队列数目QueueSize

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}