企业官网建设流程全解析

目录

一.队列的创建

二.队列的初始化

三.入队

四.判空

五.出队

六.求队列的长度

七.取队头元素

八.取队尾元素

九.销毁

一.队列的创建

相比于顺序表使用链表结构更易于理解队列和书写代码。我们知道，单链表头插头删的时间复杂度都是O（1），尾插和尾删的时间复杂度是O（N），有什么方法能够降低尾插和尾删的时间复杂度吗？想到链表有一个指针phead指向第一个节点，类比下，同样可以设置一个指针patil指向尾节点，这样对于尾部的操作的时间复杂度就将为O（1）。

所以，队列的结构就是一个头节点phead，一个尾节点ptail。但是队列毕竟是由链表组成，所以队列节点的结构也就是链表的结构。

队列的特点是：先进先出，后进后出。队尾入数据，队头出数据。所以我们将链表的头作为队头，链表的尾作为队尾。

代码如下：

typedef int QDataType; //队列结点的结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列的结构 typedef struct Queue { QueueNode* phead; QueueNode* ptail; //int size; //队列中有效数据个数 }Queue;

二.队列的初始化

在链表部分对链表的初始化是将头指针置为NULL，data置为0，而到了队列这里,多一个ptail变量，与phead的处理相同，置为NULL。

不过，要对传过来的形参断言，没有地址的队列就是没有创建，没创建就无法初始化。

代码如下：

//初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; }

三.入队

入队的思路与单链表尾插异曲同工，插入前先开辟新节点，判断队列是否为空，即头尾指针是否相等，为空则将新结点"头插"进队列，不为空“尾插”进队列即可。

同样要进行断言操作。

代码如下：

//入队——队尾 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; //队列为空 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { //队列非空 pq->ptail->next = newnode; pq->ptail = pq->ptail->next; } }

四.判空

判空对于出队和取队头，队尾操作而言很重要，如果队列为空就无法出队。如果phead为空返回true，否则返回false。

同样进行断言操作。

代码如下：

//队列判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }

五.出队

判断队列是否为空队列，如果是,抛出异常终止程序，如果不是，使用一个指针记录下当前队头的下一个结点的位置，释放当前队头结点,然后更新队头指针。

与单链表的尾删操作相同，同样需要判断队列中是否仅剩一个结点，如果只剩一个结点,释放该结点,然后将head和tail置为空。

代码如下：

//出队——队头 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); //只有一个节点，phead和ptail都套置为空 if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } }

六.求队列的长度

求队列长度的思路是：创建一个新指针来储存头节点的位置，遍历队列，直至pcur为空，每次循环size++，最后返回size即可。

代码如下：

//队列有效元素个数 int QueueSize(Queue* pq) { assert(pq); //遍历链表——适用于不会频繁调用队列有效数据个数的场景 QueueNode* pcur = pq->phead; int size = 0; while (pcur) { size++; pcur = pcur->next; } return size;

七.取队头元素

取队头元素思路:判断队列是否为空，不为空返回队头指针指向的头节点的数据域即可。

代码如下：

//取队头数据 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq->phead->data; }

八.取队尾元素

取队尾元素思路:判断队列是否为空，不为空返回队尾指针指向的尾节点的数据域即可。

代码如下：

//取队尾数据 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq->ptail->data; }

九.销毁

销毁思路:从头遍历队列的元素,逐一释放链队列中的结点。释放完将队头指针和队尾指针置为NULL。

代码如下：

//销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while(pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; }

希望对大家有帮助！共勉！