当前位置： 首页 > news >正文

那家网站建设好网站建设设计ppt

news 2025/9/18 3:14:05
那家网站建设好,网站建设设计ppt,整合营销传播名词解释,美食网站建设的栏目和模板目录 队列的定义 普通顺序队列的劣势——与链队列相比 顺序队列实现方法： 一、动态增长队列 1、初始化队列 2、元素入队 3、判断队列是否为空 4、元素出队 5、获取队首元素 6、获取队尾元素 7、获取队列元素个数 8、销毁队列 总结： 动态增长队列…

目录

队列的定义

普通顺序队列的劣势——与链队列相比 

顺序队列实现方法：

一、动态增长队列

 1、初始化队列

 2、元素入队

 3、判断队列是否为空

 4、元素出队

 5、获取队首元素

6、获取队尾元素

 7、获取队列元素个数

8、销毁队列

 总结：

动态增长队列完整测试代码：

二、固定长度队列 

1、与动态增长队列的差异

2、判断是否队满 

固定长度队列完整测试代码：

本节我们采用数组（顺序表）形式实现队列，学习单链表实现请点击下方链接：

队列—单链表实现（C语言版）-CSDN博客

为了减少数组初始长度过大对内存空间的浪费，本节我们采用动态内存管理，相关函数请的介绍点击下方链接：

动态内存函数（malloc，free，calloc，realloc）-CSDN博客

循环队列的实现：

循环队列（数组实现）-CSDN博客


 

队列的定义

队列是一种基本的数据结构，它是一种先进先出（First In First Out，FIFO）的线性结构。队列只允许在表的一端进行插入，而在另一端进行删除操作。这就相当于把数据排成一排，先插入的排在前面，后插入的排在后面，之后进行删除操作时也只能从前面依次删除。这种数据结构一般用于需要按照先后顺序进行处理的问题，如模拟系统、计算机网络中的缓存、操作系统中的进程调度等。队列的基本操作包括入队（插入元素到队尾）和出队（从队头删除元素），队列还有一个重要的特性就是队列的长度是动态变化的，随着入队和出队的操作进行不断变化。

 ​​

普通顺序队列的劣势——与链队列相比 

  1. 长度固定：普通数组队列的长度是固定的，一旦数组被分配，其长度无法改变。当队列元素数量超过数组长度时，需要进行数组的扩容操作，这会导致性能上的开销。

  2. 内存的浪费：因为普通数组队列的长度固定，可能会出现队列中存在空闲的位置，导致内存的浪费。

为了解决上述 问题1，我们在本节中对顺序表采取动态内存管理，在必要时更新数组的长度，以保证顺序队列的长度足够使用。

 （补充：问题2 的解决需要使用循环队列，本节内容先为大家介绍一般队列的实现，等同学们对队列有了充分的理解之后，我们下节再进行循环队列的学习。）

顺序队列实现方法：

一、我们首先定义一个数组，数组的头部为队首，尾部为队尾。每当插入一个元素时，就将元素放在队尾，当删除一个元素时，将队首的元素删除。当队列为空时，不能再删除元素。

二、我们采用双指针法时刻记录队列的队首和队尾：

  1. 定义一个固定大小的数组作为队列的存储空间，并定义两个指针front和rear分别指向队列的队首和队尾。

  2. 初始化队列时，将front和rear都设置为0，表示队列为空。

  3. 插入元素时，将元素放入rear指针指向的位置，并将rear指针后移一位。

  4. 删除元素时，将front指针后移一位。

  5. 判断队列是否为空，只需要判断front和rear是否相等即可。

一、动态增长队列

 1、初始化队列

初始化队列时，将front和rear都设置为0，表示队列为空。

typedef int DataType;typedef struct Queue
{DataType* a; // 队列的数组int front, rear; // 队列的头部和尾部位置索引int size; // 队列中元素的数量int capacity; // 队列的容量
} Queue;// 初始化队列
void InitQueue(Queue* q)
{q->a = NULL; // 数组指针初始化为NULLq->front = q->rear = 0; // 头部和尾部位置索引初始化为0q->size = q->capacity = 0; // 元素数量和容量都初始化为0
}

 2、元素入队

// 入队
void QueuePush(Queue* q, DataType x)
{assert(q); // 断言q不为NULLif (q->capacity == q->rear){// 如果队列已满，进行扩容操作int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间if (temp == NULL){perror("realloc fail"); // 扩容失败，则输出错误信息exit(-1); // 退出程序}q->capacity = new_capacity; // 更新队列的容量q->a = temp; // 更新数组指针}q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引q->size++; // 元素数量加1
}

 3、判断队列是否为空

判断队列是否为空，只需要判断front和rear是否相等即可。

// 判断队列是否为空
bool QueueEmpty(Queue* q)
{assert(q); // 断言q不为NULLif (q->front == q->rear){return true; // 头部和尾部位置索引相等，队列为空}return false; // 队列不为空
}

 4、元素出队

 删除元素时，将front指针后移一位。

