51这个网站还有吗,logo在线制作免费平台,怎么做内网网站,广西网站建设-好发信息网循环队列#xff08;环形队列#xff09; 循环队列的概念及结构循环队列的实现 循环队列的概念及结构
循环队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#xff08;先进先出#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。… 循环队列环形队列 循环队列的概念及结构循环队列的实现 循环队列的概念及结构
循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 注循环队列的空间大小是固定的
循环队列的实现
环形队列可以使用数组实现超出数组的范围回到起始位置也可以使用循环链表实现尾指针的next指向头节点。选用数组实现循环队列更好因为数组缓存利用率更高没有扩容的代价。
环形队列实际开辟的空间大小要比所存数据的队列长度多开辟一个空间的大小。如果环形队列实际开辟的空间大小和所存储数据个数一样时会导致环形队列所处空的状态和满的状态是一样的。这样便无法区分。 因此环形队列必须多留出一个空间这个空间不能存放数据这样才能很好的区别环形队列的状态是空还是满。 在环形队列中队列为空时队头队尾指向同一个位置。当队列不为空时队头指向插入的第一个数据队尾指向最后一个数据的下一个位置。当tail1等于front时说明环形队列已满。 循环队列的定义 循环队列选择用数组实现循环队列需要用一个指针来指向存储队列数据的空间用两个变量来记录队列中存储数据的起始对头和末尾队尾的数组位置最后用一个变量记录队列的存储数据的最大容量。
typedef struct {int *a;int front;int tail;int k;
} MyCircularQueue;循环队列的初始化 循环队列的初始化首先创建一个循环队列其次对该结构体的成员进行初始化即可。
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cur(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cur-a(int *)malloc(sizeof(int)*(k1));cur-kk;cur-front0;cur-tail0;return cur;
}注k表示的是设置队列的长度 循环队列的入队列 入队列操作首先要判断循环队列是否已满如果满了则返回假如果没满则向循环队列插入一个数据即在tail位置放数据然后tail向后挪动一个位置最后返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-tail]value;obj-tail;obj-tailobj-tail%(obj-k1);return true;
}注tail的位置为k1时就需要对tail进行处理防止tail对数组进行越界访问。这也遵循了循环队列的原则当访问到数组末尾时再次访问应该访问到数组的起始位置。 循环队列的出队列 出队列操作首先判断循环队列是否为空如果为空了则出队列失败返回假如果不为空则从循环队列中删除一个元素即只需将front往后挪一个位置即可如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}obj-front;obj-front%obj-k1;return true;
}注当front为k1时处理方式和入队列的tail类似。 获取循环队列的对头数据 获取循环队列的对头数据首先判断循环队列是否为空如果为空则返回-1如果不为空只需通过front的位置获取数组中的数据并返回该数据即可。
int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];
}获取循环队列的对尾数据 获取循环队列的对尾数据首先判断循环队列是否为空如果为空则返回-1如果不为空只需通过tail获取tail的前一个位置的数组中的数据并返回该数据即可。
int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}int prevtailobj-tail-1;if(obj-tail0){prevtailobj-k;}return obj-a[prevtail];
}注当tail为0时此时取队尾数据时取的是数组下标为k的元素数据。因为tail表示的是最后一个有效数据的下一个位置。 循环队列的判空 循环队列的判空只需判断队头和队尾是否相等即可
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return obj-frontobj-tail;
}循环队列的判满 循环队列的判满只需判断队尾的下一个位置和队头是否相等即可
bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);return obj-front((obj-tail)1)%(obj-k1);
}注当tail为k时tail的下一个位置为0此时处理情况和出入队列的处理情况类似。 循环链表的销毁 循环链表的销毁首先要对循环链表结构体中的成员进行释放然后再对循环链表进行释放即可。
void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj-a);free(obj);objNULL;
} 注意
环形队列中存储数据的空间是一开始就要创建好的删除数据时是front指针往后走存储数据的空间不销毁。插入数据时是往tail所指向的空间放数据不申请空间tail往后走。循环队列如果用链表实现最好用双向链表实现单向链表不好去找循环队列的队尾数据而且采用链表的形式实现需要定义节点的结构体以及在初始化方面需要创建k1个节点并建立连接这样操作起来很麻烦没有数组省事因此用数组实现循环队列更好。
