空间链接制作网站,淮安哪里有做网站的,建立网站的优势,阿里云轻量级wordpress目录
队列的定义
普通顺序队列的劣势——与链队列相比
顺序队列实现方法#xff1a;
一、动态增长队列 1、初始化队列 2、元素入队 3、判断队列是否为空 4、元素出队 5、获取队首元素
6、获取队尾元素 7、获取队列元素个数
8、销毁队列 总结#xff1a;
动态增长队列…目录
队列的定义
普通顺序队列的劣势——与链队列相比
顺序队列实现方法
一、动态增长队列 1、初始化队列 2、元素入队 3、判断队列是否为空 4、元素出队 5、获取队首元素
6、获取队尾元素 7、获取队列元素个数
8、销毁队列 总结
动态增长队列完整测试代码
二、固定长度队列
1、与动态增长队列的差异
2、判断是否队满
固定长度队列完整测试代码 本节我们采用数组顺序表形式实现队列学习单链表实现请点击下方链接
队列—单链表实现C语言版-CSDN博客
为了减少数组初始长度过大对内存空间的浪费本节我们采用动态内存管理相关函数请的介绍点击下方链接
动态内存函数mallocfreecallocrealloc-CSDN博客
循环队列的实现
循环队列数组实现-CSDN博客 队列的定义
队列是一种基本的数据结构它是一种先进先出First In First OutFIFO的线性结构。队列只允许在表的一端进行插入而在另一端进行删除操作。这就相当于把数据排成一排先插入的排在前面后插入的排在后面之后进行删除操作时也只能从前面依次删除。这种数据结构一般用于需要按照先后顺序进行处理的问题如模拟系统、计算机网络中的缓存、操作系统中的进程调度等。队列的基本操作包括入队插入元素到队尾和出队从队头删除元素队列还有一个重要的特性就是队列的长度是动态变化的随着入队和出队的操作进行不断变化。
普通顺序队列的劣势——与链队列相比 长度固定普通数组队列的长度是固定的一旦数组被分配其长度无法改变。当队列元素数量超过数组长度时需要进行数组的扩容操作这会导致性能上的开销。 内存的浪费因为普通数组队列的长度固定可能会出现队列中存在空闲的位置导致内存的浪费。
为了解决上述 问题1我们在本节中对顺序表采取动态内存管理在必要时更新数组的长度以保证顺序队列的长度足够使用。 补充问题2 的解决需要使用循环队列本节内容先为大家介绍一般队列的实现等同学们对队列有了充分的理解之后我们下节再进行循环队列的学习。 顺序队列实现方法
一、我们首先定义一个数组数组的头部为队首尾部为队尾。每当插入一个元素时就将元素放在队尾当删除一个元素时将队首的元素删除。当队列为空时不能再删除元素。
二、我们采用双指针法时刻记录队列的队首和队尾 定义一个固定大小的数组作为队列的存储空间并定义两个指针front和rear分别指向队列的队首和队尾。 初始化队列时将front和rear都设置为0表示队列为空。 插入元素时将元素放入rear指针指向的位置并将rear指针后移一位。 删除元素时将front指针后移一位。 判断队列是否为空只需要判断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
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef 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进行自增更新队尾索引所以在本代码中队满的判断条件是rearMAXLEN。 2、判断是否队满
当对固定长度队列添加元素时如果当前队列队尾指针已达到数组长度由于队列只能从队尾添加元素此时我们不能再为队列添加新的元素。所以在我们为队尾添加元素时我们首先要判断队列是否已满——即队尾指针是否达到数组容量的最大值。 //判断队列是否为满
bool QueueFull(Queue* q)
{assert(q); // 断言q不为NULLif (q-rear MAXLEN){return true; // 尾部位置达到数组长度最大值队列为满}return false; // 队列不为满
}
明白了以上几点我们对动态增长队列的代码稍作修改添加判断队列是否已满的函数并对增加队列元素作出限制就可得到固定长度队列的代码。 固定长度队列完整测试代码
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.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博客
