用户研究网站,公司注册核名流程,珠海网站开发价格,台州网站建设方案咨询一、循环队列的定义
定义#xff1a;队列主要有顺序队列#xff0c;循环队列#xff0c;双端队列#xff0c;优先队列。而当中循环队列是一种线性数据结构。它也被称为“环形缓冲器”。它只允许在一端进行插入操作#xff0c;即队尾#xff08;rear#xff09;#xf…一、循环队列的定义
定义队列主要有顺序队列循环队列双端队列优先队列。而当中循环队列是一种线性数据结构。它也被称为“环形缓冲器”。它只允许在一端进行插入操作即队尾rear而在另一端进行删除操作即队头 (front)其操作表现基于FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。向队列中插入新的数据元素称为入队新入队的元素就成为了队列的队尾元素。 特点 循环队列允许元素在队尾插入在队头删除同时遵循先进先出原则。由于循环队列是基于数组实现的所以它的访问速度很快特别是在移动元素时。如果需要大量添加和删除元素循环队列比链表更有效率因为它不需要频繁地移动指针来访问元素。不支持随机访问元素因此不能像数组那样直接访问特定位置的元素。 二、循环队列的实现
本篇文章要实现的操作如下 本文的思路来自设计循环队列
2.1 循环队列的行为
我们使用顺序表来实现循环队列在开始时初始化出队列的大小为k。并分别用front指向队头元素rear指向队尾元素的下一个位置。
typedef struct
{int* a;int front;int rear;int k;
} MyCircularQueue;2.2 循环队列的初始化
我们在申请空间时多申请一个空间用来解决假溢出问题。这样方便我们判断队列何时满了rear的下一个位置是front就满了
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* q(MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-a(int*)malloc(sizeof(int)*(k1));q-front0;//头q-rear0;//尾下一个q-kk;return q;
}2.3 循环队列的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj-frontobj-rear;
}2.4 循环队列的判满
可不要简单的以为循环队列满的条件就是rear 1 front我们要考虑下面两种情况 情况一 情况二 上面两种情况队列都是满的显然我们不能简单的用front rear 1来判断队列是否已满。
直接下结论我们可以用表达式(rear 1) % (k 1) front来判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-rear1)%(obj-k1)obj-front;//当rear指向多出来的位置时通过驱魔
}2.4 循环队列的入队
在入队的时候我们也要考虑两种情况 情况一 情况二
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj))return false;obj-a[obj-rear]value;obj-rear;obj-rear%(obj-k1);return true;
}2.5 循环队列的出队
在出队时同样要考虑两种情况 情况一 情况二
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return false;obj-front;(obj-front)%(obj-k1);return true;
}2.6 返回队头元素
由于队头指针指向的就是队头元素因此直接返回下标位置的元素即可
int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}2.7 返回队尾元素
由于队尾指针指向的是队尾元素的下一个位置因此要考虑两种情况 情况一 情况二
int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-rearobj-k)%(obj-k1)];
}2.8 循环队列的销毁
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
