企业官网建设流程全解析

目录

一、队列简单介绍

二、队列的实现

C语言代码：

Queue.h：引入头文件、定义队列的结构、声明队列的方法

Queue.c

1.初始化

2.销毁

3.队尾插入

4.队头删除

5.取队头数据

6.取队尾数据

7.返回队列元素个数

8.判空

9.输出队列全部元素

10.完整代码

三、循环队列

1.循环队列介绍

2.C语言实现循环队列(数组)

一、队列简单介绍

队列是只允许在一端进行插入操作，在另一端进行删除操作的特殊线性表。队列中的数据元素遵循先进先出FIFO(First In first Out)的原则。

入队列：进行插入操作的一段称为队尾

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

二、队列的实现

队列可以使用数组或链表的结构实现。使用链表的结构更优一些。

如果使用数组结构，出队列在数组头上出数据，效率会比较低。

如果使用链表结构，入队列即为尾插，出队列即为头删。

C语言代码：

Queue.h：引入头文件、定义队列的结构、声明队列的方法

#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; // 初始化 void QueueInit(Queue* pq); // 销毁 void QueueDestroy(Queue* pq); // 队尾插入 void QueuePush(Queue* pq, QDataType x); // 队头删除 void QueuePop(Queue* pq); // 取队头数据 QDataType QueueFront(Queue* pq); // 取队尾数据 QDataType QueueBack(Queue* pq); // 返回队列元素个数 int QueueSize(Queue* pq); // 判空 bool QueueEmpty(Queue* pq);

Queue.c

1.初始化

将队列大小置为0，并把队头和队尾指针置为空。

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

2.销毁

定义一个pcur代表当前节点，从队头开始。当pcur不为空时，将pcur指向的空间释放，再将pcur指向下一个结点。当pcur为空时退出循环，并将队列的头节点尾节点置空，队列大小置为0。

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

3.队尾插入

先申请一个新节点的空间，将新节点的val值赋值为x，新节点的next指向NULL，然后将新节点插入到队尾。此时有两种情况：队列为空和队列不为空。

当队列为空时，直接将队列的头指针和尾指针指向新节点即可。

当队列不为空时，将尾节点的next指向新节点，再将尾节点指向新节点。

最后将队列中数据个数+1。

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

4.队头删除

先判断队列是否为空。

如果队列不为空，删除队头元素，此时分为两种情况。

当队列中只有一个结点时，直接释放头指针指向的空间，再将头指针尾指针置为空。

当队列中有多个结点时，释放头指针指向的空间，再将头指针指向下一个结点即可。

最后队列元素个数-1。

// 队头删除 void QueuePop(Queue* pq) { assert(pq); assert(pq->size != 0); if (pq->phead == pq->ptail) { // 只有一个节点 free(pq->phead); pq->phead = pq->ptail = NULL; } else { // 有多个节点 QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }

5.取队头数据

返回头指针指向的结点的val值

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

6.取队尾数据

返回尾指针指向的结点的val值

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

7.返回队列元素个数

因为定义队列结构时定义了size，所以直接返回size

// 返回队列元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }

8.判空

队列的元素个数不等于0时返回true

// 判空 bool QueueEmpty(Queue* pq) { assert(pq); return (pq->size == 0); }

9.输出队列全部元素

队列不为空时，获取队头元素并输出，再将队头元素删除，循环直到队列为空。

while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n");

10.完整代码

#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" // 初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } // 销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } // 队尾插入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc fail"); return; } newNode->next = NULL; newNode->val = x; if (pq->ptail == NULL) { pq->phead = pq->ptail = newNode; } else { pq->ptail->next = newNode; pq->ptail = pq->ptail->next; } pq->size++; } // 队头删除 void QueuePop(Queue* pq) { assert(pq); assert(pq->size != 0); if (pq->phead == pq->ptail) { // 只有一个节点 free(pq->phead); pq->phead = pq->ptail = NULL; } else { // 有多个节点 QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } // 取队头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } // 取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } // 返回队列元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } // 判空 bool QueueEmpty(Queue* pq) { assert(pq); return (pq->size == 0); }

三、循环队列

1.循环队列介绍

使用数组实现队列会出现假溢出现象，可以使用循环队列避免假溢出。

循环队列有一个头指针一个尾指针。头指针指向循环队列的队头元素，尾指针指向队尾元素的下一个位置。

通常情况下，循环队列大小为N时，可以存储N-1个数据，尾指针指向的位置不存放数据。

所以当循环队列的头指针和尾指针指向同一个位置时，循环队列为空；当尾指针的next和头指针指向同一个位置时，循环队列为满。

使用数组存放时，判断循环队列满的条件是(tail + 1) % (k + 1) == head。其中tail表示队尾的下一个位置下标值，head表示队头的下标值，k表示队列中能存储的最大元素个数。

2.C语言实现循环队列(数组)

typedef struct { int* a; int head; int tail; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj -> a = malloc(sizeof(int)*(k+1)); obj -> head = 0; obj -> tail = 0; obj -> k = k; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if((obj->tail + 1)%(obj->k+1) == obj->head){ return false; } obj->a[obj->tail] = value; obj->tail++; obj->tail %= (obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj->head == obj->tail){ return false; } ++obj->head; obj->head %= (obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj->head == obj->tail){ return -1; }else{ return obj->a[obj->head]; } } int myCircularQueueRear(MyCircularQueue* obj) { if(obj->head == obj->tail){ return -1; }else{ return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)]; } } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head == obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return ((obj->tail + 1)%(obj->k+1) == obj->head); } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }

完