当前位置：网站首页>循环队列与扩容
循环队列与扩容
2022-04-21 22:37:00 【hello world 999】
循环队列与扩容
1.顺序队列操作
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct{
int *data;
int front, rear;
int length;
}SqQueue;
//1.队列初始化
SqQueue *InitQueue(int n){
SqQueue *sq = (SqQueue *)malloc(sizeof(SqQueue));
sq->data = (int *)malloc(sizeof(int) * n);
sq->length = n;
sq->front = sq->rear = 0;
return sq;
}
//2.队列销毁
void DestroyQueue(SqQueue *sq){
if (sq == NULL) return;
free(sq->data);
free(sq);
return;
}
//3.队列判空
int QueueEmpty(SqQueue *sq){
return sq->front == sq->rear;
}
//4.获取队列队首元素
int GetHead(SqQueue *sq){
if(sq->front != sq->rear) return sq->data[sq->front];
}
//5.队列入队
int Push(SqQueue *sq, int val){
if(sq == NULL) return 0;
if(sq->rear == sq->length) return 0;
sq->data[sq->rear] = val;
sq->rear++;
return 1;
}
//6.队列出队
int Pop(SqQueue *sq){
if(sq == NULL) return 0;
if(QueueEmpty(sq)) return 0;
sq->front += 1;
return 1;
}
void print(SqQueue *sq){
printf("Queue : [");
for(int i = sq->front; i < sq->rear; ++i){
i != sq->front && printf(", ");
printf("%d", sq->data[i]);
}
printf("]\n");
return ;
}
int main(){
srand(time(0));
#define MAX_OP 20
SqQueue *sq = InitQueue(10);
for(int i = 0; i < MAX_OP; ++i){
int op = rand() % 4;
int val = rand() % 100;
switch(op){
case 0:
case 1:
case 2:{
printf("push %d to the Queue = %d\n", val, Push(sq, val));
}break;
case 3:{
printf("pop %d from the Queue = ", GetHead(sq));
printf("%d\n", Pop(sq));
}break;
}
print(sq);
}
#undef MAX_OP
DestroyQueue(sq);
return 0;
}
普通队列存在假溢出现象，注意到最后5次push操作全部失败，但是queue队列中的元素却并没有达到设置的最大容量值10
2.循环顺序队列：
为了处理顺序队列的假溢出问题，
将普通队列修改为循环队列，程序中主要修改三个部分：
- 对于SqQueue结构体：增加一个count变量用于记录循环队列中实际存储的元素个数
typedef struct{
int *data;
int front, rear;
int length;//队列容量
int count;//实际存储的元素个数
}SqQueue;
- 对于push操作的修改：当尾指针达到队尾时，再添加元素将其重新调到队头
if(sq->rear == sq->length) sq->rear = 0;//尾指针置0
sq->count++;
- 对于pop操作的修改：当头指针达到队尾时，再删除元素则将其重新调到队头
if(sq->front == sq->length) sq->front = 0;//头指针置0
sq->count--;
循环顺序队列的实现：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct{
int *data;
int front, rear;
int length;
int count;
}SqQueue;
//1.队列初始化
SqQueue *InitQueue(int n){
SqQueue *sq = (SqQueue *)malloc(sizeof(SqQueue));
sq->data = (int *)malloc(sizeof(int) * n);
sq->length = n;
sq->front = sq->rear = 0;
sq->count = 0;
return sq;
}
//2.队列销毁
void DestroyQueue(SqQueue *sq){
if (sq == NULL) return;
free(sq->data);
free(sq);
return;
}
//3.队列判空
int QueueEmpty(SqQueue *sq){
return sq->count == 0;
}
//4.获取队列队首元素
int GetHead(SqQueue *sq){
if(sq->front != sq->rear) return sq->data[sq->front];
}
//5.队列入队
int Push(SqQueue *sq, int val){
if(sq == NULL) return 0;
if(sq->count == sq->length) return 0;
sq->data[sq->rear++] = val;
if(sq->rear == sq->length) sq->rear = 0;//尾指针置0
sq->count++;
return 1;
}
//6.队列出队
int Pop(SqQueue *sq){
if(sq == NULL) return 0;
if(QueueEmpty(sq)) return 0;
sq->front++;
if(sq->front == sq->length) sq->front = 0;//头指针置0
sq->count--;
return 1;
}
void print(SqQueue *sq){
printf("Queue(%d) : [", sq->count);
for(int i = 0; i < sq->count; ++i){
i && printf(", ");
printf("%d", sq->data[(i + sq->front) % sq->length]);
}
printf("]\n");
return ;
}
int main(){
srand(time(0));
#define MAX_OP 20
SqQueue *sq = InitQueue(10);
for(int i = 0; i < MAX_OP; ++i){
int op = rand() % 4;
int val = rand() % 100;
switch(op){
case 0:
case 1:
case 2:{
printf("push %d to the Queue = %d\n", val, Push(sq, val));
}break;
case 3:{
printf("pop %d from the Queue = ", GetHead(sq));
printf("%d\n", Pop(sq));
}break;
}
print(sq);
}
#undef MAX_OP
DestroyQueue(sq);
return 0;
}
3.循环顺序队列扩容：
当循环顺序队列真的达到最大容量时（真溢出），可以对其进行扩容操作：
注意：注意：如果使用realloc进行扩容，则队列中的元素很可能会出现顺序错乱，故应该使用malloc或者calloc实现扩容操作
关键代码：
//SqQueue扩容操作
int expand(SqQueue *sq){
int extend_size = sq->length;//扩容一倍
int *p;
//(1)开辟新的空间
while(extend_size){
p = (int *)malloc(sizeof(int) * (sq->length + extend_size));
if(p != NULL) break;//malloc扩容成功
extend_size >>= 1;//malloc扩容失败则将扩容容量extend缩小,再次尝试扩容
}
if(p == NULL) return 0;//循环扩容失败
//(2)将原队列数据转移到新队列中
for(int i = 0; i < sq->count; ++i){
p[i] = sq->data[(i + sq->front) % sq->length];//逐个将队列中的元素进行转移
}
//手动释放原队列空间
free(sq->data);
sq->data = p;
//更改新队列基本信息
sq->front = 0, sq->rear = sq->count;
sq->length += extend_size;
return 1;
}
//5.队列入队
int Push(SqQueue *sq, int val){
if(sq == NULL) return 0;
if(sq->count == sq->length){
//循环顺序队列已满需要扩容
if(!expand(sq)){
printf(RED("fail to expand !\n"));
return 0;
}
printf(GREEN("success to expand! the new length = %d\n"), sq->length);
}
sq->data[sq->rear++] = val;
if(sq->rear == sq->length) sq->rear = 0;//尾指针置0
sq->count++;
return 1;
}
完整程序：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 34)
#define GREEN(a) COLOR(a, 32)
typedef struct{
int *data;
int front, rear;
int length;//容量
int count;//元素个数
}SqQueue;
//1.队列初始化
SqQueue *InitQueue(int n){
SqQueue *sq = (SqQueue *)malloc(sizeof(SqQueue));
sq->data = (int *)malloc(sizeof(int) * n);
sq->length = n;
sq->front = sq->rear = 0;
sq->count = 0;
return sq;
}
//2.队列销毁
void DestroyQueue(SqQueue *sq){
if (sq == NULL) return;
free(sq->data);
free(sq);
return;
}
//3.队列判空
int QueueEmpty(SqQueue *sq){
return sq->count == 0;
}
//4.获取队列队首元素
int GetHead(SqQueue *sq){
if(sq->front != sq->rear) return sq->data[sq->front];
}
//SqQueue扩容操作
int expand(SqQueue *sq){
int extend_size = sq->length;//扩容一倍
int *p;
//(1)开辟新的空间
while(extend_size){
p = (int *)malloc(sizeof(int) * (sq->length + extend_size));
if(p != NULL) break;//malloc扩容成功
extend_size >>= 1;//malloc扩容失败则将扩容容量extend缩小,再次尝试扩容
}
if(p == NULL) return 0;//循环扩容失败
//(2)将原队列数据转移到新队列中
for(int i = 0; i < sq->count; ++i){
p[i] = sq->data[(i + sq->front) % sq->length];//逐个将队列中的元素进行转移
}
//手动释放原队列空间
free(sq->data);
sq->data = p;
//更改新队列基本信息
sq->front = 0, sq->rear = sq->count;
sq->length += extend_size;
return 1;
}
//5.队列入队
int Push(SqQueue *sq, int val){
if(sq == NULL) return 0;
if(sq->count == sq->length){
//循环顺序队列已满需要扩容
if(!expand(sq)){
printf(RED("fail to expand !\n"));
return 0;
}
printf(GREEN("success to expand! the new length = %d\n"), sq->length);
}
sq->data[sq->rear++] = val;
if(sq->rear == sq->length) sq->rear = 0;//尾指针置0
sq->count++;
return 1;
}
//6.队列出队
int Pop(SqQueue *sq){
if(sq == NULL) return 0;
if(QueueEmpty(sq)) return 0;
sq->front++;
if(sq->front == sq->length) sq->front = 0;//头指针置0
sq->count--;
return 1;
}
void print(SqQueue *sq){
printf("Queue(%d) : [", sq->count);
for(int i = 0; i < sq->count; ++i){
i && printf(", ");
printf("%d", sq->data[(i + sq->front) % sq->length]);
}
printf("]\n");
return ;
}
int main(){
srand(time(0));
#define MAX_OP 20
SqQueue *sq = InitQueue(1);
for(int i = 0; i < MAX_OP; ++i){
int op = rand() % 4;
int val = rand() % 100;
switch(op){
case 0:
case 1:
case 2:{
printf("push %d to the Queue = %d\n", val, Push(sq, val));
}break;
case 3:{
printf("pop %d from the Queue = ", GetHead(sq));
printf("%d\n", Pop(sq));
}break;
}
print(sq);
}
#undef MAX_OP
DestroyQueue(sq);
return 0;
}
4.链队列操作：
对比于顺序队列，链队列不会出现假溢出（循环顺序队列解决）和真溢出（循环顺序队列扩容解决）的情况，实现较为简单：
//待完善
版权声明
本文为[hello world 999]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_49167174/article/details/124329190
边栏推荐
- L1-060 心理阴影面积 (5 分)
- Mysql的并发参数调整详解
- We sincerely invite you to sign up for the first openharmony developer growth plan sharing day
- YARN线上动态资源调优
- PyQt5+OpenCV操作本地摄像头
- 爆料丨曝小米本月还有新机，多款旗下产品蓄势待发
- L3-1 then don't worry (30 points) - pit point, test point analysis
- File create file problem
- 获取用户信息-微信小程序
- L1-059 ringing stupid bell (20 minutes)
猜你喜欢
Outsourcing student management system detailed architecture design document
2022 Intermediate Accounting Title Financial Management exercises and answers
File create file problem
外包学生管理系统详细架构设计文档
![OS Experiment 3 [process communication]](/img/78/e89e0819ae345cb464613935508eac.png)
OS Experiment 3 [process communication]
L3-1 那就别担心了 (30 分)——坑点，测试点分析
Reproduce the pathways language model using colossal AI
![[matlab] matlab drawing operation skills](/img/ec/65c822e54847fcc8d799218499542c.png)
[matlab] matlab drawing operation skills
学完链表，不去找几个经典例题巩固一下知识？链表的五大OJ经典例题，你会吗？不妨来看一看（知识剖析+图形理解）
Collection of some websites
随机推荐
LeetCode146-LRU缓存-模拟-双向链表-哈希表-数据结构-操作系统
L3-1 then don't worry (30 points) - pit point, test point analysis
2022年一级注册建筑师考试建筑材料与构造复习题及答案
2022 intermediate accounting title examination economic law practice questions and answers
解锁OpenHarmony技术日！年度盛会，即将揭幕！
读书笔记《秋园》《浮木》《我本芬芳》
L1-055 谁是赢家 (10 分)
[RL] 深入理解Tabular Leaning (MC/TD) 过程中的梯度下降使用
Review questions and answers of building materials and structures in 2022 first-class registered architect examination
点云双边滤波
The next stop of cloud native microservices is the heavy upgrade of microservice engine MSE
CC10000.ZABBIX———————————————
HTTP cache notes
D:MATLAB. N practical skills -MATLAB Chinese Forum essence summary
1957年高考数学题
CC10000.MySQL———————————————
Black box test - data reading and output mode
【中南林业科技大学】【陈】第九周作业三角形异常处理
It is revealed that Xiaomi has new machines this month, and many of its products are ready to go
Opencv -- histogram processing