void QueuePop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){q->front++; // 更新头部位置索引q->size--; // 元素数量减1}else{printf("队列已空，删除失败！\n"); // 队列为空，无法出队}
}

5、获取队首元素

// 获取队首元素
DataType QueueTop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->front]; // 返回队首元素的值}else{printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素exit(-1); // 退出程序}
}

6、获取队尾元素

队尾指针q->rear在最后一个元素的下一位，所以我们返回队尾元素时需要返回队尾坐标的前一个坐标所指向的元素。

// 获取队尾元素
DataType QueueTail(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->rear - 1]; // 返回队尾元素的值}else{printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素exit(-1); // 退出程序}
}

7、获取队列元素个数

// 获取队列中元素的数量
int QueueSize(Queue* q)
{assert(q); // 断言q不为NULLreturn q->size; // 返回元素数量
}

8、销毁队列

// 销毁队列
void QueueDestory(Queue* q)
{assert(q); // 断言q不为NULLfree(q->a); // 释放队列的数组空间q->a = NULL; // 数组指针置为NULL
}

总结：

 通过对顺序队列的学习我们可以明显看到顺序队列的缺点。当我们删除队首元素后，由于队列只能从队尾进行增加元素的操作，所以front指针之前的空间不能再进行使用。

如果是在队列长度是固定长度的情况下，当队尾指针rear到达最大时，队列已满，数组内已经没有空间进行插入操作，但由于此时front指针前可能还有空余空间，这时我们就造成了空间的浪费。

我们把这种现象称为“假溢出”现象。那么通过数组的循环队列或者链队列我们可以很好的解决此类现象。

下节我们将对如何用数组实现循环队列进行介绍：循环队列（数组实现）-CSDN博客

动态增长队列完整测试代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int DataType;typedef struct Queue
{DataType* a; // 队列的数组int front, rear; // 队列的头部和尾部位置索引int size; // 队列中元素的数量int capacity; // 队列的容量
} Queue;// 初始化队列
void InitQueue(Queue* q)
{q->a = NULL; // 数组指针初始化为NULLq->front = q->rear = 0; // 头部和尾部位置索引初始化为0q->size = q->capacity = 0; // 元素数量和容量都初始化为0
}// 判断队列是否为空
bool QueueEmpty(Queue* q)
{assert(q); // 断言q不为NULLif (q->front == q->rear){return true; // 头部和尾部位置索引相等，队列为空}return false; // 队列不为空
}// 入队
void QueuePush(Queue* q, DataType x)
{assert(q); // 断言q不为NULLif (q->capacity == q->rear){// 如果队列已满，进行扩容操作int new_capacity = q->capacity == 0 ? 10 : q->capacity * 2; // 扩容的大小为原容量的2倍DataType* temp = (DataType*)realloc(q->a, new_capacity * sizeof(DataType)); // 重新分配内存空间if (temp == NULL){perror("realloc fail"); // 扩容失败，则输出错误信息exit(-1); // 退出程序}q->capacity = new_capacity; // 更新队列的容量q->a = temp; // 更新数组指针}q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引q->size++; // 元素数量加1
}// 出队
void QueuePop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){q->front++; // 更新头部位置索引q->size--; // 元素数量减1}else{printf("队列已空，删除失败！\n"); // 队列为空，无法出队}
}// 获取队首元素
DataType QueueTop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->front]; // 返回队首元素的值}else{printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素exit(-1); // 退出程序}
}// 获取队尾元素
DataType QueueTail(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->rear - 1]; // 返回队尾元素的值}else{printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素exit(-1); // 退出程序}
}// 获取队列中元素的数量
int QueueSize(Queue* q)
{assert(q); // 断言q不为NULLreturn q->size; // 返回元素数量
}// 销毁队列
void QueueDestory(Queue* q)
{assert(q); // 断言q不为NULLfree(q->a); // 释放队列的数组空间q->a = NULL; // 数组指针置为NULL
}int main()
{Queue q;InitQueue(&q);QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);QueuePush(&q, 9);QueuePush(&q, 10);DataType x;x = QueueTop(&q);printf("%d\n", x);x = QueueTail(&q);printf("%d\n", x);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);x = QueueTop(&q);printf("%d\n", x);x = QueueSize(&q);printf("%d\n", x);QueueDestory(&q);return 0;
}

二、固定长度队列 

1、与动态增长队列的差异

由于固定长度队列无需扩容，所以不需要进行动态内存的分配，也不需要进行销毁队列的操作。

同时相对于动态增长的队列，固定长度的队列需要判断队内元素数量是否达到了队列的最大容量。由于我们在代码中是先对队尾指针rear指向的位置添加元素，再对rear进行自增，更新队尾索引，所以在本代码中队满的判断条件是rear==MAXLEN。

2、判断是否队满 

当对固定长度队列添加元素时，如果当前队列队尾指针已达到数组长度，由于队列只能从队尾添加元素，此时我们不能再为队列添加新的元素。所以在我们为队尾添加元素时，我们首先要判断队列是否已满——即队尾指针是否达到数组容量的最大值。

