数据结构|设计一个【循环队列】C语言数组模拟实现-创新互联
循环队列
当前题目:数据结构|设计一个【循环队列】C语言数组模拟实现-创新互联
网页路径:http://scyanting.com/article/shids.html
- 一、普通队列概念
- 二、循环队列概念
- 三、循环队列实现:代码+注释
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
队列可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。链表头插头删比较方便,效率比较高,链表具体实现可以参考我的码云。
三、循环队列实现:代码+注释设计循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。设计循环队列由于找队尾比较麻烦,因此我们使用数组实现。
为了能够使用head,tail来区分队空还是队满,我们常常认为当head==tail的时候认为其队空,head=tail+1的时候,认为其队满
这样就可在给定队列大小的基础上多开一个结点,用来搞定!
typedef struct {int* arr;
//指向队头
int head;
//指向队尾的下一个
int tail;
//队所存数据的个数
int k;
} MyCircularQueue;
//检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//检查循环队列是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj);
//创建队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* newnode=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开辟一个数组,用来判断队满的情况
newnode->arr=(int *)malloc(sizeof(int)*(k+1));
newnode->head=newnode->tail=0;
newnode->k=k;
return newnode;
}
//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);
if(myCircularQueueIsFull(obj)){return false;
}
obj->arr[obj->tail]=value;
obj->tail++;
//如果在下标为k位置插入,tail要回到下标为0处,需要取模
//obj->tail %=(obj->k+1);
if(obj->tail==obj->k+1){obj->tail=0;
}
return true;
}
//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;
}
obj->head++;
//在下标为k位置删除,head+1也要回到下标0的位置,需要取模
//obj->head %=(obj->k+1);
if(obj->head==obj->k+1){obj->head=0;
}
return true;
}
//从队首获取元素。如果队列为空,返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);
if(myCircularQueueIsEmpty(obj)){return -1;
}
else{return obj->arr[obj->head];
}
}
//获取队尾元素。如果队列为空,返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);
if(myCircularQueueIsEmpty(obj)){return -1;
}
//判断tail是否在下标为0处,
// int tail=obj->tail==0? k:obj->tail-1;
int tail=(obj->tail+obj->k)%(obj->k+1);
return obj->arr[tail];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);
return obj->tail==obj->head;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);
return (obj->tail+1)%(obj->k+1)==obj->head;
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);
//要先销毁开辟的数组
free(obj->arr);
free(obj);
}
常见问题:
1.当(obj->tail+1)%(obj->k+1)==obj->head表示队列已满,取余是为了循环
2.其余存在取模运算的接口也是为了循环
如果写好的代码不知道如何调试运行,可以点击我进行测试哦~
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前题目:数据结构|设计一个【循环队列】C语言数组模拟实现-创新互联
网页路径:http://scyanting.com/article/shids.html