//判断队列是否为满
bool QueueFull(Queue* q)
{assert(q); // 断言q不为NULLif (q->rear == MAXLEN){return true; // 尾部位置达到数组长度最大值，队列为满}return false; // 队列不为满
}

明白了以上几点，我们对动态增长队列的代码稍作修改，添加判断队列是否已满的函数并对增加队列元素作出限制，就可得到固定长度队列的代码。

固定长度队列完整测试代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>#define MAXLEN 10
typedef int DataType;typedef struct Queue
{DataType a[MAXLEN]; // 队列的数组int front, rear; // 队列的头部和尾部位置索引int size; // 队列中元素的数量
} Queue;// 初始化队列
void InitQueue(Queue* q)
{assert(q);q->front = q->rear = 0; // 头部和尾部位置索引初始化为0q->size = 0; // 元素数量初始化为0
}// 判断队列是否为空
bool QueueEmpty(Queue* q)
{assert(q); // 断言q不为NULLif (q->front == q->rear){return true; // 头部和尾部位置索引相等，队列为空}return false; // 队列不为空
}//判断队列是否为满
bool QueueFull(Queue* q)
{assert(q); // 断言q不为NULLif (q->rear == MAXLEN){return true; // 尾部位置达到数组长度最大值，队列为满}return false; // 队列不为满
}// 入队
void QueuePush(Queue* q, DataType x)
{assert(q); // 断言q不为NULLif (!QueueFull(q))//判断队列是否为满{q->a[q->rear++] = x; // 在尾部插入新元素，并更新尾部位置索引q->size++; // 元素数量加1}else{printf("队列已满\n");exit(-1);}
}// 出队
void QueuePop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){q->front++; // 更新头部位置索引q->size--; // 元素数量减1}else{printf("队列已空，删除失败！\n"); // 队列为空，无法出队}
}// 获取队首元素
DataType QueueTop(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->front]; // 返回队首元素的值}else{printf("队列已空，获取队头元素失败！\n"); // 队列为空，无法获取队首元素exit(-1); // 退出程序}
}// 获取队尾元素
DataType QueueTail(Queue* q)
{assert(q); // 断言q不为NULLif (!QueueEmpty(q)){return q->a[q->rear - 1]; // 返回队尾元素的值}else{printf("队列已空，获取队尾元素失败！\n"); // 队列为空，无法获取队尾元素exit(-1); // 退出程序}
}// 获取队列中元素的数量
int QueueSize(Queue* q)
{assert(q); // 断言q不为NULLreturn q->size; // 返回元素数量
}int main()
{Queue q;InitQueue(&q);QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);QueuePush(&q, 9);QueuePush(&q, 10);QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);//QueuePush(&q, 9);//QueuePush(&q, 10);DataType x;x = QueueTop(&q);printf("%d\n", x);x = QueueTail(&q);printf("%d\n", x);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);x = QueueTop(&q);printf("%d\n", x);x = QueueSize(&q);printf("%d\n", x);return 0;
}

如果有同学在部分地方有疑惑，欢迎评论区讨论。

本节内容告一段落，我们下节博客见。

循环队列（数组实现）-CSDN博客

http://www.yayakq.cn/news/817527/

相关文章：

  • 南通优普网站建设制作nodejs做后端的网站
  • 做网站的具体步骤wordpress设置教程
  • 网站建设与优化计入什么科莫wordpress怎么设置标签分类
  • 专业做生鲜的网站建立视频网站要多少钱
  • 孟村县做网站价格北京网站开发最专业的公司
  • 专业从事网站开发公司新媒体营销的定义
  • 网站建设培训招生网站权重不稳定
  • 深圳罗湖住房和建设局网站官网做自由行的网站
  • 电子商务网站需求分析做损坏文档的网站
  • 北风风淘网站开发东莞横沥中学
  • 销售型企业网站建设应遵守的原则优化培训课程
  • 网站优化的作业及意义wordpress历史版本下载
  • 免费广告设计模板网站建博会广州网站
  • php网站开发接口开发网站建设合同违约条款
  • 安卓4.3网站开发兼容广州网络推广
  • 来个网站2021能用的百度搜索热词查询
  • 物流手机网站模板网站建设与维护作业
  • 泰兴做网站公司如何做直接打开网站的二维码
  • 宣传网站模板开锁行业在58做网站有活吗
  • 自定义手机网站建设今天郑州最新状况
  • 一个网站如何产生流量视频制作教学
  • 直播间挂人气自助网站wordpress中文商城
  • 网站都有哪些门户网站 开发语言
  • 丽水市住房和城乡建设局网站通州网站建设电话
  • 网站建设页面底部叫什么网页制作三剑客是指
  • wordpress出于安全考虑北京seo招聘信息
  • 怎么做提高网站排名多少人再用wordpress
  • 工信部 网站备案查询wordpress 控制台
  • 微信 网站应用开发便宜网站开发培训
  • 四川网站建设山东平台网站建设找哪家